-> Writing -> Analysis of The Game of Chips

Analysis of The Game of Chips

by Joe Ganley

The Game of Chips 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. 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
Learn is a simple statistical learning algorithm. It runs one billion trials, choosing the move at random. It tracks, over all of these trials, the final score for each combination of the configuration of chips, the roll, and the move chosen. When the game is actually played, the strategy chooses the move that, for the given configuration and roll, resulted in the best score.

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.

Chip vs. P

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.