II.3: An Order on Conway Games

Defining an Order
Now that we have verified the table of possibilities for adding games (at the end of II.1), and understand P-positions as “0”, we can note a couple things: An L-position plus an L-position is another L-position. The negative of an L-position is an R-position (so not an L-position), and vice versa. This makes the L-positions kind of like positive numbers: When you add two positives you get a positive, and the negative of a positive is never positive. For this reason, we say that a Conway position is “positive” if it’s an L-position, and “negative” if it’s an R-position. Why not the other way around? There are good reasons for both choices, but this is the one that stuck (a later post will have a better reason for this one).

With the concept of positive in hand, we can go on to define > and ≥, etc. G>H when G-H is an L-position.G≥H when G>H or G=H (equivalently, when Left has a winning strategy when Right goes first in G-H.) Under these definitions, all of the regular inequalities with integers like “-2>-3” hold for the Conway position versions of them. Also, most of the basic facts about inequalities hold: G>H implies -G<-H, etc. Basically, G>H means something like “G is better for Left than H no matter who goes first”.

The order isn’t ideal
However, be warned: there are two things that “go wrong” compared to common inequalities you’re used to. Firstly, not every Conway position is positive (L-position), negative (R-position) or 0 (P-positions), so not every pair of positions is comparable. For instance, since * is an N-position, “*>0”, “*=0”, and “*<0" are all false! We write "*‖0" and say "star is incomparable with zero" or "star is fuzzy (with respect to zero)" or "star is confused with zero". Slightly confusingly for some programmers, the notation "*<>0″ is used sometimes for this “confused” relationship. The other main thing that goes wrong is that there are games like * and {1+*|-1} which aren’t nonnegative to begin with, but become nonnegative (or even positive, in the latter case) when you add them to themself: *+*=0, {1+*|-1}+ {1+*|-1}>0. In technical language, these Conway positions form a “perforated partially ordered abelian GROUP“.

More Confusion
To become a little more comfortable with this “confused” idea, let’s look more carefully at some familiar positions. *‖0, but how does * compare with 1? Well, in *-1, if Left goes first they move to -1, and then Right moves to 0 and wins (eventually, if Left happens to have moves in the particular representation of 0, like {-1|1}=0). If Right goes first then they move to -1 and win (eventually). Therefore *-1 is an R-position so *<1. Since -*=*, we have -1<* for free. So somehow, * occupies a rough position between -1 and 1, but it's confused with 0.

With ±1={1|-1}, there's even more confusion. If Left goes first in (±1)-1, they move to 1-1=0, and win. If Right goes first, they move to -1-1=-2, and win. Therefore, ±1-1‖0, so ±1‖1 (similarly, ±1‖-1). However, let's see how ±1 compares to 2: If Left goes first in ±1-2, their only move (up to equivalence) is to 1-2=-1, and they lose. If Right goes first, they move to -1-2=-3 and win. Either way Right wins, so ±1-2). You might visualize this as ±1’s location on a number line being unclear: like a cloud over the interval [-1,1], but definitely between -2 and 2. Analogously, ±n‖m for -n≤m≤n but ±n<m for m>n and ±n>m for m<-n.

II.2: Basics of Conway Games

Conway Notation
Working with Conway games is complicated, so we need some notation to make them easier to work with. To really understand a given position G, all we need to do is understand what positions Left can move to and what positions Right can move to; these are called the “left options of G” (resp. “right options”). Now traditionally, if we had an ordered pair of sets, it would be written like ({a,b,c},{x,y}). However, that’s a lot of brackets and the commas mean two different things, which is confusing. Instead, we’ll write things like G={a,b,c|x,y} for the position with left options a, b, and c, and right options x and y. Note that by definition of the negative of a game, -G={-x,-y|-a,-b,-c}.

In general, we may use symbols for sets of options, e.g. a general game G={Gℓ|Gr} whose set of left (resp. right) options is Gℓ (resp. Gr). This makes general arguments and recursive definitions easier to write. For instance, the negative of a game G={Gℓ|Gr} is defined recursively by -G={-Gr|-Gℓ} (where -Gr means the set of the negatives of the positions in Gr). In G+H, Left can either move in G or move in H, and similarly for Right. Thus, G+H={Gℓ+H,G+Hℓ|Gr+H,G+Hr}. Note that H and G are not sets. The Left-moves-first and Right-moves-first Simple versions of G={Gℓ|Gr} can be given recursively by LeftFirst(G)={RightFirst(Gℓ)|RightFirst(Gℓ)} and RightFirst(G)={LeftFirst(Gr)|LeftFirst(Gr)} etc.

When using this notation, it would be annoying if we always had to keep track of the differences between equivalent positions. Luckily, we can generalize the lemma for the Sprague-Grundy theorem at the beginning of I.5:

1. If Gℓi=Hℓi for all i and Grj=Hrj for all j, then G:={Gℓ1,Gℓ2,…|Gr1,Gr2,…}=H:={Hℓ1,Hℓ2,…|Hr1,Hr2,…}.
Why? Let’s play G-H=G+(-H)={Gℓ1,Gℓ2,…|Gr1,Gr2,…}+{-Hr1,-Hr2,…|-Hℓ1,-Hℓ2,…} with you going first. If you’re Left and you move to Gℓi-H or you’re Right and you move to G-Hℓi, I’ll move to Gℓi-Hℓi which is a P-position since Gℓi=Hℓi. Similarly for the other two cases. Since I can always move to a P-position, G-H is a P-position, and G=H. ✓

Now that we have a way of writing things down and are sure that for most purposes we only have to worry about positions up to equivalence, let’s look at some simple Conway positions.

Integers
The simplest position of all is {|}, where neither Left nor Right have any legal moves (the P-position). This game was denoted [0] before, but we’ll just call it “0”; note that -0={|}=0. With this in hand, we can build some new positions: {0|} is the position where Left has one available move (which ends the game), and Right can’t move at all. {0|} is traditionally denoted “1”, and it’s the simplest L-position. Now, -1={|-0}={|0} is the same thing except Right has the move, not Left. 1+1={0|}+{0|} is a game where Right has no moves, and Left’s only moves turn one component into 0, which turns the whole game into 1. Thus, 1+1={1|}; this is called “2”. Similarly, “3” denotes 2+1={1|}+{0|}={{1|},{0|}+{0|}|}={2,1+1|}={2|}, and so on. In general, if n is a nonnegative integer, then n+1={n|} is an L-position. Similarly, if n is a nonnegative integer, then -n-1={|-n} is an R-position.

Some N-positions
Another position we can build from 0 is {0|0}. This is a game in which either player has a game-ending move, and no other moves. We already had a name for this before: [1]. However, to make CGT things readable, I’ll introduce Conway’s notation for this position: “*” (read “star”). {0,*|0,*} is a position where both players can move to *, or move to 0. We called this [2] before, but now we’ll call it “*2” (“star two”). Analogously, *3={0,*,*2|0,*,*2}=[3], etc. All of these stars are N-positions.

Another bunch of N-positions are written with a ±, and are special cases of a type of position called a “switch”. ±1:={1|-1} is a position in which if Left gets to move first, they secure a future move for themselves, and similarly for Right. Analogously we have ±n:={n|-n} for any positive integer n.

Equivalent positions?
There’s a whole menagerie of other positions I haven’t mentioned, but I want to point out that some of the positions you might build are equivalent to others we’ve discussed. For example, {-1|1} (not to be confused with ±1={1|-1}) is a game in which Left’s only move gives Right a move, and vice versa. In detail: If Left goes first, they move to -1={|0} and then Right moves to 0 and Left loses. Similarly, Right loses if they go first. Thus, {-1|1} is a P-position, and hence {-1|1}=0. In general, {-n|m}=0 for positive integers n and m. Another bunch of positions you might worry about are ones in which both Left and Right can move to the same bunch of stars (or zero), e.g. {0,*,*2,*5|0,*,*2,*5}. In such a case, the Sprague-Grundy theorem tells us that the position is the mex of the stars: {0,*,*2,*5|0,*,*2,*5}=*3, etc. We’ll find some more general techniques for simplifying Conway positions later.

Solutions to Exercise from II.1

L+L=L
In either component, Left has a winning strategy whether they go first or second. All they have to do is always respond (appropriately) immediately in the same component that Right plays in (if Right were to get two consecutive moves in the same component, the strategy goes out the window).
R+R=R is exactly analogous.

N+L=NL
Left can win in the sum if they play first by playing first in N, and then responding to each move of Right’s in the same component they move in. Thus, N+L is either N or L. Both are possible: *+1 is an L-position and (±1)+1 is an N-position.
N+R=NR is exactly analogous.

L+R can be any type.
2+(-1) is L, 1+(-2) is R, 1+(-1) is P, (1+*)+(-1) is N (note: 1+* is L).

N+N can be any type.
*+* is P, *+*2 is N (symmetric answer that takes a little thought to verify: both {1+*|-1} and {1+*|-1}+{1+*|-1} are N), (±1+1)+(±1) is L since ±1=-(±1) (symmetric answer: {2|-1} is N but {2|-1}+{2|-1} is L), similarly for R.

Next time: Fuzziness and the meaning of “G≤H”.

II.1: Introduction to Partizan “Conway Games”

In I.1, we talked about Simple games, but the field of Combinatorial Game Theory didn’t really come into its own until Conway’s work on a more general class of games. Since he pioneered the study of these games, I’ll call these “Conway games”. As with Simple games, a Conway game:

  1. is two-player.
  2. is “normal play”, meaning when someone has no legal moves, they lose. (If a player with no legal moves were to win instead, it would be “misère play”.)
  3. has no ties; the only way for the game to end is for someone to lose/win.
  4. is “non-loopy”, meaning the game definitely ends; it can’t go on forever.

However, instead of being impartial, they’ll be “partizan”, so that in a given position, the moves available (right now) to one player might not be the same as the moves available to the other player. As with Simple games, we may occasionally (especially later on) impose the “short” condition (meaning there are finitely many different positions reachable), as it won’t affect much of the general theory as long as we keep the other conditions (2-player, normal-play, no ties, non-loopy). To begin with, we’ll try to reproduce some of the basic results we had for impartial/Simple games; maybe we can even get to something like the Sprague-Grundy theorem (not gonna happen).

The first thing we need to check is the existence of a winning strategy for someone. In a partizan game, the players are distinguished in the moves they can make: we’ll call them Left and Right. If you take a Conway game and add a switch that says “Left moves now” on one side and “Right moves now” on the other and stipulate a starting position for it, then the game effectively becomes Simple. We know that Simple games have a strategy for the “Next” player or the “Previous” player, so for a Conway game position there are four possibilities which need names:

  1. Both Left-goes-first and Right-goes-first are N-positions. We’ll call this an N-position since the next player to move wins no matter if they’re Left or Right.
  2. Both are P-positions. We’ll call this a P-position.
  3. Left-goes-first is an N-position and Right-goes-first is a P-position. We’ll call this an L-position, since Left has a winning strategy no matter who goes first.
  4. The remaining case is an R-position.

In chess, a position where White (call them Left) is strong even if Black (Right) gets the next move may be an L-position. The initial board setup may be an N-position (if the person who goes first wins even if it were Black). If you’ve heard of trébuchet, those are P-positions.

Now that we have our types of positions, we can use it to define a sort of equivalence. If G and H are two Conway game positions, we’ll define G+H to be the “(disjunctive) sum” position: you can move in either component if you have a legal move there (this is actually the same definition as the ⊕ combination from before). We’ll say that G1 and G2 are equivalent if G1+H is always the same type of position (N or P or L or R) as G2+H, for any Conway game position H; we write G1=G2 if they’re equivalent.

If adding a physical switch turns a Conway game into two Simple games, why do we study Conway games at all? Suppose a Conway game splits into a sum (similar to isolated regions in Go): G=H+J. Then if Left moves in H, Right in J, and Left in H again, Left would have made two consecutive moves in H, and that possibility would be lost by only considering the two corresponding simple game versions of H.

It may be instructive to compare/contrast the following results with those about Simple games from I.4.

1. If G1=G2 then G1+H=G2+H for any H.
The proof is identical to the Simple game case: For each H, we can say that for any H’, (G1+H)+H’=G1+(H+H’) has the same winner as G2+(H+H’)=(G2+H)+H’. ✓

2. All P-positions are equivalent!
This is a little complicated. Suppose G is a P-position. If H is a position where Left wins going second (i.e. either a P-position or an L-position), then if Left goes second in G+H, Left has a response in each component for any moves that come up, so Left will win. Hence “H is P or L implies G+H is P or L.” If H is a position where Left wins going first (i.e. either an N-position or an L-position), then if Left goes first in G+H, they can make their first move in H, and then respond to every subsequent move in the same component their opponent moved in. Hence “H is N or L implies G+H is N or L.” Similarly, we have those same implications where L is replaced with R. These four implications show that a P-position like G does not change the winner of H (e.g. If H is an L-position, then both “N or L” and “P or L” are true of H, and hence are true of G+H, which forces G+H to be an L-position too.). Since any P-position doesn’t change the winner of a game, two P-positions have the same result (no change) when added to a game, so they must be equivalent. ✓

The next thing we’d want to do is copy the G⊕G=[0] result. The problem is that if G is, say, a Checkers/Draughts position where Right’s pieces are blocked but Left could still move, then there’s no way for Right to play some sort of “copy moves in the other component” strategy in G+G. We need to fix this by introducing some symmetry: The “negative” of a Conway position G, denoted “-G” is just like G, except in -G, Left can move to the negatives of the positions Right could move to in G, and vice versa. (This definition is recursive, but since Conway games are non-loopy, that’s not a real problem.) To simplify notation, “G-H” will denote “G+(-H)”.

3. G-G=[0]=0 for any G.
Why? Since the roles are reversed in -G, no matter who goes first in whichever component, the other player can always copy the move in the other component. Therefore, G-G is a P-position. Since all P-positions are equivalent, we can just write G-G=[0]. To simplify matters/make it look more like regular arithmetic, we’ll just write G-G=0. ✓

4. If G-H is a P-position, then G=H (and vice versa).
Why? By 2, G-H=0. By 1, G-H+H=0+H=H. By 3, G-H+H=G+(-H)+H=G+H-H=G+0=G. Putting the previous two equations together, we have G=H. For the “vice versa” part, if G=H, then G+(-H)=H+(-H) by 1, so G-H=0 by 3, so G-H is a P-position, by 2. ✓

By splitting ⊕ into the operations + and – (for a Simple game those operations are identical), we were able to recover a nice test for equivalence of Conway positions. In the Simple game case there were few enough types of positions that all the possibilities for sums came up naturally in the discussion. Here, there are many cases, so I’ll use a table (“NX” means “N-position or X-position”, “?” means any of the four types of positions are possible.):

+. P L R N
..---------
P| P L R N
L| . L ? NL
R| . . R NR
N| . . . ?

Our argument that all P-positions are equivalent was essentially a proof of the correctness of the first line of this table.
Exercise: Prove the correctness of the rest of the table. (Solutions in II.2.)

Disclaimer: There are a ton of small facts/things to check that I’ll gloss/skip over. For example, one that’s not too hard to check is “-(A+B)=(-A)+(-B)”; if there’s any detail like this you’d like to see checked, I would be happy to do so, but I skip these things for a bit of increased readability (while still proving a lot of the important stuff, some of which is glossed over in some major sources).

I.7: A Strategy for Kayles (Guy-Smith Periodicity)

Firstly, some more terminology: Now that we have the Sprague-Grundy theorem, we know every Simple game position is equivalent to a Nim pile [n] for some n. If H is the position, we’ll call the corresponding n the “Grundy value” G(H) (sometimes called “Nim value”). Note that by the theorem about combinations of piles of Nim, G(H1⊕H2)=binary xor of G(H1) and G(H2). With all the equivalences floating around, it doesn’t harm us to use ⊕ to mean binary xor when we’re dealing with numbers, so we may write G(H1⊕H2)=G(H1)⊕G(H2).

As promised, we’re going to find the Grundy values for positions in Kayles. Since the i notation doesn’t generalize nicely, and we have theorems about combinations of positions, I’ll introduce the standard notation Kn for a row of n pins in Kayles. Note that every Kayles position is a ⊕ combination of some Kn‘s, for various n.

From the proof of the Sprague-Grundy theorem (and the rules of Kayles telling us what positions we can get to), G(K5)=mex( G(K4), G(K3), G(K1)⊕G(K3), G(K2)⊕G(K2), G(K1)⊕G(K2) ), so that if we had already calculated the Grundy values for the smaller rows of pins (in this case we did: They were 0,1,2,3,1, respectively), then it’d be a straightforward calculation. You can do this sort of recursive calculation by hand (as it was first done), or with a computer. When you do so, you’ll get the following table for K12a+b (organized like that for convenience):

\ b 0 1 2 3 4 5 6 7 8 9 10 11
a . . . . . . . . . . . . .
0 . 0 1 2 3 1 4 3 2 1 4 2 6
1 . 4 1 2 7 1 4 3 2 1 4 6 7
2 . 4 1 2 8 5 4 7 2 1 8 6 7
3 . 4 1 2 3 1 4 7 2 1 8 2 7
4 . 4 1 2 8 1 4 7 2 1 4 2 7
5 . 4 1 2 8 1 4 7 2 1 8 6 7
6 . 4 1 2 8 1 4 7 2 1 8 2 7
7 . 4 1 2 8 1 4 7 2 1 8 2 7
8 . 4 1 2 8 1 4 7 2 1 8 2 7
9 . 4 1 2 8 1 4 7 2 1 8 2 7
10. 4 1 2 8 1 4 7 2 1 8 2 7
11. 4 1 2 8 1 4 7 2 1 8 2 7
12. 4 1 2 8 1 4 7 2 1 8 2 7
13. 4 1 2 8 1 4 7 2 1 8 2 7
14. 4 1 2 8 1 4 7 2 1 8 2 7

Notice that after K71 (actually after K70) it repeats the same cycle of 12 values for a long time. Normally in math, we have to resign ourselves to the fact that a pattern repeating for a finite bunch of time like this doesn’t constitute proof that the pattern would continue forever. However, for certain Simple games, it does! To see when and why, we need to introduce a class of Simple games that’s easy to work with:

Kayles and Nim are examples of a special type of Simple game called an octal game. This is a silly name because it comes from notation, not a property of the game, but it stuck. Basically, in an octal game, there are piles of objects, and for each number you want to remove from a pile: you may or may not be allowed to remove a whole pile of that size (i.e. remove that number from the pile and leave zero piles left), you may or may not be allowed to remove that number from a pile of bigger size (i.e. remove that number from the pile and leave one pile left), and you may or may not be allowed to remove that number from a pile and split the remains into two separate piles (as comes up in Kayles).

This is a lot of data about the rules of a game, so there’s a tidy notation for it (based on the connection between binary and base 8, hence octal). For each number of objects we might want to remove, we write a digit from 0 to 7, representing what’s allowed, with the 20 bit representing if leaving 0 piles is allowed, the 21 bit representing if leaving 1 pile is allowed, and the 22 bit representing if leaving 2 piles is allowed.

This might still not make sense, but a few examples will clear it up. In Kayles, you can remove one or two pins from a pile (but no more), leaving 0, 1, or 2 piles left. Therefore, the sequence would be (1+2+4),(1+2+4),0,0,0,…, and Kayles is more traditionally written in octal notation “.77”. In Nim, you can remove any number of things from a pile, but you can only leave 0 or 1 piles behind when you do so (you can’t split up a pile), so Nim is (1+2),(1+2),…, which is written “.333…”. In “.6”, since 2+4=6, you can remove only one from a pile at a time, and when you do so you have to leave stuff behind (in one or two piles). Amusingly, in this octal notation, “.0777…” (like Kayles but you can remove any number except 1 from a pile) and “.1” (the game where you can remove piles of size 1 and do nothing else) are not the same game.

Octal games are nice because you just need to calculate the Grundy values for single pile positions, and binary xor takes care of every other position. But how can we do something like this? Well, in practice, many octal games with a finite presentation (so games like Kayles .77 and .6, but not Nim, since .333… goes on forever) appear to have Grundy values that eventually repeat like those we found for Kayles. The “Guy-Smith periodicity theorem” ensures that these patterns will repeat forever if they go on long enough. Specifically, if the Grundy values repeat for as long as they weren’t repeating, plus two more cycles, plus a few more terms (as many as you’re allowed to take from a pile), they’ll repeat forever. More formally:

1. In an octal game with last non-zero code digit in the kth spot, where Hn represents a single pile of size n, and for some period p>0 we have G(Hn+p)=G(Hn) for all n with i≤n<2i+p+k, then G(Hn+p)=G(Hn) for all n≥i
Why? An intuitive summary of the proof is that since there’s only so many we can remove from a pile at a time, the bigger of the (at most) two chunks we leave when we make a move is big enough that periodicity can apply to it (by induction).

First note that k is the largest amount of things you can take from a pile, and since we’re playing an octal game piles won’t be split up into more than two piles. Therefore, a move from Hj is necessarily to a position of the form Ha⊕Hb where j-k≤a+b<j (if you leave only one pile, then one of a and b will be zero, and if you wipe out a pile, they both will be).

Now our goal is to show that G(Hn+p)=G(Hn) for all sufficiently large n. We can show this with a (strong) induction. By hypothesis, we already know the result for n<2i+p+k, so assume n≥2i+p+k and that we know the result for all relevant values below n. Since n≥2i+p+k, we have (n+p)-k≥2(i+p). By the remark of the previous paragraph, if you can move from Hn+p to Ha+Hb, then n+p>a+b≥(n+p)-k≥2(i+p), so that at least one of a and b is at least i+p (and less than n+p); call the bigger one b, so that i≤b-p≤n. By the inductive assumption, G(Hb-p)=G(Hb). Thus, G(Ha)⊕G(Hb-p)=G(Ha)⊕G(Hb). Since G(Hn+p) and G(Hn) are computed as the mex of values of the form G(Ha)⊕G(Hb) and G(Ha)⊕G(Hb-p), respectively, they must be equal, as desired. ✓

The above treatment was essentially taken from Aaron Siegel’s lecture notes.

Since Kayles is 0.77, k=2. Since Kayles started its pattern with K71, i=71. Since Kayles repeats every 12 in its pattern p=12. Therefore, we only need to check that G(Kn)=G(Kn+12) for n<2*71+12+2=156. In other words, if the pattern continues through K156+12=K168, then we know the Grundy values must repeat forever. But that’s exactly what the table from earlier shows! With this in hand, playing Kayles is now pretty trivial for a computer: (eventual) periodicity makes all of the Grundy values of individual piles quick to check, and the binary xor fact from Nim makes it easy to see the values of all of the potential moves (so you can find one with the value 0, if it exists).

Now, as I said, a lot of octal games with finite representations are eventually periodic (and thanks to the periodicity theorem it’s easy to discover a lot of them with a computer). For example, .106 eventually gets into a pattern with period 328226140474 after fumbling around for the first 465384263797 values. However, there are bunch of octal games that we don’t know whether or not their Grundy values are periodic. The most striking example is the game .6: the game in which you can take one object from any pile with more than one object and optionally split up the remains of the pile into two piles. Using some good coding and some techniques/theorems I won’t get into, the first 229 Grundy values of .6 have been calculated, but no periodicity has emerged, and no one has any idea how to prove non-periodicity for a single octal game with a finite code.

There are other things that can be said about Simple games:

  • What happens if the octal code isn’t finite? Then the differences between consecutive terms tends to be eventually periodic.
  • What about “hexadecimal games” where you can break piles into three? Occasionally the differences between consecutive terms are eventually periodic, but often the sequences of Grundy values are just crazy.
  • What about Grundy’s game where your only move is to break a pile into two piles of distinct sizes without removing anything? It’s conjectured to be periodic.
  • What about other classes of Simple games or nice subclasses of octal games? There’s a lot of other stuff known.

But I think that’s enough for now.

I.6a: The Nimber FIELD

This post is going to rely on more background than my average posts. In particular, facts about finite fields and ordinals will come into play. If you don’t know about these things at all, don’t worry, they won’t be necessary for I.7, etc. As a disclaimer, a good portion of this post is coming from Conway’s excellent, if slightly inaccessible, On Numbers and Games.

As discussed before, ⊕ (binary xor) makes ω (the set of nonnegative integers) into an abelian group of order 2. Also, by the rules of Nim and the Sprague-Grundy theorem, we know that p⊕q=mex({p’⊕q,p⊕q’:p'<p,q'<q}). To go along with this, there is a nice multiplication operation, similarly defined: p⊗q=mex({(p'⊗q)⊕(p⊗q')⊕(p'⊗q'):p'<p,q'<q}). It's easy to show (as in, it requires no background other than definitions) that ⊕ and ⊗ make ω into a commutative ring with 1. With a terrible bit of induction, it can be shown that 22n⊗22m is their regular product if n≠m, and is 3*22n/2 if n=m. With this in hand, you can show (in a terribly ugly way) that if you use these operations on the set of numbers below a “Fermat 2-power” 22n, you actually have a finite field! Thus, ω is the direct limit (think “union”) of the finite fields of size 22n. ω is not an algebraically closed field, though.

Since the ordinals are well-ordered, the mex definitions for ⊕ and ⊗ extend just fine to the class of all ordinals, On. When we give it the operations ⊕ and ⊗, the same proof that ω became a commutative ring works: On becomes a commutative RING with 1 (in fact it becomes an algebraically closed FIELD), denoted On2. A technical note: On is a proper class, not a set, so it can’t really be a ring or a field; the capitalization of “RING” and “FIELD” in the previous sentence is a standard way to represent this distinction.

As mentioned in I.6, ⊕ works essentially the same way in the infinite case as it did in the finite case: like binary xor. ⊗ in the infinite realm will be a little weirder; the pattern for finite numbers doesn’t really continue in any meaningful way. We can still get some preliminary results to help us understand things.

n⊗ω=nω for finite n.
Why?
We’ll prove it by induction on n; it’s trivial for n=0. By definition, n⊗ω=mex({(m⊗ω)⊕(n⊗o)⊕(m⊗o):m<n,o<ω}). By inductive hypothesis, m⊗ω=mω for any m<n, so we have to deal with mex({(mω)⊕(n⊗o)⊕(m⊗o):m<n,o<ω}). Consider a Fermat 2-power above n. Then the set of numbers below that form a field, so for any choice of m, we can solve the equation (n⊗o)⊕(m⊗o)=x for o. Since m and x are arbitrary, any ordinal less than nω is in the set (and no others), so the mex is just nω, as desired. ✓

ω⊗ω=ω2.
Why?
By definition, ω⊗ω=mex({(m⊗ω)⊕(ω⊗n)⊕(m⊗n):m,n<ω}). From the previous fact and the commutative ring structure of On2, this is mex({(m⊕n)ω+(m⊗n):m,n<ω}). To see that this is ω2, we must show that m⊕n and m⊗n are independently arbitrary. I.e. we need to be able to solve m⊕n=x and m⊗n=y for m and n. This system reduces to a quadratic in m, and we can solve any desired quadratic in a sufficiently big finite field of characteristic 2. ✓

ω⊗ω2=2.
That’s not a typo. Why?
By definition, ω⊗ω2=mex({(n⊗ω2)⊕(ω⊗(pω+q)⊕(n⊗(pω+q):n,p,q<ω}). Collecting like terms and using previously shown facts, this reduces to mex({(n⊕p)⊗ω2⊕(q+n⊗p)ω⊕n⊗q:n,p,q<ω}). If the expression inside the set is finite, then there must be no ω2 term, so n⊕p=0 so n=p. Similarly, there must be no ω term so q=n⊗p=n⊗n. Thus, the only finite numbers attainable are those of the form n⊗q where q=n⊗n. 0=0⊗0⊗0, so it’s not the mex, and similarly for 1. The question boils down to “does 2 have a cube root in any of the finite fields of size 22k?” Since 2⊗2⊗2=1, the question becomes “does 1 have any primitive 9th roots in one of those fields?” Since the multiplicative groups are cyclic, and 22k is never 1 modulo 9, the answer is no, and the mex is just 2, as desired. ✓

Very do-able exercise (but requiring some background): What are the other cube roots of 2?

At the beginning of this post I alluded to some inelegant inductions to prove some of the basic facts, and haven’t provided any justification at all for claims like “On2 is a FIELD“. Almost everything you need to know about On2 actually follows from a beautiful collection of theorems I’m quoting straight from Conway (after dealing with notation differences) which aren’t terribly hard to prove (once you know the statements), but which I won’t spend time proving here. Be warned, Δ and Γ are ordinals playing double-duty as both an ordinal and the set of all lower ordinals; also, I’ll use α⊗3 to denote α⊗α⊗α, etc.

  • If Δ is not a group under ⊕, then Δ=α⊕β, where (α,β) is the lexicographically earliest pair such that α⊕β is not in Δ.
  • If Δ is a group under ⊕, then Δα⊕β=Δα+β for all α and all β∈Δ
  • If Δ is a group under ⊕ but not a ring with ⊗, then Δ=α⊗β, where (α,β) is the lexicographically earliest pair such that α⊕β is not in Δ
  • If Δ is a ring, and Γ≤Δ is an additive subgroup all of whose non-zero elements have ⊗-multiplicative inverses in Δ, then Δ⊗γ=Δγ for all γ∈Γ.
  • If Δ is a ring, but not a field, then Δ is the multiplicative inverse for the smallest element α of Δ without an inverse in Δ
  • If Δ and α are as in the previous line, and Γ is the largest ordinal≤α which is a group under ⊕, then (Γ is a field and) Δ⊗n⊗γn⊕Δ⊗(n-1)⊗γn-1⊕…⊕Δ⊗γ1⊕δ=Δ(Γn-1γn+…+γ1)+δ for all n∈ω, all δ∈Δ, and all γ01,…γn∈Γ. (This one is actually a little subtle; Conway’s proof contains an error that was patched by Lenstra.)
  • If Δ is a field but not algebraically closed, then Δ is a root of the lexicographically earliest polynomial having no root in Δ. [In the lexicographic order, we examine high degree coefficients first.]
  • If Δ is as in the previous line, and N is the degree of that “earliest” polynomial, then Δ⊗n⊗δn⊕…⊕δ0nδn+…+δ0 for all n<N and all δ0,…,δn∈Δ.
  • If Δ is an algebraically closed field, then Δ is transcendental over Δ and the previous equation holds for all n∈ω.

In Conway’s words, “Each ordinal Δ extends the set of all previous ordinals in the simplest possible way.” With this in hand it’s not to bad to prove things like “distinct powers of 2 add normally”. or ω⊗3=2, or anything else you’d want to know, really. There are more things that can be said about On2, but I’ll leave you with a couple more facts: (ω3)⊗3=ω and ωωω is algebraically closed.

Wait a second, if we have all of these fields, there’s gotta be a way to divide. In fact, finding inverses does not require trial and error. The inverse of p, call it q, is given recursively by q=:1/p= mex({0,((p’⊕p)⊗q’⊕1)⊗(1/p’):0<p'<p,q'<q}).

Since "q'<q" is part of the expression, it might not seem like this calculation can be done. Let’s calculate the inverse of 2. I’ll build up the list of things we’re taking the mex of recursively:
We know 0 is in there, so the mex is at least 1.
Since the mex is at least 1, we may take q’=0, and since p=2, p’ is always forced to be 1.
Thus, we also have in the set: ((1⊕2)⊗0⊕1)⊗(1/1)=1.
So the mex is at least 2, and we may take q’=1, yielding ((1⊕2)⊗1⊕1)⊗(1/1)=3⊕1=2.
So the mex is at least 3, and we may take q’=2, yielding
((1⊕2)⊗2⊕1)⊗(1/1)=3⊗2⊕1=(1⊗2)⊕(2⊗2)⊕1=2⊕3⊕1=1⊕1=0.
But we already knew 0 was in the set, so we can’t get anything new anymore, and 1/2=3.

With the previous calculation we’ve already multiplied 2⊗3 to get 1, so this calculation really worked. It takes a bit of thought to see why this weird recursive definition will always work. Incidentally, there’s a similar formula that gives the square root: r=√s= mex({√s’,(p⊗q⊕s)⊗(1/(p⊕q)):s'<s, and p,q<r distinct}). Both of these formulas (and perhaps the formula for ⊗ as well) seem to come out of nowhere without the context of the Surreal Numbers, which will be discussed in a much later post.

I.6: A Strategy for Nim

The Sprague-Grundy theorem in I.5 wasn’t known when Bouton first solved Nim, but we can use it to make solving Nim very approachable. We can begin by analyzing how Nim piles below [8] behave under ⊕.

First, remember [1,2,3]=([1]⊕[2])⊕[3] was a P-position, so [1]⊕[2]=[3]. Now consider [1,4,5]: If the next player to move doesn’t do something stupid (eliminate a pile or make two piles equal), then we can move to [1,2,3]. Thus, [1]⊕[4]=[5]. Also, if the next player to move in [2,4,6] doesn’t do something stupid, then we can either move to [1,4,5] or [1,2,3] so [2]⊕[4]=[6].

Finally, consider [1,2,4,7]. Eliminating a pile invites the opponent to make [1,2,3] or [1,4,5] or [2,4,6]. Making two piles equal invites the opponent to make the position something like [a,a,b,b], which is an obvious P-position. [1,2,3,7] and [1,2,4,3] invite [1,2,3], [1,2,4,5] invites [1,4,5], and [1,2,4,6] invites [2,4,6]. Thus, [1]⊕[2]⊕[4]=[7]. Therefore, for the powers of 2: 1,2,and 4, we know that ⊕ acts like addition for distinct powers of 2.

By writing things as sums of powers of 2, we can use this to calculate all of the combinations of Nim piles no bigger than [7]: e.g. [3]⊕[7]=([1]⊕[2])⊕([1]⊕[2]⊕[4])=([1]⊕[1])⊕([2]⊕[2])⊕[4]=[4]. If we conjecture that this pattern continues (distinct powers of 2 add normally), then ⊕ would be equivalent to bitwise xor. We can use induction to prove this is correct.

1. [m]⊕[2n]=[m+2n] if m<2n
Why?
Suppose, for sake of induction, that we have shown the claim for all lower n and for all lower m with the same value of n. If m=0 the claim is obvious. Otherwise, we must show that [m,2n,m+2n] is a P-position by showing how to respond to any move. A move to [m,2n,k] with k≥2n invites a move to [k-2n,2n,k] which is a P-position by inductive hypothesis. A move to [m,2n,k] or [m,k,m+2n] with k<2n invites a move to [m,xor(m,k),k] (modulo ordering), which is a P-position by expanding everything out as powers of two (by inductive hypothesis) and cancelling like powers. ✓

If you’re familiar with ordinals, this proof works verbatim in that generalized situation, although you have to invoke a special version of Cantor Normal Form (note that under ordinal exponentiation, 2ω=ω) to write an ordinal uniquely as a sum of distinct ordinal powers of 2.

With fact 1 in hand, a strategy for normal-play Nim presents itself, and can be described in a variety of ways. One way would be “write the pile sizes in base 2, add them up but with no carrying, and then make a move that changes precisely those bits that were 1 when you added things up”. If there were no such move, then all of the moves would be to N-positions, which would contradict either fact 1 or the Sprague-Grundy theorem. An explicit way to find such a move is essentially “Lemma 2” in this Wikipedia section.

So we now know that every Simple game is really a pile of Nim, and how to combine piles of Nim/play Nim perfectly. We haven’t solved every Simple game, though. For instance, if we want to play Kayles perfectly, we need to know “what Nim pile is n pins in a row equivalent to?” for all n. That’ll be covered in the next post.

I.5: Classification of Simple Games (The Sprague-Grundy Theorem)

To achieve the classification I mentioned at the end of I.4, we’ll need a lemma, which has the added benefit of helping me sidestep the issue that I haven’t formally written out what a “position” (of a Simple game) is, anyway.

1. If the set of immediately reachable positions from G is {G1,G2,…} and Gi=Hi for all i, then G is equivalent to any position H where the set of immediately reachable positions is {H1,H2,…}.
Why? Let’s play G⊕H. If you move to Gi⊕H or G⊕Hi, I’ll move to Gi⊕Hi which is a P-position since Gi=Hi. Therefore, G⊕H is itself a P-position, and G=H (by I.4.4).

This lemma basically solidifies the fact that we only care about positions up to equivalence. It will allow us to prove what I’d call the birth of CGT: The Sprague-Grundy Theorem (independently proven by Sprague and Grundy during the 30s). In I.4, we showed that the single pile positions of Nim were pairwise inequivalent. Sprague and Grundy showed:

2. Every Simple game position is equivalent to a single pile of Nim.
Every complicated game of Nim, every game of Kayles (on a circle or in a line), every common game (like Chess) turned into a Simple game,… they’re all equivalent to [n] for some n. This doesn’t mean it’ll be easy to calculate which [n] a given position is equivalent to, but we can worry about that later.

Proof of the Sprague-Grundy theorem:
For clarity, we’ll prove it in the case where the game is “short”, so that there a finitely many reachable positions in a given game. Since Simple games are non-loopy, a given starting position ends up at a position with no available moves after at most some fixed number of moves. Therefore, by the lemma (or perhaps by definition), we can just think of a Simple game as a list of reachable positions, each of which is a list of reachable positions, etc. with empty lists (or [0]’s, since all P-positions are equivalent) at the bottom (you can think of this as a tree if you like). This permits some form of induction (structural induction on trees, regular induction on the maximum number of moves until the game ends, whatever you like).

Base case: If there are no available moves, it’s a P-position, which is equivalent to [0].

Induction step:
Suppose that every available move in G is equivalent to a single pile of Nim. By our lemma, G is equivalent to a game H in which the moves are to [n1],[n2],…. We will show that such a game is equivalent to [m]=[mex(n1,n2,…)] where mex means “the minimal excluded number: the least nonnegative integer that’s not one of the ni“.

To do this, we need to play H⊕[m]. If you move to [ni] in H where ni<m, then I can move to [ni] in [m] and leave you with the P-position [ni]⊕[ni]. If you move to [n] in [m], then since m is the least excluded number, n=ni for some i, and I can still move to [ni]⊕[ni]. Finally, if you move to [ni] in H where ni>m (remember it can’t be equal to m since m was excluded), then I can just move to [m]⊕[m] since [m] is a smaller pile than [ni]. Since I can always hand you a P-position no matter what you do, H⊕[m] must be a P-position, and H=[m], as desired (since G=H). ✓

For those who happen to know about the ordinals, this proof works exactly the same way for Simple games that are not “short”, but then we’d need Nim “piles” for every ordinal.