Tetrahedral Dice Game
Pobability; Difficulty: medium
How likely are you to win this game?
The Riddler Classic from this week (May 13, 2022) is probability exercise involving tetrahedral dice. While the main question posed is the likelihood of winning the game, calculating the expected number of rounds reveals an interesting property of this game. Here’s the Classic reproduced:
From Ross O’Brien comes a game of nonconformist dice:
You have four fair tetrahedral dice whose four sides are numbered 1 through 4.
You play a game in which you roll them all and divide them into two groups: those whose values are unique, and those which are duplicates. For example, if you roll a 1, 2, 2 and 4, then the 1 and 4 will go into the “unique” group, while the 2s will go into the “duplicate” group.
Next, you reroll all the dice in the duplicate pool and sort all the dice again. Continuing the previous example, that would mean you reroll the 2s. If the result happens to be 1 and 3, then the “unique” group will now consist of 3 and 4, while the “duplicate” group will have two 1s.
You continue rerolling the duplicate pool and sorting all the dice until all the dice are members of the same group. If all four dice are in the “unique” group, you win. If all four are in the “duplicate” group, you lose.
What is your probability of winning the game?
*spoiler alert* solution and answer follow in the sections below.—
Solution (probability of winning)
This puzzle is similar to the recent Leveling up your armor Riddler from a couple of weeks ago. This too can be modeled as a finite space discrete time Markov chain. But let’s look at a solution based on probability first principles alone:
Leaving aside the starting state, while the game is still active, there are four states that could possibly result from every round of dice throw and sort routine:
- Win (W): The roll results in all 4 dice having distinct digits (W in the fig. below). Game ends with a Win.
- (2,2) (B): Two dice each in the unique and duplicate piles (B in the fig.)
- (1,3) (C): One unique and 3 in duplicate pile—all the duplicates with the same digit (C in the fig)
- Loss (L): there are no uniques and only duplicates—either all 4 digits are the same OR there are two pairs with each pair having a (different) digit. Game ends with a Loss.
These four states along with the starting state S are shown in the figure below, along with the associated probabilities of transitioning from one to the other; with fractions written out unsimplified, so that the numerator is the number of possible outcomes resulting in that particular transition and the denominator, the total number of possible outcomes.
The transition probabilities are determined from straightforward combinatorial calculations.
As one example: if you have 2 uniques and 2 duplicates, the probability of rolling the 2 dice in the duplicate pile to again end up with 2 uniques and 2 duplicates, can be calculated as follows:
– Total number of possible outcomes rolling two tetrahedral dice = 16
– Number of ways in which the two rolled dice end up with one whose digits match one in the unique pile = 2 (can select either die to match a unique) X 2 (two uniques to choose from) X 2 (two ways to choose the remaining die to be unique) = 8
– Number of ways in which the two rolled die result in the same digit = 2
For a total of 8 + 2 = 10 out of possible 16 equally likely ways in which you could start with two uniques and two duplicates and still end up with 2 uniques and two duplicates.
The other transition probabilities shown are calculated similarly. You can check that all the outgoing transition probabilities from a state sum to 1 as they should—you have to end up in one of the possible states after a roll!
Starting at S there is a 24/256 chance of getting a win in that first throw and ending at W, a 144/256 chance of going to state B and a 48/256 chance of going to C. Let \(s\), \(b\) and \(c\) be the probabilities of ending up with a win (i.e. ending in state W) when starting in states S, B and C respectively. Conditioning on that first throw gives us the following three equations:
\begin{align*}
s \ &= \ \frac{24}{256} \ + \ \frac{144}{256}b \ + \ \frac{48}{256}c \\
b \ &= \ \frac{2}{16} \ + \ \frac{10}{16}b \ + \ \frac{2}{16}c \\
c \ &= \ \frac{6}{64} \ + \ \frac{36}{64}b \ + \ \frac{12}{64}c \\
\end{align*}
The first equation is saying that the probability of winning starting from S is just the sum of the probabilities of the three possible ways to win:
- the probability of winning directly in that first round
- the probability of getting to B in the first round times the probability of winning from B
- the probability of getting to C in the first round times the probability of winning from C
The other two equations follow the same line of reasoning.
Solving for \(s\), \(b\) and \(c\) gives us
\[
s = \mathbf{{\color{Red} {\frac{9}{20}}}} \\ \\
b = \frac{29}{60} \\ \\
c = \frac{9}{20} \\ \\
\]
The required probability of winning this game is then 9/20 or 45%.
It’s interesting to note that the probability of winning starting at S is the same as starting in state C i.e. with 1 die in the unique pile and 3 in the duplicate!
Read on for the calculation of the expected number of rounds required to reach a final (win/loss) outcome. This yields a pretty interesting result.
Expected number of rounds this game lasts:
Let \(E_s\), \(E_b\), \(E_c\) be the expected number of rounds it takes to end the game starting from states S, B and C respectively.
The game ends whenever a transition is made to states W or L. Similar to the method used to calculate the probability of winning, we condition on where we land on that first throw and note that landing on a state other than win/lose results in one extra turn besides the journey from that point on. This gives us the following equations:
\begin{align*}
E_s \ &= \ \frac{24+40}{256}(1) + \frac{144}{256}(1 + E_b) + \frac{48}{256}(1 + E_c) \\
E_b \ &= \ \frac{2+2}{16}(1) + \frac{10}{16}(1 + E_b) + \frac{1}{16}(1 + E_c) \\
E_c \ &= \ \frac{10+6}{64}(1) + \frac{36}{64}(1 + E_b) + \frac{12}{64}(1 + E_c) \\
\end{align*}
Solving we get \(E_s\) = \(E_b\) = \(E_c\) = 4.
Besides noting that on average this game will take 4 rounds to be completed from start, this solution has the interesting implication that if the game does not end in a particular round, you will still need 4 more rounds on average from that point on till the game ends—the same 4 rounds you would have needed on average at the start! This is thus an example of a memoryless process in the case when a round results in a non win/loss outcome.
2 thoughts on “Tetrahedral Dice Game”
Interesting, thank you!
I am wondering about part “The first equation is saying that the probability of winning starting from S is just the sum of the probabilities of the three possible ways to win:
the probability of winning directly in that first round
the probability of getting to B in the first round times the probability of winning from B
the probability of getting to C in the first round times the probability of winning from C”
Is it truly “in the first round”, or “in any round before the end of the game”? E.g. imagining path B – G – B – W.
Also wondering: is there a way to connect this approach with the approach of power matrices (i.e. the limit of the transition matrix to power n, times the initial probabilities, gives the probability of being in state W eventually). How are they connected? How are they different ways to look at the same problem?
Thanks. This is conditioning an eventual win based on where you end up in round 1. So it includes the path you describe: in the getting to B first and then ending up with a win.
Yes, you can look at as a Markov chain with a transition probability matrix P. Calculating \(P^n\) which pre-multiplied by the initial state vector gives you the limiting distribution and probabilities of being in states W or L. All other states are transient and so will have a long term probability of 0.