CHOMP

CHOMP, I learned it from Yale’s open course, Game  Theory. And I have spend my spare time on finding the explicit strategy of it. First, we introduce the game through Wikipedia.

Chomp is a 2-player game of strategy played on a rectangular “chocolate bar” made up of smaller square blocks (rectangular 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.

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

We can conclude some very interesting and easy conclusions through our effort on small blocks.(thanks for the pictures of Wikipedia)

Before we figure out the results, we have to simplify the graph with arrays.

The initial condition in the example, we can use (5,5,5) to represent. The later steps are (5,4,4),(5,4,1),(1,1,1),(1,0,0). And it is easy to find that:

• If the block is $1\times n$ or $n \times 1$, the first player will always win. He can remove all the points except the last one.
• If the block is $2 \times n$ or $n \times 2$, the first player always have winning strategy. The explicit strategy is :

If the array is $(l,l-1)$, then the first one will always lose. We can prove it by induction, because there are only two rows(columns), if we remove points from the upper one, then it remains a smaller block, then we can use our results on smaller blocks as we want. If the points are in the lower row, then we can delete some points to make the shape of $(s,s-1)$. That will lead to our induction. Where $s$ is less than $l$.

• For higher dimension blocks, we will drive ourselves into a very complicated gaming. But one thing we should remember, the symmetry of the shape is very important. With a symmetric shaped block, the fist player can delete the very point to make the case into (k,1,1,…1), and that’s obviously a winning initial.
• For the proof that $m\times n$ blocks except the $1\times 1$ case, the first player will win, i.e. he has winning strategy whatever the second player moves in the process. We consider if the first player has not winning strategy, then whatever he does, the second player will have his way to make himself to win. We assuming the first player removes the point in the corner down on the right side. And the second player moves to make himself into a winning initial. We shall say if this is true, then the first player can make this move earlier to get into the winning initial. This is a strategy-stealing game, actually.