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.

Advertisements

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.

I.4: Basic Combinatorial Theory of Simple Games

So, because I think it’s theoretically nicer to do things this way, and also perfect play for Nim is something some more people have seen before than any substantive CGT, I’m going to digress to talk about properties of all Simple games for a bit, and to get at why CGT has the word “combinatorial” in it.

Kayles positions are built up of rows of pins that are separated by space. On your turn, you basically move in any one of the rows of pins, ignoring the others. Nim positions are built up of piles of objects, and on your turn you take from one pile, ignoring the others. In general, positions in Simple games can be stitched together. If G and H are positions of any Simple games, then the combination (not a standard term) G⊕H will be the game in which, on your turn, you can move in either G or H (if there are any moves available).

In this way, ii.iii is basically the same as iiiii, and [1,2,3] is basically the same as [1,2]⊕[3]. But we can also build brand new positions like [1,2]⊕iii. “Basically the same” is a little vague, so we’ll say that two Simple game positions G1 and G2 are “equivalent” if G1⊕H is always the same type of position (N or P) as G2⊕H, for any Simple game position H. In other words, if two positions have the same effect in all combination positions, we’ll consider them equivalent, and write G1=G2.

A few observations:
1. If G1=G2 then G1⊕H=G2⊕H for any H.
Why?
Because 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!
Why?
Suppose G is a P-position. For one case, suppose H is a P-position too. Then G⊕H is a P-position since any time the next player moves in one of the two games, the opponent just makes the right response in that game (leaving it a P-position). If, instead, H is an N-position, then G⊕H is an N-position too: the next player to move simply makes the right first move in H (sending it to a P-position) and then we know that the combination of two P-positions is a P-position, so the opponent is doomed. ✓

So we now know things like [3,3]=[0]. If every N-position were equivalent, then this whole equivalence business would end up being a waste of time. Luckily, [1] and [2] are both N-positions, but [1]⊕[1] is a P-position while [2]⊕[1] is an N-position, so [1]≠[2]. In fact, [n]=[m] (the positions are equivalent) only if n=m (the naturals are equal).

3. G⊕G=[0] for any G.
Why?
If you’re next to play in G⊕G, then whatever moves you make, your opponent can just make the same move in the opposite copy of G. Therefore, G⊕G is a P-position. Since all P-positions are equivalent, we can just write this as G⊕G=[0]. ✓

(For the people with significant math background reading along, we’ve more or less shown that the set of equivalence classes of Simple game positions forms an abelian group of exponent 2 under the operation ⊕.)

4. If G⊕H is a P-position, then G=H (and vice versa).
Why?
By 2, if G⊕H is a P-position, then G⊕H=[0]. By 1, we have G⊕H⊕H=[0]⊕H=H (with the “=H” part following because there’s no moves in [0] to interfere with anything). By 3, 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⊕G=H⊕G by 1, so [0]=H⊕G by 3, so G⊕H is a P-position, by 2. ✓

Despite the fact that it came from some straightforward observations, 4 is actually a pretty amazing principle. We started out with a definition of equivalence that had us worrying about combining with all possible Simple game positions, and now we find that to check equivalence we only need to check who wins the combination position! Incidentally, none of the above requires the game to be “short”; the arguments work just fine even for games with infinitely many reachable positions.

Let’s put this to good use. Note that .=[0], i=[1], and ii=[2], just because for Kayles positions that small, the rules are basically the same as Nim.

Now, consider the position iii⊕[3], and you’re going first. If you move to iii⊕[2], I’ll move to ii⊕[2]=[2]⊕[2]=[2,2], which is a P-position. If you move to iii⊕[1], I’ll move to i⊕[1]. If you move to iii⊕[0], I’ll move to i.i⊕[0] and then you’ll hit one pin and I’ll hit the other and win. If you move in iii, I’ll make the corresponding Nim move in the previous list. In every case, I give you something that’s definitely a P-position, so iii⊕[3] is itself a P-position. By observation 4, iii=[3], even though the rules of Kayles and Nim are different!

Let’s see if this pattern continues. Consider the position iiii⊕[4], and suppose you’re going first and happen to move to iiii⊕[1]. Then if I move to ii.i⊕[1] or i..i⊕[1] or .iii⊕[1] or ..ii⊕[1], you’d respond with …i⊕[1] and I’d lose. If I move to iiii⊕[0], you’d respond with i..i⊕[0] and I’d still lose. Therefore, iiii⊕[4] is an N-position, but more importantly, iiii⊕[1] is a P-position. Thus, iiii=[1]≠[4].

Next time: A classification (“set of representatives”) of all equivalence classes for Simple game positions?!

I.3: Introduction to Nim

Nim is the most famous Simple game. Variants of it have been played for centuries and it is perhaps the first significantly interesting example of a solved game (Charles L. Bouton found out which positions were P-positions, and what winning moves would be for every N-position back in 1901, although he did not use these terms.).

In Nim, there are some piles of objects, and on your turn, you may remove any number (at least one) of objects from a single pile. Sometimes people call this game Nim even under misère play, but we will take Nim to have normal play (and hence a Simple game) where you lose when there are no objects for you to take on your turn.

Let’s analyze some small Nim positions to see how they should be played/which ones are P-positions and which ones are N-positions. I’ll list pile sizes in rectangular brackets.

[] (the position with no piles) or [0] (the position with one “pile” of size zero) is a P-position. If you’re faced with this at some point, you’ve already lost to the person who moved Previously, as per normal-play rules.

The single-pile positions [1],[2],[3],[4],… are all N-positions. If you’re Next to move, and faced with one of these, take the whole pile. You’ll leave your opponent with [] and they’ll lose.

Consider a two-pile position where the piles are equal, like [1,1], or [2,2], etc. In this case, you’re in trouble; it’s kind of like Kayles. Whatever moves you make in one pile can be mirrored by your opponent, so these are P-positions.

For a two-pile position where the piles are unequal, like [1,2], or [5,789]. You’re in good shape, because you can make the piles equal. Once you do, your opponent has just been handed a losing situation (because you’ll then go on to mirror their moves). Thus, these are N-positions.

Before considering bigger situations in Nim, I want to point out some more general facts about Simple games. The P-positions are the ones where you can only move to an N-position. Why? First assume you’re in a P-position. If you could move to another P-position, then by definition you could give you opponent a position where they had no winning strategy, but if you could do that, then doing so would win you the game! Therefore, you can’t possibly move to another P-position. Conversely, if all moves are to N-positions, then you’re forced to give your opponent the win, so you must be in a P-position. More pithily: If you’re losing a Simple game, all moves are bad, and if all moves are bad, you’re losing.

The contrapositive to the above statement is If you can move to a P-position, you must be in an N-position., so you don’t have to check full strategies if you have some table of what types of positions things are. Relatedly, From an N-position, the winning moves are the moves to P-positions. If you have control of the game, you have to make moves that don’t yield control to your opponent if you want to ensure you win.

Now let’s look at some three-pile positions in Nim. It doesn’t take too much work to see that positions where 2 pile sizes are repeated (like [2,5,5] or [4,4,4] or [1,1,7]…) are N-positions; in such a case, just take a pile that leaves two equal piles so it becomes a P-position.

What about the smallest three-pile position that’s not like that: [1,2,3]? If you kill a whole pile, you leave two unequal piles, so that you’ve handed your opponent an N-position. If you don’t kill a whole pile, you leave a pair of equal piles plus a third pile, which we just said was an N-position too! Since you can only move to N-positions, you must be in a P-position.

You can keep expanding this table by brute force: since [1,2,4],[1,3,4],[2,3,4],[1,2,5],… can be turned into [1,2,3], they must all be N-positions, etc. One would hope that there’s some pattern, some relatively quick way to just look at a three-pile Nim position and figure out whether it’s an N-position or a P-position. If we had such a method, then you could 1. test if you’re in an N-position, and if you are, 2. test all of the positions you can get to in one move to see which one(s) is/are P-position(s), so you know which is the winning move.

However, I’ll tell you right now: It’s really hard to come up with a method that works for all three pile positions on your own (but if you somehow do, you’ll probably be able to figure out how to handle all Nim positions, not just three-pile ones).

I know many of you have seen this before, but if you haven’t, try and play some three pile (or more!) Nim/make some tables to see if you can notice any patterns. Even if you don’t get a complete rule, maybe you can get some interesting general results. For instance, here’s one: if all three pile sizes are odd, it’s an N position!

I.2: Winning Strategies

In Introduction to “Simple Games”, I introduced the concept of a Simple game, and the example of Kayles. If you’re interested in playing Kayles, at least in a circle (instead of in a line), you can do so at cut-the-knot. In general, Kayles can be pretty tricky, but if you’re starting from a full row of pins, it’s comparatively easy. You may want to take some time now to figure out a strategy for that special case, before reading on.

Spoiler for Kayles when played on a complete row:
If the row is empty, you have no moves and you’ve lost. If the row is non-empty, then take the middle pin if the row has odd length, or the middle two pins if the row has even length. This splits the game into two separate identical non-interacting rows of pins. When your opponent moves in one, you mirror their move in the other. When they eliminate one of the equal rows, you’ll take the remaining pins and they’ll lose.

(If, as in the cut-the-knot game, the pins are in a circle, then after the first person takes a pin or two, the circle is just like a row of pins, so for three or more in a circle, the second player can always win.)

There’s a basic theorem of CGT that’s intuitively obvious to some, but bears explicit stating:
In a Simple game, one of the players has a winning strategy.

Now, if you want to be really rigorous about things, you have to lay out even more carefully what a Simple game is, and what a “strategy” is, but for now I’ll just say this: A “strategy” is like a partial lookup table that tells you what moves to make if you’re in a certain position. A “winning strategy” is a strategy that makes you definitely win the game, no matter what moves your opponent does.

I’ll sketch why this theorem is true, intuitively. Suppose that a position is such that the next player to move has no winning strategy. This means that no matter what strategy they employ, they can’t guarantee a win. If they can’t guarantee a win for any strategy, then after any first move, the second player must have some move that doesn’t let the first player guarantee a win. As long as the second player keeps playing these sorts of “blocking” moves, the first player won’t get a chance to win (since the game is non-loopy). This constitutes a winning strategy for the second player.

With this theorem in hand, we can say that every Simple game position is either an “N-position” (where the player to move next has a winning strategy), or a “P-position” (where the player who moved previously, or at least isn’t the one moving next, has a winning strategy).

This still works the same way even when the game is not “short”; it could have infinitely many reachable positions, as long as the game still ends in finite time. (And for similar reasons, if we drop “no ties”, then someone can at least force a tie, etc.)