Chomp is a two-player game which is played as follows: The two players, A and B, start with a “board” which is a chocolate bar divided into small squares. With Player A starting, they take turns choosing a square and eating it together with all squares above and to the right. The catch is that the square at the lower left-hand corner is poisonous, and the player who is forced to eat it loses.
This image from the Wikipedia article shows a typical sequence of moves for a chocolate bar:
At this point, Player A is forced to eat the poisoned square and hence loses the game.
Although the question of what the winning strategies are for this game is very much an open problem, the question of who has a winning strategy is not: On the board, Player B wins (since Player A must eat the poison piece on his first move). But for any other board, Player A has a winning strategy.
To see why, suppose not. Then if Player A’s first move is to eat just the one square in the top right-hand corner, Player B must have a winning response (since we are supposing that Player B has a winning response to any move that Player A makes). But if Player B’s response is winning, then Player A could have simply made that move to start with.
However, suppose we play Chomp not just on boards, but on boards, where and are arbitrary ordinals. The game still makes sense just as before, and will always end in finite time, but Player A no longer wins all of the time (there will no longer be a top right-hand corner square if either or is a limit ordinal).
Scott Huddleston and Jerry Shurman investigated Ordinal Chomp in this paper, and showed that it has a number of interesting properties. I’ll describe a few of them below.