The Universe of Disco

A simple dice-throwing game that seems hard to play

I ran into a fun math problem yesterday, easy to ask, easy to understand, but somewhat open-ended and seems to produce fairly complex behavior. It might be a good problem for a bright high school student to tinker with.

Consider the following one-player game. You start with a total of n points. On each turn, you choose to throw either a four-, six-, or eight-sided die, and then subtract the number thrown from your point total. The game continues until your total reaches zero (and you win) or goes below zero (and you lose).

This game seems surprisingly difficult to analyze. The computer analysis is quite easy, but what I mean is, if someone comes to you offering to pay you a dollar if you can win starting with !!n=9!! points, and it would be spoilsportish to say “just wait here for half an hour while I write this computer program”, what's your good move?

Is there even a way to make an educated guess, short of doing a full analysis? The !!n≤4!! strategy is obvious, but even for !!n=5!! you need to start calculating: rolling the d4 is safe. Rolling the d6 gives you a chance of wiping out, but also a chance of winning instantly; is that an improvement? (Spoiler: it is, quite substantially so! Your chance of winning increases from !!36\%!! to !!40.7\%!!.)

With the game as described, and optimal play, the probability of winning approaches !!45.66\%!! as the number of points increases, and the strategy is not simple: the best strategy for !!n≤20!! uses the d4 in 13 cases, the d6 in 4 cases, and the d8 in 3 cases:

$$\begin{array}{rcl} n & \text{Best play} & \text{Win %} \\ \hline 1 & 4\quad & 25.00\% \\ 2 & 4\quad & 31.25 \\ 3 & 4\quad & 39.06 \\ 4 & 4\quad & 48.83 \\ \hline 5 & 6 & 40.69\% \\ 6 & 6 & 47.47 \\ 7 & 4\quad & 44.01 \\ 8 & \quad8 & 47.04 \\ \hline 9 & 4\quad & 44.80\% \\ 10 & 4\quad & 45.83 \\ 11 & 4\quad & 45.42 \\ 12 & 4\quad & 45.77 \\ \hline 13 & 6 & 45.48 \% \\ 14 & \quad8 & 45.73 \\ 15 & 4\quad & 45.60 \\ 16 & \quad8 & 45.71 \\ \hline 17 & 4\quad & 45.63 \% \\ 18 & 4\quad & 45.67 \\ 19 & 4\quad & 45.65 \\ 20 & 6 & 45.67 \end{array} $$

It seems fairly clear (and not hard to prove) that when the die with fewest sides has !!d!! sides, the good numbers of points are multiples of !!d!!, with !!kd+1!! somewhat worse, and then !!kd+2, kd+3, \ldots!! generally better and better to the next peak at !!kd+d!!. But there are exceptions: even if !!d!! is not the smallest die, if you have a !!d!!-sided die, it is good to have !!d!! points, and when you do you should roll the !!d!!-sided die.

I did get a little more insight after making the chart above and seeing the 4-periodicity. In a comment on my Math SE post I observed:

There is a way to see quickly that the d4 is better for !!n=7!!. !!n=1!! is the worst possible position. !!n=2,3,!! and !!4!! are increasingly good; !!4!! is best because you can't lose and you might win outright. After that !!5!! is bad again, but not as bad as !!1!!, with !!6,7,8!! increasingly good. The pattern continues this way, with !!4k−3,4k−2,4k−1,4k!! being increasingly good, and then !!4k+1!! being worse again but better than !!4k−3!!. For !!n=7!!, the d6 allows one to land on !!\{1,2,3,4,5,6\}!!, and the d4 on !!\{3,4,5,6\}!!. But !!1!! is worse than !!5!! and !!2!! is worse than !!6!!, so prefer the d4.

The d4-d6-d8 case is unusually confusing, because for example it's not clear whether from 12 points you should throw d4, hoping to land on 8, or d6, hoping to land on 6. (I haven't checked but I imagine the two strategies perform almost equally well; similarly it probably doesn't matter much if you throw the d4 or the d6 first from !!n=10!!.)

That the d6 is best for !!n=13!! is very surprising to me.

Why !!45.66\%!!? I don't know. With only one die, the winning probability for large !!n!! converges to !!\frac2{n+1}!! which I imagine is a fairly straightforward calculation (but I have not done it). For more than one die, it seems much harder.

Is there a way to estimate the winning probability for large !!n!!, given the list of dice? Actually yes, a little bit: the probability of winning with just a d4 is !!\frac 25!!, and the d6 and d8 can't hurt, so we know the chance of winning with all three dice available will be somewhat more than !!40\%!!, as it is. The value of larger dice falls off rapidly with the number of sides, so for example with d4+d6 the chance of winning increases from !!40\%!! to almost !!45\%!!, and adding the d8 only nudges this up to !!45.66\%!!.

The probability of winning with a d2 is !!\frac 23!!, and if you have a d3 also the probability goes up to !!\frac 34!!, which seems simple enough, but if you add a d4 instead of the d3 instead it goes to !!68.965\%!!, whatever that is. And Dfan Schmidt tells me that d3 + d4 converges to !!\frac{512}{891}!!.

I wrote it up for Math StackExchange but nobody has replied yet.

Here's Python code to calculate the values. Enjoy.

[ Addendum: Michael Lugo points out that the d2+d4 probability (“!!68.965\%!!, whatever that is”) is simply !!\frac{20}{29}!!, and gives some other similar results. One is that d3+d4+d5 has a winning probability of !!\frac{16}{27}!!; the small denominator is surprising. ]

[Other articles in category /math] permanent link