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?!

Advertisements

One thought on “I.4: Basic Combinatorial Theory of Simple Games

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

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