Roll More to Win More
Since the last installment of Probability in Games, a reader requested an analysis and strategy suggestion for a dice game that is simple to explain and play, but complicated to analyze and strategize about. In fact, there is a thread discussing this hypothetical game on the Board Game Geek (BGG) Forums. When I began to work through analyzing this game, I found one very surprising insight, and one very expected complication. So I’ll split this analysis into two parts: the surprising insight will be discussed below, and the expected complication will be addressed in part two.
The Game in Question
The game in question involves rolling five customs six-sided dice with sides labelled: FAIL, FAIL, FAIL, PASS, PASS, ACE. The player’s goal is to minimize the number of dice showing FAIL, although each die showing ACE negates a single FAIL when counting this score. After rolling all five dice, the player must choose to set aside one or more dice (to not be rolled again), and then reroll their remaing dice. Play continues in this way until all five dice are set aside, at which point their score is assessed.
One of the strategies proposed on BGG for this game is to always set aside any dice showing PASS or ACE, and to reroll as many dice showing FAIL as possible. But this strategy does not appear to be optimal. There are a few cases cited in that thread where rolling a die that shows PASS leads to better expected results. Between this article and its successor, we’ll investigate the optimal strategy for this game.
How can risking an extra FAIL by rerolliong a PASS be part of an optimal strategy? Since you must lock at least one die with every roll, choosing to roll more dice will give you the option of more future rolls before you must stop. And each of these extra rolls could give you additional chances to improve your score. In this specific game, the fact that a PASS has a chance of being improved to an ACE makes the value of these extra rolls more apparent. But what if that were not the case. Is there be a game where the optimal strategy involves rerolling dice showing their best possible face so that you have the option of additional rolls in the future?
From Dice to Coins
To help understand the value of these extra rolls without the confound of ACEs negating FAILs, let’s consider a slight modification to the game described aboive. Let’s replace the ACE side on each custom die with a side labelled PASS. This gives each die a 50/50 chance to roll PASS/FAIL. Which for our purposes, functions similar to a fair coin toss. If we assign FAIL to the tail sides of our coins, then our score that we are trying to minimize will be the number of tails on these coins. I’ll stick with this coin flipping terminology for this variant to help distinguish it from the original game, but keep in mind how similar the two games truly are.
Let’s come up with an optimal strategy for this new game by computing the expected value for every possible set of coin flips. We’ll start with a single coin and then work our way up to five, so that we can can make use of our previous expected value computations when deciding between reflipping 0, 1, 2, 3, or 4 of coins.
Computing an Expected Value
The case of a single coin flip is a great one to quickly review the idea of expected value. We weight each of our possible scores by the chance of flipping them, and this is known as the expected value. In our game we have a 1/2 chance of flipping heads which leads to a score of 0, and a 1/2 chance of flipping tails which leads to a score of 1. When we need to reference the expected value of flipping a single coin in the future, I’ll refer to this value as E1 (E for expected value, and 1 to indicate the consideration of a single coin being flipped).
Two Coins for the Show
When flipping two coins, there are four possible outcomes. I’ve listed the probabilities of each below, with coins showing heads = H and tails = T. Since HT and TH are different permutations of the same outcome, they are combined into a single line below and this explains why the probability of this outcome is higher than the other two.
When flipping two coins, we get the option of re-flipping a single coin. So let’s extend this table to include the expected score both with (flip1) and without (flip0) this extra coin flip. Whenever possible, we’ll prefer to flip coins showing tails over coins showing heads. Since heads are listed to the left of tails in each row, you can think of this as flipping the right-most coins from this order.
To help ensure this table is clear, let’s step through the middle row. The chances of flipping HT on two coins is 1/2. The score of this flip without any reflips is 1, because it includes one coin showing tails. After reflipping the worst (right-most) coin showing tails here, our expected score is 0 (from the heads showing coin that we set aside) plus E1 (the expected score from a single coin flip, as calculated above).
Our best strategy will involve choosing between flip0 and flip1 to minimize the resulting expected score. This is the purpose of the final column in the table above. And we’ll always consider use this best strategy when computing the expected value for our coin flips.
Three Coins to Get Ready, Four to Go
When building a similar table for three coins, we’ll need an extra column to account for reflipping two of those three coins (labelled flip2). This will help us compute E3.
E3 = (1/8 * 0) + (3/8 * 1/2) + (3/8 * 5/8) + (1/8 * 13/8) = 5/8
If you were surprised to see the trend of increasing expected values from E1=1/2 to E2=5/8 end with E3=E2, then brace yourself before looking at the table for four coins.
|HHTT||6/16||2||1+E1||E2||E3||E2 = E3|
E4 = (1/16 * 0) + (4/16 * 1/2) + (6/16 * 5/8) + (4/16 * 5/8) + (1/16 * 13/8) = 79/128
The table above gives us our first chance to flip a coin showing heads without lowering our expected value. When we flip HHTT, we find the same expected value for reflipping TT as TTH. But the more surprising result above is that E4=79/128 (~0.6171), which is smaller than E2=E3=5/8 (0.625). So whenever we find two or three tails that are worth flipping, it will actually be BETTER to flip them as part of a group of 4 coins… even when that means reflipping coins that show heads.
All Five Coins
Enough foreshadowing… let’s get to the final table and expected score when flipping all five coins.
E5 = (1/32 * 0) + (5/32 * 1/2) + (10/32 * 79/128) + (10/32 * 79/128) + (5/32 * 79/128) + (1/32 * 207/128) = 1251/2048
What All of this Means
Here’s the result that I found so surprising: that when flipping five coins, the optimal strategy is to reflip as many coins as possible (including heads) whenever our initial flip contains more than one coin showing tails. In fact, with the help of a computer, I’ve extended these tables up to 20 coins and found that the same pattern and optimal strategy applies to all hand sizes 5-20 (and beyond, I would expect). The expected value slowly creeps around 0.6. I calculated E20 to be ~0.5996 (or 3764286286996839944308718867837813911129194142252135609361 / 6277101735386680763835789423207666416102355444464034512896 to be more precise). And the intuitive strategy of only reflipping your tails is only optimal when you have zero or one tails to flip, or owhen you are down to four or fewer available coins.
I like the idea of a game with an optimal strategy of rolling and playing more, in contrast to the lessons from the classic 80s movie War Games. But repeatedly flipping all but one coin until you either hit the jackpot or run out of coins may appeal more to our inner gamblers than our inner strategy gamers. I think the lesson here for strategy game designers here is to avoid positioning players too far above this inflection point.
I hope that this article has shed some light on the value of getting extra flips, rolls, or other kinds of attempts in games. In the next installment, we’ll address the confound of ACEs negating FAILs within these kinds of expected value computations. Feel free to work ahead or in parallel with me, as I continue to analyze this games. I’ll be interested to hear whether your results align with mine, and whether you notice any other patterns or convenient perspectives for working through this kind of analysis.