My mother introduced me to The Game of Chips,
which she had seen in some restaurant, where apparently it served the same purpose as those
triangular peg puzzles: to keep you busy while you wait to be served.
It is a very simple game, and actually sort of cool: Kids can easily understand it, and it's
very portable.
If you like this game, beware: I'm about to ruin it for you.
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.