So I Felt Like Solving Zombie Dice

Sun, 09/06/2013 - 02:05 — root

There is a party game called Zombie Dice where you roll dice and try to get as many points as you can without losing all of your health and dying. Green dice make points more likely than death, red dice make death more likely than points and yellow dice are neutral. I played it with some friends awhile ago and realized that it was probably simple enough for me to come up with the optimal strategy.

Just about every game is solvable in principle, but it is very easy to make a game that would take longer than the age of the universe to solve. The prototypical solved game is tic-tac-toe. The prototypical game that is still a long way from being solved is chess. An xkcd comic lists a bunch of solved games so let's see how we can add Zombie Dice to this list.

Now the rules of Zombie Dice are that you have a cup containing 13 dice and on your turn, you randomly choose dice to roll. You always roll three at a time and you can keep doing this until you die, run out of dice or choose to pass the cup on to the next person. There are three icons that can be rolled:

Brains: Each brain is a point. The possibility of more brains would encourage a person to keep rolling. Green dice have three, yellow have two and red have one.
Shotguns: Shotgun blasts lower your health by one, and if three of them are encountered in a turn, the turn ends with 0 points. The possibility of more shotguns would discourage one from continuing to roll. Green dice have one, yellow have two and red have three.
Walkers: Denoted by footprints, this result means that the die will be included in the next roll if you choose to roll again. Instead of drawing three new dice, you draw three minus the number of walkers from the last roll. All dice have two of these.

The cup begins with 6 green dice, 4 yellow dice and 3 red dice. The first player to get 13 points wins. This can be done in one turn but the probability is about one in a million. The need for some basic strategy is clear. You could end up with three green dice for your first roll and then roll them and get a lot of brains, which is good. But this makes the second roll more risky. The fact that three green dice have been used up means that the next dice are more likely to be yellow and red which increase your chances of being shot. This uncertainty about whether to roll is part of the fun of the game. It can be surmounted by using a formula for the expected number of points $E$ . When deciding whether to continue, a player should roll if $E > n$ and cash in if $E < n$ .

The game state is a function of a few different variables. First, you need to know how many green dice are left $N_g$ , how many yellow dice are left $N_y$ and how many red dice are left $N_r$ . You also need to know your health $h$ and the number of points you already have $n$ . Also dictating the state of the game are the number of walkers you have and the colours of the dice on which they appear. The initial condition is $N_g = 6$ , $N_y = 4$ , $N_r = 3$ , $h = 3$ and $n = 0$ with no walkers.

If a player rolls three walkers, the following roll would just be a re-roll so in this case

$ E = E_{w_1, w_2, w_3} (n, h) $

Rolling two walkers on the other hand, requires the player to draw one die. This can either be a green, a yellow or a red die so there are three expectation values to consider. Moreover they must be weighted by the probability that the given die will be drawn so the overall expected number of points is

$\begin{align*} E &= P(g|N_g, N_y, N_r) E_{w_1, w_2, g} (n, h) + P(y|N_g, N_y, N_r) E_{w_1, w_2, y} (n, h) + P(r|N_g, N_y, N_r) E_{w_1, w_2, r} (n, h) \\ &= \frac{1}{N_g + N_y + N_r} \,\, \left [ N_g E_{w_1, w_2, g} (n, h) + N_y E_{w_1, w_2, y} (n, h) + N_r E_{w_1, w_2, r} (n, h) \right ] \end{align*}$

where in the last step I have written in the expressions for how likely it is that a given die will be drawn. With one walker, there are two dice to be drawn leading to a weighted sum of six conditional expectations:

$\begin{align*} E &= P(g, g|N_g, N_y, N_r) E_{w, g, g} (n, h) + P(y, y|N_g, N_y, N_r) E_{w, y, y} (n, h) + P(r, r|N_g, N_y, N_r) E_{w, r, r} (n, h) \\ &+ P(g, y|N_g, N_y, N_r) E_{w, g, y} (n, h) + P(g, r|N_g, N_y, N_r) E_{w, g, r} (n, h) + P(y, r|N_g, N_y, N_r) E_{w, y, r} (n, h) \\ &= \frac{1}{\binom{N_g + N_y + N_r}{2}} \, \left [ \binom{N_g}{2} E_{w, g, g} (n, h) + \binom{N_y}{2} E_{w, y, y} (n, h) + \binom{N_r}{2} E_{w, r, r} (n, h) \right \none \\ &\left \none + N_g N_y E_{w, g, y} (n, h) + N_g N_r E_{w, g, r} (n, h) + N_y N_r E_{w, y, r} (n, h) \right ] \end{align*}$

With no walkers and no dice pre-determined, we get ten terms in the sum:

$\begin{align*} E &= P(g, g, g|N_g, N_y, N_r) E_{g, g, g} (n, h) + P(g, g, y|N_g, N_y, N_r) E_{g, g, y} (n, h) + P(g, g, r|N_g, N_y, N_r) E_{g, g, r} (n, h) \\ &+ P(y, y, y|N_g, N_y, N_r) E_{y, y, y} (n, h) + P(y, y, g|N_g, N_y, N_r) E_{y, y, g} (n, h) + P(y, y, r|N_g, N_y, N_r) E_{y, y, r} (n, h) \\ &+ P(r, r, r|N_g, N_y, N_r) E_{r, r, r} (n, h) + P(r, r, g|N_g, N_y, N_r) E_{r, r, g} (n, h) + P(r, r, y|N_g, N_y, N_r) E_{r, r, y} (n, h) \\ &+ P(g, y, r|N_g, N_y, N_r) E_{g, y, r} (n, h) \\ &= \frac{1}{\binom{N_g + N_y + N_r}{3}} \left [ \binom{N_g}{3} E_{g, g, g} (n, h) + N_y \binom{N_g}{2} E_{g, g, y} (n, h) + N_r \binom{N_g}{2} E_{g, g, r} (n, h) \right \none \\ &\left \none + \binom{N_y}{3} E_{y, y, y} (n, h) + N_g \binom{N_y}{2} E_{y, y, g} (n, h) + N_r \binom{N_y}{2} E_{y, y, r} (n, h) \right \none \\ &\left \none + \binom{N_r}{3} E_{r, r, r} (n, h) + N_g \binom{N_r}{2} E_{r, r, g} (n, h) + N_y \binom{N_r}{2} E_{r, r, y} (n, h) \right \none \\ &\left \none + N_g N_y N_r E_{g, y, r} (n, h) \right ] \end{align*}$

Once we know the ten expected values, these four expressions allow us to plug in the game state and always know whether it makes sense to keep betting or fold. The expectations are tedious to calculate but I didn't come this far to back down now! Here is a list of them:

$\begin{align*} E_{g, g, g} (n, h) &= \left ( -\frac{5}{36} h^2 + \frac{55}{72} h - \frac{5}{108} \right ) n + \left ( -\frac{3}{16} h^2 + \frac{47}{48} h - \frac{1}{4} \right ) \\ E_{g, g, y} (n, h) &= \left ( -\frac{67}{432} h^2 + \frac{127}{144} h - \frac{19}{72} \right ) n + \left ( -\frac{5}{54} h^2 + \frac{239}{216} h - \frac{1}{9} \right ) \\ E_{g, g, r} (n, h) &= \left ( -\frac{1}{6} h^2 + \frac{71}{72} h - \frac{17}{36} \right ) n + \left ( -\frac{11}{48} h^2 + \frac{533}{432} h - \frac{17}{36} \right ) \\ E_{y, y, y} (n, h) &= \left ( -\frac{1}{9} h^2 + \frac{7}{9} h - \frac{10}{27} \right ) n + \left ( -\frac{1}{6} h^2 + \frac{17}{18} h - \frac{1}{3} \right ) \\ E_{y, y, g} (n, h) &= \left ( -\frac{5}{36} h^2 + \frac{31}{36} h - \frac{19}{54} \right ) n + \left ( -\frac{7}{36} h^2 + \frac{115}{108} h - \frac{5}{18} \right ) \\ E_{y, y, r} (n, h) &= \left ( -\frac{1}{12} h^2 + \frac{25}{36} h - \frac{7}{18} \right ) n + \left ( -\frac{19}{108} h^2 + \frac{35}{36} h - \frac{1}{2} \right ) \\ E_{r, r, r} (n, h) &= \left ( \frac{3}{8} h - \frac{1}{4} \right ) n + \left ( -\frac{1}{16} h^2 + \frac{7}{16} h - \frac{1}{4} \right ) \\ E_{r, r, g} (n, h) &= \left ( -\frac{1}{12} h^2 + \frac{17}{24} h - \frac{5}{12} \right ) n + \left ( -\frac{19}{144} h^2 + \frac{13}{16} h - \frac{5}{12} \right ) \\ E_{r, r, y} (n, h) &= \left ( -\frac{1}{24} h^2 + \frac{13}{24} h - \frac{1}{3} \right ) n + \left ( -\frac{7}{72} h^2 + \frac{5}{8} h - \frac{1}{3} \right ) \\ E_{g, y, r} (n, h) &= \left ( -\frac{1}{8} h^2 + \frac{61}{72} h - \frac{4}{9} \right ) n + \left ( -\frac{13}{72} h^2 + \frac{221}{216} h - \frac{4}{9} \right ) \end{align*}$

A zombie bee card from the game Munchkin.

As an example I will repeat one of the calculations here. How about $E_{r, r, r} (n, h)$ , the one with three red dice. Whenever you begin a roll with $n$ points, there are five possibilities for the number of points you will have at the end of the roll: $0$ , $n$ , $n+1$ , $n+2$ or $n+3$ . One definite thing we can say is that $P(n+3|h) = \frac{1}{216}$ because in order to get three points, we need to roll three brains in a row. Every other probability depends on what the health is. First, let's solve for them when the player has three health.

$ P(0|h=3) = \left ( \frac{1}{2} \right )^3 = \frac{1}{8} $

because in order to die and lose all your points, you would have to roll three shotgun blasts in a row. In order to gain or lose no points, you have to roll three non-brains without dying.

$ P(n|h=3) = \left ( \frac{5}{6} \right )^3 - \frac{1}{8} = \frac{49}{108} $

The first product is the probability for rolling three non-brains in a row. This counts the possibility of three shotguns however which is why we subtract one eighth.

$ P(n+1|h=3) = 3 \left ( \frac{1}{6} \right ) \left ( \frac{5}{6} \right )^2 = \frac{25}{72} $

If we want one additional point, we are rolling one brain and two non-brains. We multiply by three because any one of the three red dice could've been the one that was a brain.

$ P(n+2|h=3) = 3 \left ( \frac{1}{6} \right )^2 \left ( \frac{5}{6} \right ) = \frac{5}{72} $

For two additional points, we do the same thing except it's two brains and one non-brain. Plugging these into the formula for expected value,

$\begin{align*} E_{r, r, r} (n, 3) &= n \frac{49}{108} + (n+1) \frac{25}{72} + (n+2) \frac{5}{72} + (n+3) \frac{1}{216} \\ &= \frac{7}{8}n + \frac{1}{2} \end{align*}$

Moving on to two health,

$ P(0|h=2) = \left ( \frac{1}{2} \right )^2 + 3 \left ( \frac{1}{2} \right )^3 = \frac{1}{2} $

we get an extra term in the probability of dying compared to three health. We could roll the three shotgun outcome from our last calculation but we also need to count the three ways of rolling two shotguns and one non-shotgun.

$ P(n|h=2) = \left ( \frac{1}{3} \right )^3 + 3 \left ( \frac{1}{3} \right )^2 \left ( \frac{1}{2} \right ) = \frac{11}{54} $

Here, the first term is the probability of three walkers and the second is the probability of two walkers and a shotgun.

$ P(n+1|h=2) = 3 \left ( \frac{1}{6} \right ) \left ( \frac{1}{3} \right )^2 + 6 \left ( \frac{1}{2} \right ) \left ( \frac{1}{3} \right ) \left ( \frac{1}{6} \right ) = \frac{2}{9} $

This is brain-walker-walker plus brain-walker-shotgun. The six is there because there are six permutations we can apply to the three different values.

$ P(n+2|h=2) = 3 \left ( \frac{1}{6} \right )^2 \left ( \frac{1}{3} \right ) + 3 \left ( \frac{1}{6} \right )^2 \left ( \frac{1}{2} \right ) = \frac{5}{72} $

This one is brain-brain-walker plus brain-brain-shotgun. Now we can plug these in again to get

$\begin{align*} E_{r, r, r} (n, 2) &= n \frac{11}{54} + (n+1) \frac{2}{9} + (n+2) \frac{5}{72} + (n+3) \frac{1}{216} \\ &= \frac{1}{2}n + \frac{3}{8} \end{align*}$

Notice that this roll puts you at a disadvantage unless you have zero points and nothing to lose. This is in contrast to the same roll at three health where you need to have four points before the roll becomes too dangerous. Now to deal with the case of one health,

$ P(0|h=1) = 1-\left ( \frac{1}{2} \right )^3 = \frac{7}{8} $

Everything but three non-shotguns leads to death so we simply subtract this probability from unity.

$ P(n|h=1) = \left ( \frac{1}{3} \right )^3 = \frac{1}{27} $

For this one, a single shotgun would kill us and a single brain would give us a point, so it's walker-walker-walker.

$ P(n+1|h=1) = 3\left ( \frac{1}{6} \right ) \left ( \frac{1}{3} \right )^2 = \frac{1}{18} $

This has to be brain-walker-walker for the same reason.

$ P(n+2|h=1) = 3\left ( \frac{1}{6} \right )^2 \left ( \frac{1}{3} \right ) = \frac{1}{36} $

Similarly, this is brain-brain-walker. Now to plug in these numbers one more time,

$\begin{align*} E_{r, r, r} (n, 1) &= n \frac{1}{27} + (n+1) \frac{1}{18} + (n+2) \frac{1}{36} + (n+3) \frac{1}{216} \\ &= \frac{1}{8}n + \frac{1}{8} \end{align*}$

Now we have three equations but we want to combine them into one that looks like $E_{r, r, r} (n, h) = f(h)n + g(h)$ . This is just a cheap trick so we will choose quadratics $f(h) = ah^2 + bh + c$ , $g(h) = xh^2 + yh + z$ . The requirements $f(3) = \frac{7}{8}$ , $f(2) = \frac{1}{2}$ , $f(1) = \frac{1}{8}$ , $g(3) = \frac{1}{2}$ , $g(2) = \frac{3}{8}$ and $g(1) = \frac{1}{8}$ reduce this to a system of linear equations. Solving them, we get $(a, b, c) = (0, \frac{3}{8}, -\frac{1}{4})$ and $(x, y, z) = (-\frac{1}{16}, \frac{7}{16}, -\frac{1}{4})$ . Of the ten tedious functions of $n$ and $h$ , this gives us the seventh one. The others are all obtained in similar ways.

Clearly by taking your first roll, you can only gain points or stay the same. Subsequent rolls only happen if you stand to benefit from them. Therefore a turn will give a player more than zero points on average. In other words, the game will almost surely end. A harder calculation would tell you how many turns this is likely to take. This is the same as asking what the expectation is for the number of points that can be accumulated in a single turn if this optimal strategy is used from start to finish. In fact one could get the entire distribution for the number of points accumulated. This is mainly hard because of the walkers. The events of rolling a certain outcome and choosing a certain set of dice for the next roll are not independent. Maybe we should simulate this. Sorry for switching between first, second and third person so often.

Tags:

fun calculations

tuning performance

Main menu

Navigation

You are here

So I Felt Like Solving Zombie Dice