The Game of Chomp
Introduction
The Game of Chomp consists of a chocolate bar with n×m pieces. There are two players who alternate turns. A turn consists of eating a piece of the chocolate. When a piece is eaten, all the pieces to the right and below the chosen piece are eaten too. The top left piece of the chocolate is poisoned. Whichever player forces the other player to eat the poisoned piece wins the game. This form of the game was given by David Gale and is related to the Game of Divisors formulated by Frederik Schuh.
First player can always win
For games of size other than 1×1, we can prove that the first player has a winning strategy. The game is finite and it cannot end in a tie. At least one player has a winning strategy. Assume that the second player has a winning strategy against any initial first player move. Therefore, if the first player chooses to eat the bottom-right piece of chocolate, the second player has a response that forces victory.
Now, we can use a 'strategy stealing' argument to say that the first player should play the response instead of eating the bottom-right piece (which will anyway be consumed by eating any other piece.) This means now the first player can force victory. This is a contradiction, and so the second player cannot have a winning strategy. The first player, therefore, always has a winning strategy.
But what is the winning strategy?
The proof to show that there is a winning strategy is ‘non-constructive’ which means we have not demonstrated an explicit winning strategy. Except for in specific cases, this is still an open question!
Specific Cases
- n×n (n is greater than 1) In the n×n case the first player should eat the (2,2)th piece of chocolate, leaving an 'L' shape. From there, the player should respond by mirroring the strategy of the second player, i.e., if the second player eats the (m,1)th piece of chocolate, the first player should eat the (1,m)th piece and vice versa.
- n×2 In the n×2 case, the first player should eat the bottom-right square. Thereafter, if the second player picks (m,1), the second player should pick (m-1,2) and vice versa.
Can you figure out the strategy for other special cases or imagine a three dimensional version of the game?
Interesting Links
