Problem 205: Dice Game

Detailed mathematical approach

Problem Summary

Peter rolls nine four-sided dice with faces numbered \(1\) to \(4\), and Colin rolls six six-sided dice with faces numbered \(1\) to \(6\). The higher total wins, and equal totals are a draw. We must find the probability that Peter's total is strictly greater than Colin's, rounded to seven decimal places in the form 0.abcdefg. ^[1] As usual, all faces are equally likely and the dice independent.

The whole solution in one sentence: for each player we count, die by die, in how many ways each total can be rolled, then add the products of the two counts over all pairs of totals in which Peter's is larger, and divide by the number \(4^9\cdot6^6\) of equally likely outcomes.

Mathematical Approach

A roll of \(n\) dice with \(s\) sides is the ordered list \((f_1,\dots,f_n)\) of the faces shown.

1. The smallest game

Let Peter roll one four-sided die and Colin one six-sided die. The \(4\cdot6=24\) pairs of faces are equally likely, so the probability of an event is the number of pairs in which it happens divided by \(24\), the classical definition of probability. ^[2] Peter wins with the \(6\) pairs \((2,1)\), \((3,1)\), \((3,2)\), \((4,1)\), \((4,2)\), \((4,3)\), the \(4\) pairs \((1,1),\dots,(4,4)\) are draws, and Colin wins with the other \(14\), so Peter wins with probability \(6/24=1/4\). The C++ program checks this value before it solves the real game.

2. Only the totals matter

In the real game an outcome is the list of all fifteen faces, and by the rule of product ^[3] there are

$$\Omega=4^9\cdot6^6=262144\cdot46656=12\,230\,590\,464$$

equally likely outcomes. Only the two totals decide the game, and Peter has just \(28\) possible totals, \(9\) to \(36\), and Colin \(31\), \(6\) to \(36\). Write \(N_{n,s}(t)\) for the number of rolls of \(n\) dice with \(s\) sides whose total is \(t\), and put \(A(p)=N_{9,4}(p)\) and \(B(c)=N_{6,6}(c)\). Any of Peter's \(A(p)\) rolls with total \(p\) can be combined with any of Colin's \(B(c)\) rolls with total \(c\), so by the rule of product \(A(p)\,B(c)\) outcomes have these two totals. Peter therefore wins in

$$W=\sum_{p\gt c}A(p)\,B(c)$$

outcomes, with probability \(W/\Omega\).

3. Adding one die at a time

For two four-sided dice the total \(5\) comes from the rolls \((1,4)\), \((2,3)\), \((3,2)\), \((4,1)\), so \(N_{2,4}(5)=4\), and the totals \(2,\dots,8\) have the counts \(1,2,3,4,3,2,1\). A roll of three dice with total \(7\) is a roll of two dice with total \(7-f\) followed by a last face \(f\), so \(N_{3,4}(7)=3+4+3+2=12\), the sum of the counts of the totals \(6\), \(5\), \(4\) and \(3\).

Claim. \(N_{0,s}(0)=1\), \(N_{0,s}(t)=0\) for \(t\ne0\), and for every \(n\ge0\) and every integer \(t\)

$$N_{n+1,s}(t)=\sum_{f=1}^{s}N_{n,s}(t-f).$$

Proof. The only roll of no dice is the empty list, whose total is \(0\). Cutting off the last face maps the rolls of \(n+1\) dice with total \(t\) and last face \(f\) one to one onto the rolls of \(n\) dice with total \(t-f\), and appending \(f\) reverses it. So there are \(N_{n,s}(t-f)\) such rolls, and adding over \(f=1,\dots,s\) proves the claim. \(\square\)

The recurrence is a convolution: the distribution of a sum of independent variables is the convolution of their distributions. ^[4] Computing the tables for \(1,2,3,\dots\) dice, each from the one before, is dynamic programming. ^[5] By induction, \(N_{n,s}(t)\ne0\) exactly for \(n\le t\le ns\), and the counts add up to \(s^n\). Replacing every face \(f\) by \(s+1-f\) maps rolls one to one and the total \(t\) to \(n(s+1)-t\), so every table is symmetric:

$$N_{n,s}(t)=N_{n,s}\bigl(n(s+1)-t\bigr).$$

For three four-sided dice the totals \(3,\dots,12\) have the counts \(1,3,6,10,12,12,10,6,3,1\), and for two six-sided dice the totals \(2,\dots,12\) have the counts \(1,2,3,4,5,6,5,4,3,2,1\).

4. A closed formula for one count

Multiplying out \((x+x^2+\dots+x^s)^n\) gives one term \(x^{f_1+\dots+f_n}\) per roll; for two two-sided dice, \((x+x^2)^2=x^2+2x^3+x^4\), where the \(2\) counts the rolls \((1,2)\) and \((2,1)\). So \(N_{n,s}(t)\) is the coefficient of \(x^t\), and expanding the polynomial as \(x^n(1-x^s)^n(1-x)^{-n}\) with the binomial theorem and the binomial series gives, for \(n\ge1\) and \(t\ge0\), ^[6]

$$\begin{aligned}N_{n,s}(t)&=\sum_{k=0}^{K}(-1)^k\binom{n}{k}\binom{t-sk-1}{n-1},\\K&=\lfloor (t-n)/s\rfloor.\end{aligned}$$

For Colin's total \(21\) the terms are \(\binom{20}{5}=15504\), \(6\binom{14}{5}=12012\) and \(15\binom{8}{5}=840\), so \(N_{6,6}(21)=15504-12012\)\({}+840=4332\). The programs do not use this formula, but it checks their tables.

5. The two tables of the real game

Nine steps of the recurrence give Peter's table: totals \(9\) to \(36\), counts adding up to \(4^9=262144\), symmetric about \(22.5\), rising from \(A(9)=1\) and \(A(10)=9\) to the largest counts \(A(22)=A(23)=30276\). Six steps give Colin's table: totals \(6\) to \(36\), counts adding up to \(6^6=46656\), symmetric about \(21\), rising from \(B(6)=1\) and \(B(7)=6\) to the largest count \(B(21)=4332\).

6. From two tables to one count

Grouping the terms of \(W\) by Peter's total, the inner sum is the number \(L(p)\) of Colin's rolls with a total below \(p\):

$$L(p)=\sum_{c\lt p}B(c),\qquad W=\sum_{p=9}^{36}A(p)\,L(p).$$

The draws, \(A(p)\,B(p)\) outcomes for each \(p\), are left out because the inequality is strict. The programs do not form \(L(p)\): they add \(A(p)\,B(c)\) for every pair with \(p\gt c\), which gives the same sum.

7. Worked example: three dice against two

Three four-sided dice against two six-sided dice is the real game with a third of the dice, and again both players can reach the same maximum, \(12\). With \(A=N_{3,4}\) and \(B=N_{2,6}\) from Section 3, the numbers \(L(p)\) for \(p=3,\dots,12\) are \(1,3,6,10,15,21,26,30,33,35\), and

$$\begin{aligned}W&=1\cdot1+3\cdot3+6\cdot6+10\cdot10\\&\quad+12\cdot15+12\cdot21+10\cdot26\\&\quad+6\cdot30+3\cdot33+1\cdot35=1152\end{aligned}$$

of the \(4^3\cdot6^2=2304\) outcomes, so Peter wins with probability exactly \(1/2\). The draws add up to \(2+9+24+50+72\)\({}+60+40+18+6+1\)\({}=282\), so Colin wins in the other \(870\) outcomes. A listing of all \(2304\) outcomes confirms the three counts.

8. Why the example gives exactly one half

Let \(X\) and \(Y\) be the two totals and \(Z=X-Y\). Turning each face \(f\) of a four-sided die into \(5-f\) and of a six-sided die into \(7-f\) maps outcomes one to one. In the example it sends \(X\) to \(15-X\) and \(Y\) to \(14-Y\), hence \(Z\) to \(1-Z\), so it matches Peter's wins, \(Z\ge1\), with the outcomes where \(1-Z\ge1\), that is \(Z\le0\); as \(Z\) is an integer, these are all the others. In the real game it sends \(Z\) to \((45-X)-(42-Y)=3-Z\) and matches the outcomes with \(Z\ge2\) with those with \(Z\le1\). Each kind is again half of all outcomes, and adding the case \(Z=1\) gives

$$\Pr(Z\ge1)=\tfrac12+\Pr(Z=1).$$

Since \(\Pr(Z=1)\) still needs both tables, this identity checks the computation rather than replacing it.

9. Exact counts and seven correct decimals

All counts are integers, and every partial sum formed in the computation is at most \(\Omega\lt2^{53}\). A double has a 53-bit significand, so it holds every integer up to \(2^{53}\) exactly, and in IEEE 754 arithmetic a division is correctly rounded. ^[7] The sums are therefore exact, and the computed quotient differs from \(W/\Omega\) by less than \(10^{-15}\). This matters only if \(W/\Omega\) lies very close to a midpoint between consecutive multiples of \(10^{-7}\), which integers alone can rule out. Write

$$10^7\,W=Q\,\Omega+R,\qquad 0\le R\lt\Omega.$$

The nearest midpoint is \((Q+\tfrac12)\cdot10^{-7}\), at distance \(|2R-\Omega|/(2\cdot10^7\,\Omega)\) from \(W/\Omega\). For the real game the test \(5\,|2R-\Omega|\gt\Omega\) holds, so this distance exceeds \(10^{-8}\), and the seven printed decimals are those of the exact probability, correctly rounded.

How the Code Works

The C++ program ^[8] keeps the parameters, by default \(9\), \(4\), \(6\) and \(6\), and a checkpoint switch in the struct Options. parse_arguments accepts --skip-checkpoints and the options --pete-dice=, --pete-sides=, --colin-dice=, --colin-sides=, whose digits parse_int_after_prefix reads into an int without an overflow check; on anything else, or on fewer than one die or two sides, the program stops with exit code \(1\). Unless switched off, run_checkpoints requires win_probability(1, 4, 1, 6) to lie within \(10^{-15}\) of \(0.25\), the game of Section 1; otherwise the exit code is \(2\).

distribution(dice, sides) implements Section 3 with a std::vector<long double> named dp of dice * sides + 1 entries, starting from dp[0] = 1. For each die it fills a fresh vector next, adding every nonzero count dp[sum] to next[sum + face] for face from \(1\) to sides; then next replaces dp. Before die \(i+1\) the nonzero counts lie at the totals \(i\) to \(is\), so no index leaves the vector. win_probability builds both tables, adds pete[p] * colin[c] for every pair of totals with nonzero counts to total, and also to wins when p > c, and returns wins / total, which is \(W/\Omega\) because total ends at \(\Omega\). main prints it as a double with std::fixed and std::setprecision(7).

The Python and Java programs fix the parameters at \((9,4)\) and \((6,6)\), have no options or checkpoint, and test s + f against the array length before each addition, a test that never fails. C++ counts in long double, at least as precise as double, ^[7] Java in double and Python in exact integers, so for this game every count and sum is exact in all three, and the only rounding is the final division and, in C++, the conversion to double. Python prints with f"{wins/total:.7f}" and Java with System.out.printf("%.7f%n", ...), which formats in the default locale; ^[9] under a locale with a decimal comma, such as German, Java therefore prints a comma instead of the point.

Complexity and Verification

For \(n\) dice with \(s\) sides, distribution makes \(n\) passes over \(ns+1\) totals, and pass \(i=0,\dots,n-1\) makes \(s\) additions for each of its \(i(s-1)+1\) nonzero counts: \(s\bigl(n+(s-1)n(n-1)/2\bigr)\) additions, \(468\) for Peter and \(486\) for Colin. The final double loop multiplies the \(28\cdot31=868\) pairs of nonzero counts, so a few thousand operations replace the \(1.2\cdot10^{10}\) outcomes of Section 2. In general, with \(m\) dice of \(r\) sides for Colin and each arithmetic operation counted as one step, the program takes \(O(n^2s^2+m^2r^2+nmsr)\) steps and \(O(ns+mr)\) memory.

The C++ checkpoint is the game of Section 1. The following checks were made for this article and are not part of the published solutions. Enumerating all \(262144\) rolls of Peter and \(46656\) of Colin reproduces the tables of Section 5, and the formula of Section 4 agrees with them. Listing all outcomes of five small games, among them those of Sections 1 and 7, confirms their wins, draws and losses. For all \(625\) games with one to five dice of two to six sides per player, the C++ program printed the exact probability rounded to seven decimals, or one of the two nearest values in the \(14\) games where it lies exactly halfway; modified copies of the Python and Java programs give \(0.5000000\) for Section 7. For the real game, exact rational arithmetic confirms the identity of Section 8 and the test of Section 9, and all three programs print the same seven decimals, \(W/\Omega\) correctly rounded.

Footnotes and References

The references below supply the background facts used above; the recurrence, the examples, the symmetry identity and the operation counts are derived here.

1. Project Euler 205 — Dice Game. The official statement gives Peter nine four-sided and Colin six six-sided dice, lets the higher total win, with equal totals a draw, and asks for the probability that Peter wins, to seven decimal places.
2. Wikipedia — Classical definition of probability. Laplace defined the probability of an event as the ratio of the number of cases favourable to it to the number of all cases, when these are equally possible.
3. Wikipedia — Rule of product. If there are a ways of doing one thing and b ways of doing another, there are a · b ways of doing both.
4. Wikipedia — Convolution of probability distributions. The distribution of a sum of independent random variables is the convolution of their distributions; for integer-valued X and Y, P(X + Y = z) = Σₖ P(X = k) P(Y = z − k).
5. Wikipedia — Dynamic programming. Dynamic programming breaks a problem into simpler subproblems, solves each once and builds larger solutions from smaller ones.
6. MathWorld — Dice. The number of ways to roll p points with n s-sided dice is the coefficient of xᵖ in (x + x² + ⋯ + xˢ)ⁿ; expanding it gives the alternating sum of Section 4, after Uspensky (1937).
7. Wikipedia — Double-precision floating-point format. The binary64 format has a 53-bit significand and represents every integer from −2⁵³ to 2⁵³ exactly. IEEE 754 operations are correctly rounded unless specified otherwise, and the C++ working draft, [basic.fundamental], makes long double at least as precise as double.
8. C++ — Euler205.cpp. The linked immutable revision contains parse_arguments, distribution, win_probability and run_checkpoints. It is the implementation record for this article.
9. Java — java.io.PrintStream. printf behaves like format, which always uses the default FORMAT locale; java.util.Formatter then substitutes a locale-specific decimal separator.