Shut-The-Box

This is a French game for two or more players. You could buy the thing at a shop, which consists of a purpose built box and two dices, but the game can be played with a pen and a piece of paper (you still need two dices).

Start with numbers from 1 to 9. Roll the two dices and let D be the sum of the face values. You can either cross out D if it is available, or cross out two numbers of which the sum is D.

For example, if your first roll gives 3 and 5, then you can cross out 8, or 1 & 7, or 2 & 6, or 3 & 5.

If you cross out all the numbers, you win; if you cannot cross out any more numbers while there is at least one left, you lose. This is not quite the same rule as used in the real game but we shall stick with it for the discussion.

What is the probability of winning, assuming the best choice is always made?

The program that calculates the answer: box.c (9K).
The output from the program: box.txt (71K).

Answer:

With the best strategy, the probability of winning, p, is 0.05; if you make choices randomly, p = 0.025; if you always pick the worst choice, p = 0.01. It is a bit disappointing to see that even the best strategy does not improve the probability a lot, but the game is tough in the first place!

Sample output:

8 7 6 5 2 <-- 7 = 8 6 5 2 (0.045410)
8 7 6 5 2 <-- 8 = 7 6 5 2 (0.061257)
8 7 6 5 2 *** p = 0.0372919

The output says if the dices give a total of 7, and you have {8, 7, 6, 5, 2}, then the best strategy is to cross out 7 (rather than 5 and 2) to give a winning probability of 0.045. If the total is 8, then cross out 8 to give p = 0.06. The overall probability of winning at this position is 0.037.

Discussion:

This game is a finite game and is completely solvable. The computer program works backwards: when there is only one number left, the probability of winning is trivial. When there are two numbers left, we either cross them out in one go (with a known probability), or cross out one of them and leave the game in a one-number state of which p has already been calculated. If there is a choice, we choose the ‘branch’ with highest p. It is really as simple as that.