Can You Shut the Box?

In a simplified game of Shut the Box, six tiles numbered $1$ through $6$ start face up. You roll a fair die, and may then flip down any set of still-up tiles whose values add up to the roll. You keep rolling; you win if you flip every tile down, and lose the moment a roll cannot be matched by any subset of the remaining tiles. Playing optimally, what is your probability of winning?

The Fiddler, Zach Wissner-Gross, September 13, 2024(original post)

Solution

Work backwards over the $2^6$ sets of tiles that might still be up. From a set $S$, a roll of $d$ can be answered only if some subset of $S$ sums to $d$, and among those you flip the subset that leaves the best onward chances. So the value of a state obeys $$W(S)=\frac16\sum_{d=1}^{6}\ \max_{\substack{T\subseteq S\\ \sum T=d}} W(S\setminus T),$$ with $W(\varnothing)=1$ and any roll that no subset can match contributing $0$. Evaluating from the empty set upward, the full board $\{1,\dots,6\}$ comes out at $$\boxed{\tfrac{145}{1944}}\approx7.46\%.$$ The game is harsh: a single unmatchable roll ends it, and with six tiles you almost always strand one.

The computation

The recurrence is exact, so memoise $W$ over the set of up tiles, trying every subset that matches each roll and keeping the best continuation.

from fractions import Fraction as F
from functools import lru_cache
from itertools import combinations
@lru_cache(maxsize=None)
def W(S):                                         # S: sorted tuple of up tiles
    if not S: return F(1)
    total = F(0)
    for d in range(1, 7):
        best = F(0)
        for r in range(1, len(S) + 1):
            for T in combinations(S, r):
                if sum(T) == d:
                    best = max(best, W(tuple(x for x in S if x not in T)))
        total += F(1, 6) * best
    return total
print(W(tuple(range(1, 7))))                       # 145/1944

Extra Credit

Now play the standard game: two dice, and nine tiles numbered $1$ through $9$.

Solution

The same backward recursion applies, now over $2^9$ states with the roll being the sum of two dice, so $d$ runs from $2$ to $12$ with the usual triangular weights. Optimal play wins with probability $$\boxed{\ \frac{466473281}{6530347008}\ }\approx7.14\%,$$ a touch lower than the six-tile game: more tiles give more flexibility, but the heavier two-dice rolls and the awkward high tiles $7,8,9$ just outweigh it.

The computation

The same memoised recursion, now averaging over the $36$ ordered outcomes of two dice.

@lru_cache(maxsize=None)
def W2(S):
    if not S: return F(1)
    total = F(0)
    for d1 in range(1, 7):
        for d2 in range(1, 7):
            d, best = d1 + d2, F(0)
            for r in range(1, len(S) + 1):
                for T in combinations(S, r):
                    if sum(T) == d:
                        best = max(best, W2(tuple(x for x in S if x not in T)))
            total += F(1, 36) * best
    return total
print(W2(tuple(range(1, 10))))                     # 466473281/6530347008