[Math] Winning strategy at chomp (a chocolate bar game)

combinatorial-game-theoryrecreational-mathematics

The game of chomp is an example of a game with very simple rules, but no known winning strategy in general.

I copy the rules from Ivars Peterson's page:

Chomp starts with a rectangular array of counters arranged neatly in rows and columns. A move consists of selecting any counter, then removing that counter along with all the counters above and to the right of it. In effect, the player takes a rectangular or square "bite" out of the array—just as if the array were a rectangular, segmented chocolate bar. Two players take turns removing counters. The loser is the one forced to take the last "poisoned" counter in the lower left corner.

A nice non-constructive argument shows that the first player has a winning strategy. The winning strategy can be made explicit in very specific cases. As far as I know, the more general setting for which the winning strategy is known is when we have 3 rows and any number of columns, see this page.

My question is:

Are there any recent advances on chomp?

Best Answer

Here are two papers, from 2002 and 2007; not sure if they are new to you.

Jan Draisma and Sander van Rijnswou show in their paper, "How to chomp forests, and some other graphs" (2002), that Chomp can be completely solved when the underlying graph $G$ is a forest. From the Abstract:

Interesting consequences are: first, that the starting player has a winning strategy for any non-empty tree; and second, that he has a winning strategy for the complete graph on $n$ vertices if and only if $n$ is not a multiple of 3.

A second relatively recent paper is, "Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp," by Eric J. Friedman and Adam Scott Landsberg (Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 2007, Volume 4616/2007, 200-207). Their results resist succinct summary, but, for example, they are able to compute "the expected number of winning moves" under certain circumstances.