Chomp Tidbit

prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)

Playing games is fun, and if one wins, so much the better. Mathematics has provided insight into games from many perspectives. One service mathematics provides is to classify games from different points of view. This makes it possible to apply different tools to get insights into various kinds of games. For example, a game can be classified by now many players are need for the games. Thus, we have solitaire games, games for two players, etc. Games can also be classified according to whether or not chance is involved. Poker is a different kind of game from chess because chance is involved. Probability theory can sometimes be applied to get an insight into a situation in poker. Another difference between games has to do with what moves players can make. In chess, there are two kinds of pieces, white and black, and each player controls the moves only for the pieces of one of the colors. In other games, given a position of the board, the moves that either player can make would be identical. Most games, do not allow “pass” as a move. If it is your turn to move, you must do something. John Conway (Princeton University) has tried to standardize the play of many games by setting out the principle: If you can not move (from a given position of a game) then you lose! The misere form of a game is when with the same rules as the original if you can not move you win. For reasons which are not totally clear, misere form of a game is nearly always much harder to analyze than the original game.
 
Some games are games of perfect information. This means that at each stage each of the players knows the position of the board and what moves are available to the players participating. Mathematicians have had a long interest in such games, and their study has proved to be remarkably rewarding.
 
Chomp is an example of a game of perfect information that is appealing because it is so simple to learn how to play. The game is played on a board which initially consists of a rectangular array of dots, say m rows and n columns. Think of the dots as representing appealing cookies (to eat) except that there is one cookie, at the bottom left (think of it as a black dot) which is poisoned.
 
A move consists of selecting a cookie (dot) and removing (chomping) that cookie and the cookies that are above and to the right of the dot you select. The purpose of the game is to avoid being the person to take the poison cookie. If you take the poison cookie you lose. This way of describing the game does not fit Conway’s “standardization.” To put the game in this form, have the board consist of an array of dots with the lower left dot removed. Now, using the same chomp rule, as before (when a dot is selected, it and all the dots above it and to its right are removed) , the game terminates when one of the players can not move. That player loses.
 
A typical Chomp board, in this framework, is shown below:

 

The game which is now called chomp was is often attributed to David Gale. However, essentially the same game was discovered by Fred Schuh in a different form. earlier (Schuh's game is described in terms of divisibility of integers.)

Chomp is an interesting game because it can be shown that the player who goes first can always win providing that player always responds perfectly to moves made by the second player. The proof of this goes by the name of strategy stealing. If the second player could win, then what would have stopped the first player from using that approach instead? Except for m x m, 2 x m, and m x 2, where the first player has a relatively easy to describe winning strategy, no one has a way of easily describing a winning strategy for other size boards. Recently, there has been work which suggests unexpected complexity associated with Chomp. The physicist Adam Landsberg and computer scientist Eric Friedman have shown behavior associated with Chomp that is similar to complexities associated with crystal growth. Geometric diagrams associated with chomp suggest some of the complexities one sees with automata and fractals. The new results suggest that it may be intrinsically difficult to describe the winning method for a particular chomp board. Another interesting investigation involving Chomp is if the winning move for the first player is unique or not. It turns out that for the 8 x 10 board, for example, there is more than one first move which will result in a win for the first player. (This was discovered by Ken Thompson and M. Beeler.) Determining which chomp boards have a unique first move to win seems to be very complicated, too.



Chomp has been generalized in a great variety of tantalizing ways. Some of these variants have yielded to solution and others show the same perplexing complexity of chomp itself.


References:

Gale, D., A curious Nim-type game, Amer. Math. Monthly 81 (1974) 876-879.

Peterson, I., Chaotic Chomp, Science News, July 22, 2006, Volume 170, p. 58-60.

Schuh, F., Spel van delers, Nieuw Tijdschrift voor Wiskunde, 39 (1952) 299-304.