Shut the box in one of Flachau’s “libraries”

Shut The Box

Shut The Box

Last Christmas I was a few days in the skying resort Flachau in Austria to visit a friend. There I encountered a strange dice game, which I later learned to be “Shut the Box“.

The rules of the game are simple. You roll two dices and turn down numbers as long as you can. The sum of the numbers you turn down must equal the sum of your dices. For example, in the picture at the right, the only possibility is to turn down the 4. If at the next turn the player rolls 7, he can turn down either [7], or both [1] and [6]. If you can’t turn down any more numbers you are finished and your final score is the number shown. If the player in the picture had rolled 3, he could not go on and would score 14679. The player with the lowest score wins.

I played a variant of the game, where there is no winner, but the player with the highest score looses. He then has to pay every other player a coffee at the library we were playing at. Or something like that, I can’t remember the details…

Problem: How do you play the game in order to maximize the amount of free coffee you receive?

The whole long night, I was thinking about the proper strategy for this game. Obviously we are dealing with partitions of numbers here. Also, the probability of some numbers is higher than others (to roll 7 is much more likely than rolling 2). What we want to do, is to minimize the expected value of the final score. Even the smallest number with five digits is higher than the highest number with four digits, therefore trying to turn down high numbers is possibly a bad strategy. We want to turn down as many numbers as possible. The greedy strategy (turning down as much numbers as possible each time) however, is also obviously a bad one, because the low numbers are more valuable. If on the first turn we roll 6, turning down [6] is probably a better strategy than turning down [1],[2], and [3]. If we did the second, and rolled 2, or 3 any time after, we’d be done. Despite thinking about all of this, I could not find a satisfactory solution.

Therefore, when I returned home late at night from my library tour, I decided to write a program to find the optimal strategy. The only development environment I had installed on my laptop was Eclipse for Android. So, Java it was.

For the given problem size (only numbers from 1 to 9), it is easy for a computer to recursively enumerate the whole decision tree and always pick the move with the lowest expected score. The optimal decision tree is too big to print here, but we’ll see an example. Suppose You roll a 7 at the very beginning. The optimal strategy here is to just put down the 7. The probability to finish on the next dice roll stays zero, i.e., you still can cover every possible roll of the dices with the remaining numbers. If you keep playing optimally, your expected value when you roll 7 at the beginning is 1950. The following listing shows this as well as the optimal moves afterwards. (p_die is the probability to die after the current state, EV is the expected value of the current state).

                   [1, 2, 3, 4, 5, 6, 7, 8, 9, ], p_die: 0.000, EV: 14765.975
Dice 7 (0.166):    [1, 2, 3, 4, 5, 6,    8, 9, ], p_die: 0.000, EV:  1950.347
  Dice  2 (0.027): [1,    3, 4, 5, 6,    8, 9, ], p_die: 0.028, EV: 40935.389
  Dice  3 (0.055): [1, 2,    4, 5, 6,    8, 9, ], p_die: 0.000, EV:  2689.550
  Dice  4 (0.083): [1, 2, 3,    5, 6,    8, 9, ], p_die: 0.000, EV:  1842.870
  Dice  5 (0.111): [1, 2, 3, 4,    6,    8, 9, ], p_die: 0.000, EV:   580.920
  Dice  6 (0.138): [1, 2, 3, 4, 5,       8, 9, ], p_die: 0.000, EV:   574.532
  Dice  7 (0.166): [   2, 3, 4, 5,       8, 9, ], p_die: 0.000, EV:  1383.462
  Dice  8 (0.138): [1, 2, 3, 4, 5, 6,       9, ], p_die: 0.000, EV:   284.588
  Dice  9 (0.111): [1, 2, 3, 4, 5, 6,    8,    ], p_die: 0.000, EV:   236.435
  Dice 10 (0.083): [1, 2, 3,    5,       8, 9, ], p_die: 0.000, EV:   499.984
  Dice 11 (0.055): [1, 2, 3, 4,          8, 9, ], p_die: 0.000, EV:   354.398
  Dice 12 (0.027): [1, 2, 3,    5, 6,       9, ], p_die: 0.000, EV:   294.848

The optimal strategy wins  91.5% of the time against three randomly playing opponents. (Of course the random strategy also wins 75% of the time against three random opponents.) No one can remember the optimal strategy by heart obviously, because the decision tree is too big. However, we can try to extract an easy to remember near optimal  strategy from the insights we gained.

The best trade-off strategy I found is quite easy to remember and wins 90.8% of the time against three random opponents. It is therefore very close to the optimal strategy.

Strategy:

  1. Always put down as few numbers as possible.
  2. If there are several ways to put down the minimal amount of numbers, use the most “central” option.

Rule number two needs a bit of an explanation. The most central number is [5], the next two are [4] and [6], followed by [3] and [7], and so on. It is sufficient to rate “centrality” separately for each number, starting with the most central one. So if you rolled 7 and [7] is already gone,  putting down [5] and [2] is better than putting down [4] and [3], because [5] is more central than [4]. There are only very few cases where it is not immediately clear which option is more central. As an example here is the order of moves this strategy proposes if you roll 11.

[5]-[6]
[4]-[7]
[3]-[8]
[2]-[9]
[2]-[4]-[5]
[1]-[4]-[6]
[2]-[3]-[6]
[1]-[3]-[7]
[1]-[2]-[8]
[1]-[2]-[3]-[5]

So if you can, put down [5] and [6]. If this is not possible, try [4] and [7], and so on. Notice that [1]-[4]-[6] is better than [2]-[3]-[6] in this strategy, because [4] is more central than [3].

Having found a satisfactory solution, I finally went to sleep at 8 am in the morning. Unfortunately I never returned to the same library to have some coffee…

 

Leave a Reply

Your email address will not be published. Required fields are marked *