| 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.
The 1st player to move could take the bottom right hand square. If the 2nd player has a winning strategy then she has a winning
response to this. But the 1st player could have done a winning move by taking the square she took as his first move.
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.
External links
|
