Chomp is a 2-player game played on a rectangular chocolate bar made up of smaller square blocks. The players take it in turns to choose one block and eat it together with those that are below it and to its right. The top left block is poisoned and the player who eats this loses.
Example Game
Below shows the sequence of how a typical game could look
Initially Player A Player B Player A Player B
xxxxx xxxxx xxxxx x x
xxxxx xxxx xxxx x
xxxxx xxxx x x
Player A must eat the last block and so loses.
Who wins?
Chomp belongs to the category of 2-player perfect information games and so any position can be said to be a 1st player win or a 2nd player win. It turns out that for any rectangular starting position bigger than 1 x 1 the 1st player can win.
This is because of an ingenious strategy stealing argument. Assume that the 2nd player has a winning strategy against any initial 1st player move. Suppose then, that the 1st player takes only the bottom right hand square. By our assumption, the 2nd player has a response to this which will force victory. But if such a winning response exists, the 1st player could have played it as his first move and thus forced victory. Contradiction.
Generalisations of Chomp
3-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 which all of whose indices are greater or equal to the chosen block. In the same way Chomp can be generalised to any number of dimensions.
Ordinal Chomp is played on an infinite board with some ordinal as its length. For example a 2 by ω + 4. A move is to pick any block and remove all block with both indices greater than or equal to it.
More generally than the above Chomp can be played on any partially ordered set with a least element. A move is to remove any element along with any larger elements. A player loses if they take the least element.
See also
External links