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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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