Mathematical mysteries: Chomp

Issue 14
March 2001

Chomp is a simple two-dimensional game, played as follows.

Cookies are set out on a rectangular grid. The bottom left cookie is poisoned.

Two players take it in turn to "chomp" - that is, to eat one of the remaining cookies, plus all the cookies above and to the right of that cookie.

The loser is the player who has to eat the poisoned cookie.

We can ask if either player has a winning strategy, that is, can one player, before starting play, be sure of winning?

The answer to this question is yes. One of the players is sure to have a winning strategy. This is easy to see, because the game must finish in finitely many moves, and can't be drawn. In fact, the person who plays first can be certain of winning, if they make the right moves. To see this, suppose the first player (Player A) makes the first move by chomping just the top right-hand cookie. Then either this is the first move of a winning strategy for Player A, or there is a reply which is the first move of a winning strategy for Player B. If the latter is the case, then Player A could have opened with that very move and been guaranteed a win.

So what is the winning strategy for Player A? Well, that is the mystery - nobody knows! The proof that there is a winning strategy for the first player was very simple - but didn't describe the strategy. No one has ever been able to do that. Maybe you can!

There are some simple cases where a winning strategy can be described - Square Chomp and Thin Chomp. Square Chomp is Chomp played on a square grid, and Thin Chomp is Chomp played on a grid that is only two squares wide. See if you can find the winning strategies in these special cases - or find out how if you get stuck.

Helen Joyce is an assistant editor of Plus.

Thanks to John Webb of the University of Cape Town in South Africa for telling me about Chomp.

It's obvious.... or is it?

"One of the players is sure to have a winning strategy. This is easy to see, because the game must finish in finitely many moves, and can't be drawn."

Is that "easy to see"?

It implies a theorum: "If a game must finish in finitely many moves, and can't be drawn, then there must be a winning strategy for one player."

No doubt it's "easy to see" once explained, but it's far from obvious to ne... it would be nice to have an explanation, or proof....

Proof (or explanation)

Label a position a winning position if there is at least one move to a losing position, a losing position as one with no moves to non-winning positions, and a drawing position as one where there is no move to a losing solution, but there is a move to a drawing position. The final position(s) are unknown, but they are not . The first player has a winning strategy on a position when it is a winning position, and the second player has a winning strategy if it is a losing position (this should at least be obvious). Therefore, the only time when neither player has a winning strategy is in a drawing position.

Consider such a drawing position. By definition there is a move to another drawing position. However, that creates an infinite sequence of moves, which contradicts the original assumption that the game is finite. Therefore there are no drawing positions, and every finite game that cannot end in a draw has a winning strategy for one of the players.

Note: This argument doesn't work for infinite games. There are some (highly interesting) infinite games that cannot end in a draw, but neither player has a winning strategy.