Chomp is a two-player game that starts out with an M by N chocolate bar, in which the square on the top left corner is poisonous. A player must name a remaining square, and eat it together with all the squares below and/or to the right of it. Whoever eats the poisonous one (top-left) loses. The game can also be interpreted as two players alternately name a devisor of a given number N, which may not be multiples of previously named numbers. Whoever names 1 loses.

It is easy to see that any rectangular shaped Chomp positions is an N-position (losing): you can take the piece on the bottom right corner, if your opponent has a winning move, then since you start first, you can move to that position directly, and therefore you are winning. If he does not has a winning move, then your original move is winning. So you can win no matter what. However, this proof only says that you can win, but not how. People have tried to find out a general winning strategy, but only sporadic results are available.

Even fewer results are available for infinite Chomp: positions with infinite number of pieces. It is trivial for two-dimensional Chomp: take the piece at coordinate (2, 2), hence you only have two axis left. Now if your opponent moves on the x-axis, mimic it on the y-axis, and vice versa. Dr. David Gales offered a prize of $100.00 for the first complete analysis of 3D Chomp. You can try to play the game here.

Improvements on Chomp

Integers, vol. 2 (2002)

The article extends the result in Three-Rowed CHOMP by Doron Zeilberger by being able to calculate P-positions with unlimited number of rows and columns (up to the limit of your computer and Maple, of course). It also improves a result in Winning Ways for Your Mathematical Plays by providing a formula to calculate P-positions with three pieces in the second column.

The article is available in Latex , dvi and ps formats. You can also download the Maple source code here. Other results include the lists of P-positions with up to 4 rows and 9 columns, P-positions with the top 16 rows having at most two pieces, and the values of the Grundy function with positions with up to 4 rows and 40 columns.

The Sprague-Grundy Function for Chomp

(In preparation)

The article calculated the Sprague-Grundy Function for three and four-rowed Chomp positions, and found out that then the top rows are fixed, the difference between the value of the Sprague-Grundy function and the value of the last row is periodic. It also gave the complete result for the Sprague-Grundy function for two-rowed Chomp positions. The article is also available in Latex, dvi and ps formats. The Maple package is also downloadable. Some result generated by the package include Sprague-Grundy function for two-rowed positions up to 250 columns, and some  three and four-rowed positions. Another set of results generated by a separate C++ program is also available for three-rowed (up to 500 squares per row. 81MB) and four-rowed (up to 140 squares per row. 67MB) positions. The result also supports the conjecture in the article, which was proved by Steve Byrnes in his paper Poset Game Periodicity.

Additional Results

The following result is believed to be first proved by Scott Huddleston, although the original proof is not available: For any Chomp P-positions (a, b, c) with a >= b >= c, a - b will eventually be periodical if there exist no a' > c such that (a', a', c) is a P-position. It was proved again by Steve Byrnes.

The following result is proposed by David Gale and proved by Andries Brouwer: If (a, b, c) is a P-position with a >= b > = c, then a reaches its maximum when b = c for any fixed b.

References

E. R. Berlekamp, J.H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays , Academic Press, London, 1982. 598-599 Doron Zeilberger, Three-Rowed CHOMP, Adv. Appl. Math. v. 26 (2001), 168-179 Richard J. Nowakowski, Games of No Chance , Cambridge University Press, 1998, 482 D. Gale, A Curious Nim-type game , Amer. Math. Monthly 81 (1974), 876-879