Lecture on Combinatorial Games (First few chapters of Winning Ways) D. Sleator, October 2001

The Sprague-Grundy theory of impartial games gives an elegant way to evaluate sums of games. The sum of two games means the new game in which a move consists of picking a game to move in, then moving in that game. A player stuck with no move available loses. In Sprague-Grundy theory, we assign a number (call it the nimber) to any position in the game. Then we give an algorithm that takes as input the nimbers of two games, and computes the nimber of sum of these two games. The algorithm, of course, is nim addition.

In this lecture we attempt to generalize this theory to “partizan” games (as opposed to impartial games). In these games, there are different sets of moves available for each of the two players. Our goal will be to label such games with numbers, and then give an algorithm that lets us compute the number of the sum of two games.

We’ll only be partially successful. We will have to restrict the games somewhat in order to get the theory to work.

Let G be a game. Let the two players be called Left and Right. If Left were to move in G, left might have several options. Call them G_{1}^{L}, G_{2}^{L}, . . .. Let the set G^{L} = {G_{1}^{L}, G_{2}^{L} … }. Similarly, Right may have several options G^{R} = {G_{1}^{R}, G_{2}^{R} … }. This completely characterizes the game. So we write:

G = {G^{L}|G^{R}}

If G^{L} is the empty set, then Left loses when Left must move in the game G. Similarly for Right. This is how the outcome of the game is determined. We’ll also assume that a game ends in a finite number of moves.

The intuition of the labeling (numbering) we come up with will be that the number of a game is the number of moves advantage that Left has over Right in the game. And with the labeling we come up with summing games corresponds to just adding the numbers together. Let N(G) be the number assocated with G.

With this as a starting point, let’s try to evaluate some games. (The “value” of a game will be the number we assign to it, and by “evaluating” it we mean computing this value.)

What’s the value of G = {|}? (This is the game in which neither player has any moves available. So the next player to move loses.) If we add this game to any other game, we know that it cannot change the game at all, because it does not change the set of moves available to either player. Therefore we know that N(G) = 0. That is, (omitting N()):

{|} = 0

Actually, we can find a whole class of other games that must have value 0. Suppose we have ANY game G in which the next player to move can be forced to lose. It turns out that we must have N(G) = 0. Why? Consider any game H. What happens in G + H? Say Left going second in H has a winning strategy in H. Then Left can win in G + H by seeing which game Right moves in, and following the winning strategy in that game. Right will eventually get stuck with no moves, and Left will win. The same thing works if Left has a win going first in H, or Right has a win going first or second in H. Therefore, for our theory to work we know that the outcome of a game is not changed by adding G to it. This implies that N(G) = 0.

What about the game {0|}? (Note that we’ve used “0” to indicate a game of value 0, the simplest example being {|}.) In {0|}, Left can move and leave right looking at {|}, and Right has no move at all. Our guiding intuition that the value should be the number of moves advantage to left indicates that this game should have value 1.

{0|} = 1

By symmetry, we must have that:

{|0} = −1

We want addition to work, so this requires that:

{0|} + {|0} = 0.

This is of course, not the same game as {|}. But it does have the property that the first player to move in this game loses. So everything is consistent so far.

We can continue to build up games and their values. What about {1|}? This clearly has value 2, because Left can make two moves to Right’s zero. In general

{n|} = n + 1
{| − n} = −n − 1

What about the game {0|1}? What must its value be? (Perhaps working this out with hackenbush makes this easier to see, but we’ll proceed with the set notation.) Consider the following game:

G = {0|1} + {0|1} + {|0}

What happens if Right moves first? Ignoring identical alternatives, he has two options:

{0|1} + {0|1} + {|} –OR– {0|1} + 1 + {|0}

That is:

{0|1} + {0|1} –OR– {0|1} + 1 + −1

That is:

{0|1} + {0|1} –OR– {0|1}

In either case, Left wins. (In the choice on the right, Left moves and leaves Right with {|}, and in the left choice Left moves and leaves Right with {0|1}, which loses for Right).

Now, going back to G, what happens when Left moves first? Left has only one choice (eliminating symmetry), and leaves the following:

{|} + {0|1} + {|0}

That is:

{0|1} + {|0}

Now right has two choices:

{0|} + {|0} –OR– {0|1} + {|} = {0|1}

The choice on the left lets Right win, the other choice loses for Right, so he avoids it.

So game G has the property that whichever player starts that player loses. This means it must have value 0. Let x be the value of {0|1}. We know that

x + x + (−1) = 0

Therefore in order for our theory to work we have:

\{0|1\} = \frac{1}{2}

We can go on this way and derive more and more results like this. For example, you can prove that \{|4\} = 0, \{3|5\} = 4, \{3|4\} = 3+ \frac{1}{2}, etc. Instead, let’s just state the rule that defines these values, and prove the whole theory works with these values.

Definition of value of a game:

Say G = {G^{L}|G^{R}}. Recursively compute the values of each element of G^{L}, let the set of numbers that results be A. Similarly, compute B from G^{R}. Now A and B are sets of numbers. Define a = max(A) and b = min(B), with the convention that if A is empty a = −∞, and if B is empty b = ∞. We require that a < b. (Otherwise this procedure fails to assign a value to G.) Now the value of G is the “simplest” number in the open interval (a, b).

It remains to explain what “simple” means. The integers are the simplest numbers, with 0 being the simplest of all, followed by ±1 follwed by ±2 etc. After that comes the dyadic numbers, that is, rational numbers with powers of two in the denominator. The lower the power of 2 the simpler the number.

[There is a unique simplest number in any interval (a, b). Because if an interval contains two numbers of the same simplicity, then it also contains an even simpler number.]

Note that this definition requires that a < b, and it requires this recursively for all subgames of G. So, for example, this definition fails to assign a number go {0|0}, which is the game where the first player to move wins. This value of this game is not a number, and we denote it by ∗. We’ll talk more about games that don’t have numbers later.

Now our job is to prove that this way of assigning a value to a game has the sum property.

Theorem: Let G and H be games that have values, and let these values be g and h respectively. Then the game G + H has value g + h.

Proof: Let’s first look closely at the game that is the sum of G and H. Let G = {G^{L}|G^{R}} and H = {H^{L}|H^{R}}. What are the left sets of G+H? Left can choose an element of G^{L} and leave H intact, or Left can choose an element of H^{L} and leave G intact. The choices for Right are similar. Thus:

G + H = {G^{L} + H, G + H^{L}|G^{R} + H, G + H^{R}}

(Where by G^{L}+H we mean the union of (X +H) over all X that are elements of G^{L}.)

Let g^{L} and g^{R} and h^{L} and h^{R} be the values of the left and right sides of G and H respectively. That is, g^{L} = max(G^{L}) and g^{R} = min(G^{R}), etc. Then g is the simplest number in (g^{L}, g^{R}) and h is the simplest number in (h^{L}, h^{R}). Here’s a schematic diagram of the situation:

  ---(------|----)---------(--|---)----------(---(--|---))---
            g                 h                    g+h

The two parens to the left of g+h correspond to the options for Left: G^{L} +H (whose value is g^{L} + h) and G + H^{L} (whose value is g + h^{L}). The ones to the right of g + h are the choices for Right. (Note that this picture is logically correct, even if some of the parens are located at −∞ or ∞.)

Clearly g + h is in the range defined by these parentheses. We need to prove that g + h is the simplest number in that range.

We break the proof down into a number of cases (can this be avoided?).

Case 1: g and h are integers. If g + h = 0, we’re done, because 0 is the simplest number of all. If g + h > 0 then we know that one of g or h is positive, so assume wlog that h > 0. Therefore h^{L} is at most 1 below h. Therefore h^{L} + g is at most one below g + h. And g + h is the simplest number in the range. An analogous proof works if g + h < 0. This completes case 1.

Case 2: g is an integer, h is a dyadic number. g + h is also a dyadic number, with the same simplicity as h. In fact, the interval (h^{L} + g, h^{R} + g) is an identical copy of (h^{L}, h^{R}) when viewed in terms of the simplicities of the numbers in it. Therefore if h is the simplest number in (h^{L}, h^{R}), then g + h must be the simplest number in (g + h^{L}, g + h^{R}). (And the interval that we need to consider may even be smaller – it must be contained in (g^{L}+h, g^{R}+h) too, but this only further reduces the choices available.)

Case 3: g and h are both dyadic numbers with g simpler than h. Actually, the argument in case 2 works here too. Because the interval (h^{L} + g, h^{R} + g) is an identical copy of (h^{L}, h^{R}), as described above.

Case 4: g and h are both dyadic numbers of the same simplicity. In this case it turns out that g + h simpler than g and h (in fact it could be an integer). Now the interval (h^{L} +g, h^{R} +g) is an identical copy of (h^{L}, h^{R}) when viewed in terms of the simplicities of the numbers in it –EXCEPT– that g + h is simpler than g. Therefore, if g was the simplest in its interval, then g + h it’s certainly the simplest number in an even smaller interval around it.

QED.