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).

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