Chomp

Chomp is a two-player strategy game played on a rectangular grid of squares, often visualized as a chocolate bar. Players take turns "eating" a square and all squares above and to the right of it. The square in the bottom-left corner is "poisoned" — the player forced to eat it loses. Despite its simple rules, Chomp has deep mathematical properties and connects to important concepts in combinatorial game theory.

Rules

1. The game starts with a rectangular grid (e.g., 5x4), visualized as a chocolate bar divided into squares.
2. Players alternate turns.
3. On each turn, a player selects any remaining square. That square and all squares above it and to its right are removed ("eaten").
4. The bottom-left square is poisoned (often marked with a skull or different color).
5. The player who is forced to eat the poisoned square loses.

Strategies

• First Player Wins: It has been proven mathematically (by a strategy-stealing argument) that the first player always has a winning strategy on any rectangular grid larger than 1x1. However, the proof is non-constructive — it proves a winning strategy exists without revealing what it is.
• Corner Nibble Opening: On the first move, eating only the top-right corner square is often a strong opening, as it preserves maximum flexibility.
• L-Shape Positions: When the remaining squares form an L-shape with equal-length arms, the position is often losing for the player whose turn it is.
• Symmetry Strategy: On square grids (NxN), the first player can win by eating the top-right corner on the first move, then mirroring the opponent's moves. This doesn't work on rectangular grids.
• Small Grid Memorization: For small grids (up to 5x4), winning and losing positions can be memorized through complete game tree analysis.
• Reduce Options: Try to leave your opponent in positions with few squares remaining, forcing them toward the poisoned corner.

Chomp was invented independently by mathematician David Gale in 1974 and by Fred Schuh in 1952 (who called it a different name in his Dutch-language book on mathematical games). Gale published the game in the American Mathematical Monthly, where it quickly attracted attention from mathematicians and game theorists.

The game's most famous mathematical property is its "strategy-stealing" proof. The argument goes: if the first player doesn't have a winning strategy, then the second player does. But the first player could always eat just the top-right corner square on their first move — if the second player then has a winning response, the first player could have made that same response as their first move instead. This contradiction proves the first player must have a winning strategy. However, this proof tells us nothing about what that strategy actually is.

For non-square rectangular grids, finding the optimal strategy remains an open problem in mathematics. While computers have solved small grids exhaustively, no general formula is known. This makes Chomp one of the simplest-to-state unsolved problems in combinatorial game theory.

Chomp has deep connections to other areas of mathematics, including partially ordered sets (posets) and divisor lattices. A variant called "Schur's Game" or "Divisor Chomp" replaces the rectangular grid with divisors of a number — players choose a divisor and remove all its multiples. The game has been used as a teaching tool in universities to introduce students to game theory, proof techniques, and computational complexity.