Chomp

Chomp is a two-player strategy game played on a rectangular chocolate bar made up of smaller square blocks (cells). The players take it in turns to choose one block and "eat it" (remove from the board), together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.

The chocolate-bar formulation of Chomp is due to David Gale, but an equivalent game expressed in terms of choosing divisors of a fixed integer was published earlier by Frederik Schuh.

Chomp is a special case of a poset game where the partially ordered set on which the game is played is a product of total orders with the minimal element (poisonous block) removed.

Below shows the sequence of moves in a typical game starting with a 3 × 5 bar:

Player A must eat the last block and so loses. Note that since it is provable that player A can win, at least one of A's moves is a mistake.

Chomp belongs to the category of impartial two-player perfect information games.

It turns out that for any rectangular starting position other than 1×1 the first player can win. This can be shown using a strategy-stealing argument: assume that the second player has a winning strategy against any initial first-player move. Suppose then, that the first player takes only the bottom right hand square. By our assumption, the second player has a response to this which will force victory. But if such a winning response exists, the first player could have played it as his first move and thus forced victory. The second player therefore cannot have a winning strategy.

Computers can easily calculate winning moves for this game on two-dimensional boards of reasonable size.

Three-dimensional Chomp has an initial chocolate bar of a cuboid of blocks indexed as (i,j,k). A move is to take a block together with any block all of whose indices are greater or equal to the corresponding index of the chosen block. In the same way Chomp can be generalised to any number of dimensions.

...
Wikipedia