What this game is
Chomp is played on a chocolate bar. A move picks one square and eats it together with every square to its right and above it — a rectangular corner breaks off the bar. The bottom-left square is poisoned, and whoever is left to eat it loses. There are no draws.
The game is known as Chomp from David Gale, who described it in 1974. An equivalent game about divisors of a number had been published earlier, by Frederik Schuh in the 1950s, but the chocolate-bar form is Gale's.
Whatever moves are played, what remains of the bar is always a staircase: no row is ever longer than the row below it. That is what makes the game small enough to be counted square by square.
The stolen strategy
On any rectangular bar bigger than 1×1 the first player has a winning strategy, and the proof takes three lines. Suppose the second player won with correct play. Then to the opening move "eat the top-right square" the second player would have some winning reply. But the first player could have made that very reply as the opening move — the top-right square would have been eaten along with it anyway. So the first player has a move after which the first player wins. Contradiction.
The proof is non-constructive: it guarantees that a winning first move exists and does not name a single one. Nim has Bouton's formula — an XOR you can do in your head. Chomp has no formula. For any particular bar the winning moves are found only by checking the positions, all of them.
This 8×5 bar is solved completely
The staircase positions on an 8×5 bar number about thirteen hundred. When this page loads, the machine walks through every one of them and marks it: winning or losing for the player about to move. That takes milliseconds.
The first move is yours — which is to say, you were handed the side that is proven to win. On the expert level the machine plays the table exactly: while you hold the winning line it can only drag the game out, picking the longest continuations and waiting. One mistake, and the table carries the game to the poisoned square in your hands.
Levels
- Normal — the computer consults the table on about a third of its moves; the rest are picked at random.
- Hard — the table three times out of four.
- Expert — the table on every move. From a winning position it always answers with a losing one for you; from a losing position it plays the longest resistance it can find.
The computer never eats the poisoned square while it has any other choice — and neither can you: the square unlocks only when it is the last one left.