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 **ii**⊕**iii**, 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 G_{1} and G_{2} are “equivalent” if G_{1}⊕H is always the same type of position (*N* or *P*) as G_{2}⊕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 G_{1}=G_{2}.

A few observations:

**1. If G _{1}=G_{2} then G_{1}⊕H=G_{2}⊕H for any H.**

Why?

Because for each H, we can say that for any H’, (G

_{1}⊕H)⊕H’=G

_{1}⊕(H⊕H’) has the same winner as G

_{2}⊕(H⊕H’)=(G

_{2}⊕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?!

Pingback: II.1: Introduction to Partizan “Conway Games” | Combinatorial Games