OddThinking

This is background information for Part 1.

About six years ago, I was taught a dice game called Farkle. If you haven’t heard of it, it is not the same as Yahtzee, but it is close enough for this discussion.

I have been meaning to get around to modelling Farkle, and coming up with an optimal strategy. However, I quickly eventually realised that there was an element of Game Theory I didn’t know enough about. I understand trying to maximise your expected value on each turn. I understand minimaxing between turns. However, I don’t have a good grasp of how to optimise taking greater risks when you are falling behind, and playing safe when you are far in front. In short, I need to learn about Expectimax, and related areas.

Before I get formal, I wanted to play a little with the ideas I’ve already had independently. My main goal for this exercise: see if my ideas about data structures and algorithms for probability distributions would work.

The reason for all these different, related, games, was to allow me to incrementally work on the features of the code, from simplest to more complex.

In short, the answer was yes, but I learned a lot along the way. I over-engineered some parts, and under-engineered others. I haven’t shown that it scales for a full-sized game. I am ready to ditch what I wrote and start again for a much better implementation. In other words, I am a happy developer, playing.

To be clear, my approach is not a Monte Carlo simulation. It looks at every outcome, and the possibility that outcome will eventuate.

My secondary goal was to see if I could come up with some moderately interesting strategies with these simple rules.

What do I mean by interesting? Well, jumping ahead, the Basic Strategy is boring. You decide whether to throw each of dice independently, based only on its own pips. You could decide whether to re-roll the blue die even before you had seen the red die.

A more interesting strategy would be if you needed to see the blue die before deciding whether to re-roll the red die.

A really interesting strategy (for small values of “really”) would be if the strategy recommended breaking up doubles – in particular a double 4. If you rolled two fours, but the total of eight wasn’t sufficient to win frequently enough, you might reasonably re-roll both of them, but it would be cool if the optimal strategy was to re-roll one, but keep the other. As I added new rules to the games, I was watching for that to be optimal strategy.

See Part 3 to see how I did against these secondary goals.