Thursday, December 24, 2015

Expected Value of a Roll in Farkle

We like to play Farkle in my family (well... I like to). It's a game played with 6 standard dice and the goal is to be the first to get more than 10,000 points. If multiple people have more than 10,000 points after N turns, then the person with the max points wins. We have Farkle Party and play by its scoring rules. A question I often ask myself is, "What should I do next?"

Maybe a little more on how the game is played would help. When it's your turn you roll all six dice. Each time you roll dice you must increase the number of points earned during your turn. If your roll has no dice that add to your score, you rolled a "Farkle" and you get 0 points for your turn and your turn is over. You may end your turn at any time to "bank" the points you've earned that turn. The 10,000 point end goal is for banked points. The leftover dice that don't add to your score after a roll may be re-rolled to continue your turn. A single 1 is worth 100 points. A single 5 is worth 50 points. There are more points awarded for more difficult combinations, such as three-or-more-of-a-kind, that vary depending on the rules you've set. The Wikipedia article linked to above covers many of those variations.

An example. It's your turn and you roll 1-1-2-3-4-6. You may take the two 1s for 200 points or you may just take one of the 1s for 100 points. The rest are worth nothing. You may then roll the remaining four or five dice, respectively, to earn more points. Again, with each roll you must increase your score or your turn ends with 0 points. So say I take 200 points and roll the remaining four and get 2-2-3-6. That's worth 0. I didn't increase my turn's score of 200 with that roll so I get 0 that turn and hand the dice to the next player.

This example was one where I would ask myself if it is better to take 100 points and roll 5 dice or take 200 points and roll 4. Which choice will maximize my expected score?

There's lots of factors that go into answering that question. Am I behind? Or do I hold a comfortable lead over my opponents?  I won't go into that strategy today. For now I will talk about the expected value of a roll.

Let's change the example we've been using. Say I take 200 points, roll four dice, and get 6-6-6-2. Three sixes is worth 600 points. I take those points and am left with one die and 800 points for my turn. What is the expected value of rolling one die? I have a 1/6 chance of getting 100, a 1/6 chance of getting 50, and a 4/6 chance of getting something else and losing my 800 points. So my expected value is $\frac{1}{6}100 + \frac{1}{6}50 - \frac{4}{6}800$ which is $-508.33$ points. I should stop, right? Well it's not exactly that. If I get a 1 or a 5 then I can start over and roll all six dice again to continue building my score. So now the expected value is
E[d_1] = \frac{1}{6}(100+E[d_6]) + \frac{1}{6}(50+E[d_6]) - \frac{4}{6}800
where $E[d_i]$ is the expected value of rolling $i$ dice.

Over several lunch breaks I figured out the expected values for all six $E[d_i]$ in terms of each other. The hard part was calculating the number of ways you can roll different scoring combinations with $i$ dice. Hmm... six equations and six unknowns... that's a system of linear equations! We can solve that.

But wait. Don't we have seven unknowns? We assumed 800 was our current score when that's also an unknown. True. We don't know what our score is or will be when we get to roll $i$ dice. But for now let's calculate our expected values assuming our current score is 0. Then we can calculate them again over many possible values for our current score later.

If we solve this system of linear equations, we find the following expected values:

$E[d_1] = 280$
$E[d_2] = 260$
$E[d_3] = 304$
$E[d_4] = 390$
$E[d_5] = 520$
$E[d_6] = 700$

Interesting that rolling two dice gives the lowest expected value rather than rolling one. I won't go into detail but I'll just say that if we assume our current score is 50 or 150 or $C$ then all of these expected values go down by 50, 150, or $C$.

So if we have 800 points and one die to roll, our expected value for that roll is -520. That means I should stop, right? Or if I go back one roll in the example I can take 100 and have an expected value of 420 or I can take 200 and my expected value of 190. That means I should take 100 and roll five dice, right? I'll weasel out of this by saying it depends.

Like I said earlier, decisions don't just depend on expected value but on what the game situation is. Am I ahead by 1500 points? Behind by 500? How many turns (more or less) are left until someone breaks 10,000? But the expected value gives a gauge of your risk relative to your current score. Fun!