My mother introduced me to

It seems like a fairly brain-dead game, and I was surprised to realize that there is some small element of strategy involved. Indeed, the more I thought about it, the less sure I was about the optimal strategy for playing this game.

Amazon.com summarizes the game thusly:

*Ten poker chips, numbered 1 through 10, are placed face up on the playing area. Roll a pair
of dice, and remove any combination of chips adding up to your total roll; keep rolling until
you can't remove a combo. Your score for that round is the total on all chips remaining face up
when play passes to the next player.*

The strategy comes in when more than one combination of chips sums to your roll. Being a computer geek, naturally my approach to determining a strategy for this game was to simulate a number of different ones. I wrote code to simulate the game, and then plugged in a variety of strategies to choose among the possible moves for each roll. The following table summarizes these algorithms and their average scores over one billion game trials. (Remember, a lower score is better.)

Fewest |
Flip the fewest chips | 16.8644 |

Most |
Flip the most chips | 32.3546 |

HighMax |
Maximize the highest-numbered chip flipped | 16.8781 |

LowMax |
Minimize the highest-numbered chip flipped | 32.2283 |

Random |
Choose a random move | 28.3982 |

Learn |
(See below.) | 17.2353 |

As you can see, the clear winners are *Fewest*, *HighMax*, and *Learn*, which it
turns out are all running almost the same algorithm.
*HighMax* and *Fewest* are the same, except that *HighMax* breaks ties toward
the highest maximum, while *Fewest* breaks ties arbitrarily.
Furthermore, examining the table produced by *Learn*'s learning stage, I see that it also
appears to be running essentially *HighMax*.
I assume that its score is slightly worse either because this simple algorithm
isn't rich enough to discover the optimal strategy, or because one billion is not enough trials in the
learning phase to perfect the strategy.

Having seen the data, this strategy makes perfect sense. It is much harder to eliminate the high numbers than the low ones, since fewer of the possible rolls can eliminate them. Specifically, the following graph plots (assuming an initial configuration) the probability that a roll can eliminate each chip.

Furthermore, since your score is the sum of the remaining chips, having the larger-value chips left at the end produces a poor score.

Of course, there are subtleties here; since most rolls are not presented with the initial configuration, there are bin-packing issues as far as rolling the right total to eliminate the remaining chips. Nonetheless, it is clearly much more difficult to eliminate the high-numbered chips, so the strategies that pass up opportunities to do so suffer.