II.2: Basics of Conway Games

Conway Notation
Working with Conway games is complicated, so we need some notation to make them easier to work with. To really understand a given position G, all we need to do is understand what positions Left can move to and what positions Right can move to; these are called the “left options of G” (resp. “right options”). Now traditionally, if we had an ordered pair of sets, it would be written like ({a,b,c},{x,y}). However, that’s a lot of brackets and the commas mean two different things, which is confusing. Instead, we’ll write things like G={a,b,c|x,y} for the position with left options a, b, and c, and right options x and y. Note that by definition of the negative of a game, -G={-x,-y|-a,-b,-c}.

In general, we may use symbols for sets of options, e.g. a general game G={Gℓ|Gr} whose set of left (resp. right) options is Gℓ (resp. Gr). This makes general arguments and recursive definitions easier to write. For instance, the negative of a game G={Gℓ|Gr} is defined recursively by -G={-Gr|-Gℓ} (where -Gr means the set of the negatives of the positions in Gr). In G+H, Left can either move in G or move in H, and similarly for Right. Thus, G+H={Gℓ+H,G+Hℓ|Gr+H,G+Hr}. Note that H and G are not sets. The Left-moves-first and Right-moves-first Simple versions of G={Gℓ|Gr} can be given recursively by LeftFirst(G)={RightFirst(Gℓ)|RightFirst(Gℓ)} and RightFirst(G)={LeftFirst(Gr)|LeftFirst(Gr)} etc.

When using this notation, it would be annoying if we always had to keep track of the differences between equivalent positions. Luckily, we can generalize the lemma for the Sprague-Grundy theorem at the beginning of I.5:

1. If Gℓi=Hℓi for all i and Grj=Hrj for all j, then G:={Gℓ1,Gℓ2,…|Gr1,Gr2,…}=H:={Hℓ1,Hℓ2,…|Hr1,Hr2,…}.
Why? Let’s play G-H=G+(-H)={Gℓ1,Gℓ2,…|Gr1,Gr2,…}+{-Hr1,-Hr2,…|-Hℓ1,-Hℓ2,…} with you going first. If you’re Left and you move to Gℓi-H or you’re Right and you move to G-Hℓi, I’ll move to Gℓi-Hℓi which is a P-position since Gℓi=Hℓi. Similarly for the other two cases. Since I can always move to a P-position, G-H is a P-position, and G=H. ✓

Now that we have a way of writing things down and are sure that for most purposes we only have to worry about positions up to equivalence, let’s look at some simple Conway positions.

Integers
The simplest position of all is {|}, where neither Left nor Right have any legal moves (the P-position). This game was denoted [0] before, but we’ll just call it “0”; note that -0={|}=0. With this in hand, we can build some new positions: {0|} is the position where Left has one available move (which ends the game), and Right can’t move at all. {0|} is traditionally denoted “1”, and it’s the simplest L-position. Now, -1={|-0}={|0} is the same thing except Right has the move, not Left. 1+1={0|}+{0|} is a game where Right has no moves, and Left’s only moves turn one component into 0, which turns the whole game into 1. Thus, 1+1={1|}; this is called “2”. Similarly, “3” denotes 2+1={1|}+{0|}={{1|},{0|}+{0|}|}={2,1+1|}={2|}, and so on. In general, if n is a nonnegative integer, then n+1={n|} is an L-position. Similarly, if n is a nonnegative integer, then -n-1={|-n} is an R-position.

Some N-positions
Another position we can build from 0 is {0|0}. This is a game in which either player has a game-ending move, and no other moves. We already had a name for this before: [1]. However, to make CGT things readable, I’ll introduce Conway’s notation for this position: “*” (read “star”). {0,*|0,*} is a position where both players can move to *, or move to 0. We called this [2] before, but now we’ll call it “*2” (“star two”). Analogously, *3={0,*,*2|0,*,*2}=[3], etc. All of these stars are N-positions.

Another bunch of N-positions are written with a ±, and are special cases of a type of position called a “switch”. ±1:={1|-1} is a position in which if Left gets to move first, they secure a future move for themselves, and similarly for Right. Analogously we have ±n:={n|-n} for any positive integer n.

Equivalent positions?
There’s a whole menagerie of other positions I haven’t mentioned, but I want to point out that some of the positions you might build are equivalent to others we’ve discussed. For example, {-1|1} (not to be confused with ±1={1|-1}) is a game in which Left’s only move gives Right a move, and vice versa. In detail: If Left goes first, they move to -1={|0} and then Right moves to 0 and Left loses. Similarly, Right loses if they go first. Thus, {-1|1} is a P-position, and hence {-1|1}=0. In general, {-n|m}=0 for positive integers n and m. Another bunch of positions you might worry about are ones in which both Left and Right can move to the same bunch of stars (or zero), e.g. {0,*,*2,*5|0,*,*2,*5}. In such a case, the Sprague-Grundy theorem tells us that the position is the mex of the stars: {0,*,*2,*5|0,*,*2,*5}=*3, etc. We’ll find some more general techniques for simplifying Conway positions later.

Solutions to Exercise from II.1

L+L=L
In either component, Left has a winning strategy whether they go first or second. All they have to do is always respond (appropriately) immediately in the same component that Right plays in (if Right were to get two consecutive moves in the same component, the strategy goes out the window).
R+R=R is exactly analogous.

N+L=NL
Left can win in the sum if they play first by playing first in N, and then responding to each move of Right’s in the same component they move in. Thus, N+L is either N or L. Both are possible: *+1 is an L-position and (±1)+1 is an N-position.
N+R=NR is exactly analogous.

L+R can be any type.
2+(-1) is L, 1+(-2) is R, 1+(-1) is P, (1+*)+(-1) is N (note: 1+* is L).

N+N can be any type.
*+* is P, *+*2 is N (symmetric answer that takes a little thought to verify: both {1+*|-1} and {1+*|-1}+{1+*|-1} are N), (±1+1)+(±1) is L since ±1=-(±1) (symmetric answer: {2|-1} is N but {2|-1}+{2|-1} is L), similarly for R.

Next time: Fuzziness and the meaning of “G≤H”.

Advertisements

One thought on “II.2: Basics of Conway 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