(Double Shutter) Shut The Box Winning Strategy
Home -->
Programming Projects -->
Shut The Box (Winning Strategy)
For family fun my dad got the game "Double Shutter: Shut The Super Box"
(see pictures below).
I thought I would be a smarty-pants and compute an optimal
strategy for the game using a computer so that is what I did!
This game is a variant of the traditional "Shut The Box" game, where
this version uses two rows of tiles (9 tiles in a row) instead of one.
Durango Bill
already performed an analysis of the optimal strategy for
various modifications of the original game,
but it looks like the double-shutter variation is new teritory!
For a description of the original game, see
Wikipedia.
Here are the rules of the game:
Each turn the player rolls two 6 sided die and the player must
"shut" enough standing tiles so that the sum of the values of the
tiles shut equals the sum of the values on the two die just rolled.
The goal of the game is to get a low score.
If the player cannot do this, the game is over and his score is the
sum of the values of the tiles in the back row plus twice
the values of the tiles in the front row.
As an exception, a player may choose to instead roll one die if
the sum of the values of the exposed tiles is less than or equal
to 6 (a player would be crazy not to make this choice if he is able to).
Consider the above picture to the left. If the player rolls 10, he can
shut the left-most 1 tile and then shut the 9 tile behind it and this
counts as a valid move.
Suppose that the object of playing the game is to get the least
expected value.
Here is how to compute a winning strategy for the game:
Let a board be defined as a valid
configuration of tiles in a box as depicted by the pictures above.
If b is a board, let rank(b) denote the number of tiles standing in b.
Let adj(b,r) denote the set of all boards that could be reached (in one move) from
b given that r has been roled.
Let prob(r) denote the probability or rolling r (let us ignore the
issue of rolling two versus one die in this discussion).
Let E(b) denote the expected score of the game given that the board
is currently b.
Let score(b) denote
twice the sum of the values on the standing tiles in the front row
plus the sum of the values on the standing tiles in the back row.
We have the recursive relationship:
E(b) = sum (from r = 2 to 12) of prob(r) * A(b,r)
A(b,r) = min { E(b') | b' in adj(b) } if adj(b) is non-empty
A(b,r) = score(b) otherwise
The key is that if b' in adj(b) then rank(b') < rank(b).
This means that E(b) can be computed using dynamic programming:
computing the expected values for all boards of rank R
given the expected values of all boards of rank < R.
The only anoying part is enumerating all boards of rank R and
determining adj(b) for a given b. The (Haskell) source code
used to brute force this program can be found
here and the
computed optimal strategy (board expected values) can be found
here.
Notice how a table of computed expected values along with
a way to compute adj is all that is needed to play the
game optimally.
It turns out that the expected value for the game
(playing optimally) is "19.427".
If instead the point of the game is not to get the least expected
value but to get a score of 0 with the highest probability, then
we would want to use a different (all or nothing) strategy!
Indeed, all we do is change the third line in the above recursive
relationship to the following:
A(b,r) = (0 if score(b) == 0 and 1 otherwise) otherwise
In this case, the expected value is just the probability
of not getting a score of 0 when playing optimally.
The computed board expected values for this can be found here
here.
It turns out that the probability for not getting a score of 0
(playing optimally) is "0.923".
More generally, here is a graph showing the probability p(n) of
not getting a score <= n given an optimal strategy for
trying to do so:
Exact values for p(n) for n = 1,...,20 can be found
here. It is a bit anoying that
the optimal strategy does not make winning much more likley.
A comparison of the optimal strategy with the strategy of
making moves randomly would be interesting for future work.