Playing Games in the Transfinite: An Introduction to “Ordinal Chomp”

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 n \times m 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 5\times 3 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 1\times 1 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 n\times m boards, but on \alpha\times\beta boards, where \alpha and \beta 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 \alpha or \beta 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.

First of all, to make things a bit easier to discuss, we will consider only n\times \alpha games where n is finite rather than \beta\times\alpha games where \beta is arbitrary. However, everything said will go through fine in that case as well.

Secondly, we will use the following game which is equivalent to Chomp: At any point in the game, the board is described by a non-increasing sequence (\alpha_0,\ldots, \alpha_n). On each turn, the appropriate player picks an i and a \beta such that \beta < \alpha_i and replaces the sequence with (\alpha_0,\ldots, \alpha_{i-1},\beta,\ldots, \beta). We call this taking a bite of height \beta. Playing on an n\times m chocolate bar as described above corresponds to playing with the sequence (m,\ldots, m) consisting of n m‘s.

For ease of discussion later, we make the convention that any sequence (not just a non-increasing one) describes a game position by stipulating that (\alpha_1,\ldots, \alpha_n) is the same as the position (\alpha_1,\min\{\alpha_1,\alpha_2\},\ldots,\min\{\alpha_1,\ldots,\alpha_n\}).

We saw above that Player A wins all non-trivial finite Chomp games, so let’s start by looking at a transfinite chomp game that Player B wins: 2\times \omega, or (\omega,\omega) in our new notation. What is Player B’s winning strategy? Well, notice that Player A’s first move has to put the game either in the state (n,n) for some n or (\omega, n) for some n. In either case, Player B can then move the game into state of the form (m+1,m) for some m. From a position of that form, whatever Player A does, Player B can again move to a position of that form. Eventually, Player B will move to the position (1,0), and Player A will be forced to eat the poison piece.

So, Player B can win at least some transfinite Chomp games, although he still loses a lot of them: for example, he loses all games of the form 2\times \alpha where \alpha > \omega. The reason is that in such a game Player A can win by first moving to the position 2\times \omega and then using Player B’s winning strategy! Similarly, Player B loses all games n \times \omega for n > 2.

In fact, for any ordinal \alpha, there is exactly one ordinal \beta such that Player B wins \alpha\times\beta. This is a consequence of what Huddleston and Shurman call the Fundamental Theorem of Transfinite Chomp in the above paper. Another interesting consequence, which illustrates the style of reasoning used in their proof of the Fundamental Theorem, is the following:

Theorem: For any sequence \alpha_2,\ldots, \alpha_n of ordinals, there is exactly one ordinal \alpha_1 such that Player B wins the game (\alpha_1,\ldots,\alpha_n). (Remember the convention above about sequence which are not necessarily non-increasing.)

Proof: The uniqueness is similar to the argument given above: If Player B has a winning strategy on the game (\alpha_1,\ldots,\alpha_n) then Player A has a winning strategy on all games (\alpha'_1,\alpha_2,\ldots,\alpha_n) where \alpha'_1 > \alpha_1, since Player A can just move to the position (\alpha_1,\ldots, \alpha_n) and then use Player B’s winning strategy.

The existence is by induction. Fix \alpha_2,\ldots, \alpha_n and suppose that for all \beta_2,\ldots,\beta_n where \beta_i \leq \alpha_i for all i and for at least one i, \beta_i < \alpha_i we know that there is a \beta_1 = h(\beta_2,\ldots,\beta_n) such that Player B has a winning strategy.

For each ordinal \gamma, let B_\gamma be the set of all (\beta_2,\ldots, \beta_n) obtainable from (\alpha_2,\ldots, \alpha_n) by taking a bite of height \gamma (this term was defined above, if you forgot what it means).

Let H = \{ h(\beta_2,\ldots,\beta_n)\mid (\beta_2,\ldots,\beta_n)\in B_\gamma\text{ and }h(\beta_2,\ldots,\beta_n) > \gamma \}. Let \alpha_1 be the minimal ordinal not in H. I claim that Player B has a winning strategy for (\alpha_1,\ldots,\alpha_n). We will show this by showing that, for any move Player A makes, Player B can make a move that we know leads to a winning strategy for B.

So suppose Player A moves to (\beta_1,\ldots, \beta_n). Either \beta_1 < \alpha_1 or \beta_1 = \alpha_1. First suppose that \beta_1 = \alpha_1. This means that Player A moved by taking a bite of height (say) \gamma out of (\alpha_2,\ldots, \alpha_n) by moving to (\alpha_1,\beta_2,\ldots, \beta_n). But by construction, we know that \alpha_1 \ne  h(\beta_2,\ldots, \beta_n), which means that the player who is to move (Player B in this case) has a winning strategy.

Now suppose \beta_1 < \alpha_1. This means by construction of \alpha_1 that \beta_1 = h(\beta'_2,\ldots, \beta'_n) where \beta'_i \leq \beta_i for all i and \beta'_i < \beta_i for at least one i. Thus, if Player B moves to the position (\beta_1,\beta'_2,\ldots, \beta'_n) he ensures himself a win. \square.

Note that this proof is constructive. This means that you can actually use it to compute that (as we already know), the unique \alpha such that Player B wins (\alpha,\omega) is \omega. As a puzzle, you might like to find the unique \alpha such that Player B wins (\alpha,\omega,1) (or such that Player B wins (\alpha,\omega,\omega) or (\alpha,\omega^\omega,\omega^2) or whatever you like, although the last one will be hard).

The much-more-general Fundamental Theorem of Transfinite Chomp in the paper linked above is also constructive. It allows you, in theory, to compute who will win the n-dimensional game (we have been considering 2-dimensional games) \alpha_1\times \cdots \times \alpha_n for any ordinals \alpha_i. However, this is quite difficult in practice: according to the Wikipedia article, it is an open question who wins the 3-dimensional game \omega\times\omega\times\omega.

As a final note, in the book Tracking the Automatic Ant, David Gale gives a very nice non-constructive proof that for all n, there is a unique \alpha such that Player B wins n\times \alpha.

About these ads


Filed under Uncategorized

4 responses to “Playing Games in the Transfinite: An Introduction to “Ordinal Chomp”

  1. GR

    No doubt it is a silly point and perhaps I am just being thick here, but here goes anyway… Now, if we speak of an n x m board where n and m are finite, this uniquely picks out both 1) a board whose highest column/row are specified by the finite ordinals n and m, and 2) a board whose column/row count has cardinality the cardinality of the ordinals n and m. You get both, because these descriptions pick out the very same board.

    But this nomenclature breaks down when you turn to speak of an alpha x beta board where alpha and/or beta are limit ordinals. The board whose highest column has ordinal alpha is just one of the many board(s) whose column count has the cardinality of alpha.

    If when you speak of an alpha x beta board, you mean to pick out board(s) by cardinality, then you will have picked out not a single board but a rather large collection of boards, and in particular have not distinguished between the board with a column for every n < alpha and no more, and the board whose highest column has ordinal alpha. So, in that case, your nomenclature cannot distinguish between these two rather different sorts of board.

    Notice, it would then be a mistake to assert that there is no upper right square on an alpha x beta board, because one of the boards thus picked out does have a highest column/row, namely the one whose highest column has ordinal alpha, and whose highest row has ordinal beta.

    On the other hand, if your talk of an alpha x beta board is meant to speak of a board whose highest column/row have the ordinals alpha and beta respectively, then in this case it would again be a mistake to say that there would be no upper right square. It is the square at column alpha, row beta.

    Finally, maybe the nomenclature is supposed to work differently for limit and non-limit ordinals. One might say that an alpha x beta board means a board with a) columns for every n<=alpha for non-limit alpha, and b) columns for every n<alpha for limit alpha; & ditto for rows. But this would not be quite happy either, since we would be skipping a board at every limit ordinal, namely the one whose highest column has ordinal alpha for limit alpha (ditto for rows).

    Maybe I am just trying to think too early in the morning…

  2. Actually, it’s just that an \alpha\times \beta board has a column for each ordinal \alpha' where 0\leq \alpha' < \alpha (and similarly for the rows with \beta).

    I believe that works for all cases, but I definitely should have made it more clear.

  3. In your discussion of non-non-increasing sequences I think you mean “min” instead of “max”.

  4. Quite right. Thanks for the correction.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s