Analysis of Shut the Box

Once again, motivation for this post comes from God Plays Dice, where I saw Vince Knight’s interesting blog post describing some analysis of the pub game Shut the Box.  (I remember playing this game in college, usually as a means of determining who paid for the next round; we called the game “Clacker.”)  The basic game is very simple: start with a set of nine tiles labeled 1 through 9, and repeatedly roll two dice, each time “covering” some subset of tiles whose sum exactly equals the sum of the dice rolled.  Your turn ends when you can’t move; i.e., when no subset of remaining uncovered tiles has the required sum.  Your final score is the sum of tiles left uncovered; e.g., if you cover all nine tiles– we called this clacking— then your score is zero.

Bill Butler (also of past analysis of Monopoly fame) has analyzed the single-player “all-or-nothing” version of the game, computing the optimal strategy that maximizes the probability of clacking (covering all of the tiles).  Knight’s analysis, on the other hand, involves Monte Carlo simulation of thousands of games played using various strategies that are easy to describe, but not necessarily optimal in any sense (e.g., given a choice of multiple subsets of tiles with the same dice roll sum, cover the subset with the fewest elements).

I think the game gets much more interesting– and more complex– with two players, where each player takes a turn, and the player with the lowest score wins, say, one dollar from the loser.  (This is also how I remember actually playing.)  Is this a fair game?  If not, which player has the advantage?  There are several common rule variations, such as allowing a player to roll just one die instead of two dice in some situations.  Among these different games with slightly different rules, which version is “best” in the sense that it is fairest?

Following is Mathematica code that answers these questions.  First, we compute the playing strategy and corresponding expected value for each of the possible subsets of uncovered tiles that a player may be confronted with.  The only interesting thing to note here is that we must be sure to visit the subsets in (any topological sort of) inclusion order.  This guarantees that, when computing strategy for a subset, which depends on the expected values of smaller subsets reached by covering some tiles, those expected values will have already been computed.

optimizeStrategy[utility_, roll1_] :=
 Scan[
  chooseDice[#, rollValues[#, utility[#]], roll1[#]] &,
  Subsets[Range[9]] // Sort
  ]

To compute strategy for a particular subset of uncovered tiles, we consider each possible roll of the dice, which may have a total ranging from 1 through 12.  (Remember, we anticipate allowing a single die roll in some situations.)  For each roll, we select among all valid moves the one with the largest expected value… or if there are no valid moves and the roll ends the turn, we are stuck with the “utility” of our current subset (more on this later).

rollValues[subset_, utility_] :=
 Module[
  {t = Total[subset], roll, moves, value, move},
  Table[
   moves = Select[Subsets[subset], t - roll == Total[#] &];
   {value, move} = If[moves === {},
     {utility, subset},
     Map[{expectedValue[#], #} &, moves] // Sort // Last
     ];
   moveStrategy[subset, roll] = move;
   moveForced[subset, roll] = (Length[moves] < 2);
   value,
   {roll, 12}
   ]
  ]

Once we know the expected values of each possible dice roll, we can determine whether it is better to roll one or two dice by comparing the corresponding linear combinations of those expected values, weighted by the distribution of roll totals for one or two dice.

chooseDice[subset_, values_, roll1_] :=
 {expectedValue[subset], rollStrategy[subset]} = {
     {values[[Range[2, 12]]].(6 - Abs[Range[2, 12] - 7])/36, 2},
     If[roll1,
      {values[[Range[6]]].Table[1/6, {6}], 1},
      {-3, 0}
      ]
     } // Sort // Last

Finally, we put it all together by evaluating each player’s strategy in turn.  The trick is that we must evaluate the second player’s strategy first, since it depends on the outcome of the first player’s turn, which may be any score from 0 (a clack) to 45.  For each of these cases, the parameterized “utility” function for the value of the second player’s turn is essentially just a win (+1) or loss (-1) depending on whether his final score is less or greater, respectively, than the first player’s score.  (The more complex expression below deals with some of the rule variations which will be explained shortly.)

Once we know all of the possible expected values for the second player, given the first player’s outcome, we can now compute the first player’s optimal strategy– and overall value of the game– by using the second player’s (negated) expected values as the utility function.

overallValue[roll1_, odds_, immediate_] :=
 (
  Do[
   optimizeStrategy[
    If[score1 === 0 || # === {}, odds, 1] * If[
       immediate && score1 === 0, -1, Sign[score1 - Total[#]]] &,
    roll1
    ];
   value2[score1] = expectedValue[Range[9]],
   {score1, 0, 45}
   ];
  optimizeStrategy[-value2[Total[#]] &, roll1];
  expectedValue[Range[9]]
  )

Using the above code, I evaluated 16 different versions of the game, corresponding to all possible combinations of the following common rule variations:

1. When may a player choose to roll a single die instead of two?  Two common variants allow rolling a single die if (a) the sum of remaining uncovered tiles is at most 6, or (b) the maximum of remaining uncovered tiles is at most 6 (i.e., 7, 8, and 9 are all covered).  In addition to these, I also considered always and never allowing the choice of rolling a single die.
2. If a player clacks (i.e., covers all nine tiles), does he receive double the initial stakes, so that the loser pays the winner $2 instead of $1?
3. If the first player clacks, does he immediately win the game, or is the second player allowed to take his turn in an attempt to tie?

The following table shows the results, indicating the first player’s expected value for each set of rule variations, sorted by absolute value of advantage.

Roll 1 die	Clack pays	Clack wins immediately	Player 1 EV (%)
never	1:1	yes	0.1071
always	1:1	yes	0.1721
max <= 6	1:1	yes	0.2980
sum <= 6	2:1	no	-0.3276
never	2:1	no	-0.3526
sum <= 6	1:1	no	-0.3900
never	1:1	no	-0.4012
max <= 6	2:1	no	-0.4772
sum <= 6	1:1	yes	0.5621
always	2:1	no	-0.5679
max <= 6	1:1	no	-0.6489
never	2:1	yes	0.6645
always	1:1	no	-0.7747
always	2:1	yes	1.3269
max <= 6	2:1	yes	1.4177
sum <= 6	2:1	yes	1.5767

There are a couple of interesting observations.  First, as might be expected, the first player has the advantage only when his clack wins immediately; otherwise the second player has the advantage of “knowing what he has to beat.”  Second, it seems that the fairest version of the game is (almost) the simplest one described in the first paragraph of this post: you always roll two dice, and the loser always pays the winner one dollar, with the only additional detail being that a clack by the first player wins immediately.