Making shut-the-box fair
The standard game of "shut the box", analyzed in previous posts, has a fundamental flaw: it's not fair! On average in a two-player game, the first player will lose 2.5% of their stake in each game. Can we make a more fair two-player game?

The simplest solution is to change how ties are treated: with optimal strategies, 1% of the games end in ties. We can resolve all ties in favor of the first player, but that's not good enough. We actually need to treat ties like box-shutting, and award double payoffs. And it's still not enough, especially since the 2nd player can alter their strategy to avoid ties if they become too painful.

So let's leave ties alone, and alter the box-shutting payoff. Although the 2nd player has an advantage in the points race, because they know what 1st player score they have to beat, the 1st player has an advantage in shutting the box: if there are able to do so, the game ends immediately and the 2nd player doesn't have a turn. The 2nd player doesn't have the opportunity to, for example, achieve a shut box themselves, tying the game.

In the standard game, box-shutting pays out double: if everyone had to put up a $1 stake to play, then they have to pay another $1 to the player who is able to shut the box. We'll call this a "2x" payout. Even odds work out to a 3.8x payout (accounting for the fact that optimal strategies change as the payout rises). It would be a little awkward to ante up $2.80 a person in a $1 ante game, but it turns out that a 4x payout ($3 more from each person on a shut box) is probably okay: this only gives the 1st player a 0.1% advantage. That might be enough for a casino to live on, but it's probably acceptable among friends.

Another way to even the odds is to force the players to alternate turns. This is hard in the physical game, where there's only one physical box with tiles, but it is natural in a computer version of shut-the-box — and it probably improves gameplay by elimininating the long waits between a player's turns. The first player still has a slight advantage, but computation indicates that this advantage is limited to 0.4% of the stake ("acceptable among friends"). It's hard to compute optimal strategies in a 3 player game, due to combinatorial explosion, but it appears the first player's advantage grows as the number of players does.

Even more shutting of boxes.
In previous posts I've talked about mathematics and strategies for the "shut the box" game. I've been describing a two-player game, but shut the box can be played with any number of players. How do strategies change?

It's easy to think about the limit case and work backwards. If there are an infinite number of players, eventually someone will "shut the box" — it happens in about 1 in 10 games, after all. Since the round will eventually end this way, then your final score doesn't matter: all that's important is whether you manage to shut the box. Every player's strategy is identical. (With an infinite number of players, there is no "last" player — in fact, even if there were one, there would be an infinitesimal chance of their touching the dice: they game would almost certainly be ended by a previous player's shutting the box before the "last turn" occurred.)

A strategy which maximizes your chances of shutting the box, ignoring final score, is easy to implement and evaluate, and differences from the "largest result" strategy described previously can again be tabulated on a single side of a sheet of paper. This "most zeros" strategy manages to shut the box in 9.8% of games played, but still loses in a two player game — even though the optimal 1st player strategy only manages the shut the box in 9.5% of its games. As first player against an optimal 2nd player, "most zeros" loses 3.3% of the stake in each game, compared to only 2.5% lost by an optimal 1st player (game results: 9.5% 1st player shut box, 8.2% 2nd player shut box, 37.3% 1st player by points, 43.8% 2nd player by points, 0.9% ties). As second player against an optimal 1st player, "most zeros" loses 2.8% of the stake; an optimal second player would win 2.5% of the stake (game results: 9.5% 1st player shut box, 8.8% 2nd player shut box, 41.1% 1st player by points, 39.7% 2nd player by points, 0.9% ties).

Since the box is shut with a fairly high probability, we converge to the "most zeros" strategy fairly quickly as the number of players increases. Intermediate strategies are parameterized by the "score to beat" (the minimum score achieved by previous players) and the probability distribution of the minimum score to be achieved by future players. The complexity of computing exact solutions increases quickly.

In my next post on the topic, I'll discuss an "alternating turns" variant of shut-the-box which might be a more enjoyable real-time-collaborative computer game.

xkcd and shut-the-box

An xkcd comic from a while ago mentioned a "knapsack problem," and one reader (dhogarty) wrote some set enumeration code to tackle it.

Before I go further, I should mention that Knuth is the definitive reference here (as in most things), in particular Volume 4 which is now available only in fascicle form. If you haven't been reading the pre-fascicles just as soon as they're posted on the TAOCP web page, you're a sad sorry person who doesn't deserve to be called a computer scientist. (If you're not a computer scientist, read at least fascicle 4's chapter on the history of combinatorics; you can buy a hardcopy from amazon.)

The xkcd problem is called a "knapsack problem", but it's not, really; see Knuth's commentary around Algorithm F of (vol 4 fascicle 3a). We're generating multicombinations of n items taken from the m appetizers (repetition permitted). It's always worthwhile generating your options in strict lexicographic order to get a handle on duplicates; consult the history of combinatorics cited above for cautionary tales.

A compact way to generate multicombinations without duplicates is simply to require the output to be in lexicographic (sorted) order. For example, tweaking dhogarty's code only slightly:

def all_seqs(size, alphabet):
   for n,c in zip(xrange(len(alphabet)), alphabet):
     for s in all_seqs(size-1, alphabet[n:]) if size>1 else [[]]:
       yield [c]+s

You can wrap this in an iteration of sizes from 0 to infinity to generate multicombinations of all possible cardinalities.

A more elegant solution only generates multicombinations which sum properly (this is similar to Knuth's Algorithm F):

def ways_to_sum(total, menu):
    if total < 0: return
    if total == 0: yield []
    for (item,price),n in zip(menu, xrange(len(menu))):
        for tail in ways_to_sum(total-price, menu[n:]):
            yield [ item ] + tail

menu = [('Fruit', 215), ('Fries', 275),
        ('Salad', 335), ('Wings', 355),
        ('Sticks', 420), ('Sampler', 580)]

for solution in ways_to_sum(1505, menu):
    print solution

It's regrettable that the solution isn't unique. Bad Randall.

I've found lots of opportunities to generate "all possible solutions" in various contexts, and Python's generators have generally been an elegant means to express solutions. For example, I've been discussing "Shut the Box"; here's some code fragments to generate all possible plays for some board state:

def ways_to_sum(total, min_digit=1, max_digit=9):
    """Generate all the ways to sum to the given total using the digits
    `min` through `max` without repetitions.
    By default min and max are 1 and 9, respectively.

    >>> list(ways_to_sum(1))
    >>> list(ways_to_sum(2))
    >>> list(ways_to_sum(3))
    [[1, 2], [3]]
    >>> list(ways_to_sum(12))
    [[1, 2, 3, 6], [1, 2, 4, 5], [1, 2, 9], [1, 3, 8], [1, 4, 7], [1, 5, 6], [2, 3, 7], [2, 4, 6], [3, 4, 5], [3, 9], [4, 8], [5, 7]]
    for first in xrange(min_digit, min(max_digit+1, total)):
        for tail in ways_to_sum(total-first, min_digit=first+1, max_digit=max_digit):
            yield [ first ] + tail
    if min_digit <= total and total <= max_digit:
        yield [ total ]

def all_states(min_digit=1):
    """Generate all possible shut-the-box states."""
    if min_digit <= 9:
        for x in all_states(min_digit=min_digit+1):
            yield x
            yield [min_digit] + x
        yield []

The all_states() function generates the states in lexicographic order based on the set's binary representation (a9 a8 a7 ... a2 a1, to use Knuth's notation).

[This was originally going to be a comment on dhogarty's post, but after writing it I discovered that dhogarty had broken his wordpress installation sometime after 12 Sep 2008. I reverse-engineered the "Captcha-free" spam protection and fixed the Ajax URL in his page, but no dice. Querying the "Captcha-free" implementation with a python one-liner and performing a manual submission still loses. Maybe trackback will work.]

More shut-the-box
In previous entries I've been discussing the mathematics of the game "Shut the Box". I first asked about good strategies which were simple enough for a human to use.

One obvious intuitive strategy is to chose tiles to flip down such that your score is as low as possible after each turn. It turns out this is an extraordinarily bad choice: against an optimal 2nd player, the 1st player can expect to lose 75.3% of their stake in each game, and against an optimal 1st player, a second player following this strategy will lose 70.8% of their stake (first player shuts the box 9.5% of the time and wins 71.5% of the rest of the games).

A better strategy is the opposite: flip tiles so that your score is as high as possible after each turn! Against optimal play, this strategy shuts the box in 9.6% of games and loses 5.8% of the stake as the first player (compared to shutting the box in 9.5% of games but losing only 2.5% of the stake when playing optimally), and loses 5.3% of the stake as the second player (compared to winning 2.5% when playing optimally). Obviously, this strategy is a little better as a 1st player strategy: the 2nd player can improve by immediately flipping tiles to secure a win or tie if the opportunity is available, and following the "largest result" strategy otherwise. This loses only 1.2% of the stake to an optimal 1st player (again, compared to losing 5.3% using the unmodified strategy or winning 2.5% using an optimal 2nd player strategy).

A table of the positions where optimal 1st player strategy differs from "largest result" is small enough to memorize (!) or squeeze on a single page as a cheat sheet allowing actual optimal 1st player play by a human (390 differences from optimal). Optimal 2nd player strategy is more complicated: tabulating the differences from even the modified "largest result" strategy described above still runs to 15 pages. As far as I know this is still an open problem: is there a better "short and comprehensible" strategy? Is there a better way to represent optimal 2nd player play to allow real practice by a human?

In my previous post, I promised to describe how strategy changes when you increase the number of players in the game, and to talk about an "alternating turns" variant of the game. That will have to wait until the next post -- this one is long enough already!

Shut the box, continued
In my earlier post, I asked you to consider whether "shut the box" was fair. luckylefty got the correct answer quickly: it's not fair -- and (surprisingly) it's the first player who is at a disadvantage. The nice thing about this game is that the state space is not large, so you can actually evaluate all possible games played and formulate optimal strategy. Given optimal play by both players, on average the first player will lose 2.5% of their stake each game. This is despite the fact that the first player can expect to shut the box 9.5% of the time, while the second player can only shut the box 8.2% of the time. The second player wins 43.1% of the times the box is not shut, compared to the 1st player's 38.2%. The second player knows what score they need to beat to win, and that confers a substantial advantage. In fact, the first player can't expect to profit unless they score a 27 or lower on their turn.

The computer can calculate an optimal strategy: but can it be described in terms simple enough for a human to learn and use? I'll describe a reasonable "human playable" strategy in my next post on this theme.

You might also want to ponder these questions: how might the strategy change if the number of players in the game increased, from 2 to, say, 10? Or 100?

And would making the players strictly alternate their turns make the game more fair?

A game to think about.
My family has a nice shut the box set at home. They play with the rules variation where the final score is the digits left uncovered, read in order -- ie, if 1, 5, and 9 are left uncovered, the score is 159 (some variants instead use the sum of the digits as the score), and you must roll two dice unless the sum of the uncovered digits is 6 or less, in which case you must roll only one die (some variants make this a free choice). In a two player game, both players put a dollar in the pot and then the first player attempts to shut the box; if he fails the second player starts from scratch and tries to shut the box; if they both fail, the winner is the player with the lower score. If the game ends by shutting the box, the winner gets the $2 in the pot and an extra dollar from the other player (double the stake); otherwise the winner just gets the pot.

An easy question: is this a fair game? If not, who is the sucker?

A hard question: what's the best "short" strategy for playing the game? (I'll define a "short" strategy as "capable of being described on a single side of a sheet of paper.)

Answers in a future post...