Combinatorial Game Theory VI

Lesson 6

General Combinatorial Game Theory

[ Warning: the following lesson is significantly longer than the previous ones. ]

Starting from this lesson, we will look at a more rigourous, complete and general theory. Prior to this, in any game configuration both players have the same sets of moves available to them. These are called impartial games. Here, we will look at partial games, whereby a configuration has different options for either player. To distinguish our players, we will call them Left and Right. We will only look at finite games, i.e. we exclude loopy games and games with possible draws. To highlight our theory this week, we’ll introduce the game of Domineering:

Domineering

We have a union of unit squares. E.g.

Each player, at his turn, places a domino (1 × 2 piece) across two neighbouring squares such that no two dominoes may overlap. Left must place his vertically while Right places his horizontally. A player wins if his opponent has no legal move to make. To analyse this game further, let’s have a proper definition of the concept of “game”.

Definition

A game is described as two collections of options, one for Left and one for Right. Each option is in turn a game, so in this way we get a recursive definition of games. This is usually written in the following form:

$G = \{A, B, C, \ldots | X, Y, Z, \ldots \}$

where A, B, C, … are the possible configurations after Left makes a move, and X, Y, Z, … are the possible configurations after Right makes a move. For simplicity, we write 0 for the game { | }, where neither Left nor Right has any move available.

Example

Let’s consider the following Domineering game, with its options:

So the above game is $G = \{G_1, G_2 | G_3, G_4\}$ , where the games $G_1 = \{0 | \ \}$ , $G_2 = \{0 | 0 \}$ , $G_3 = \{\ | 0\}$ and $G_4 = \{\ | \ \} = 0$ . Note that the four games $G_1, G_2, G_3, G_4$ are all different. We can also write the game G in full as follows:

$G = \{ \{ \{ \ |\ \} | \ \}, \{ \{ \ | \ \} | \{ \ | \ \} \}\ |\ \{ \ | \{ \ | \ \} \}, \{\ | \ \} \}.$

But of course no one likes to deal with such unwieldy expressions.

Addition of Games

As before, we can add two games together. Recall the definition of game addition:

The sum of two games G and H is as follows: place G and H side-by-side. At each player’s turn, he must make a move from either G or H, but not both. The move must be legal in the individual game, but there are no constraints on which component to choose from. As before, a player wins if his opponent is left with no legal moves.

Here is an example of addition of two domineering games:

It is clear that addition satisfies:

existence of identity : for any game G, the game 0+G is identical to G;
commutativity : for any games G and H, the games G+H and H+G are identical;
associativity : for any games G, H and K, the games G+(H+K) and (G+H)+K are identical.

These are the common properties one would expect from addition.

Negative of Games

Next, we wish to define the negative of a game G.

Informally, the negative of a game G, written -G, is obtained by exchanging the options of Left and Right recursively. For example, in a game of chess or Chinese chess, the negative of a game is obtained by flipping the board around.

For another example of game negative:

To give a more formal definition of game negative, suppose we write the game as $G = \{A, B, C, \ldots | X, Y, Z, \ldots \}$ . Then the negative is defined recursively via:

$-G = \{ -X, -Y, -Z, \ldots | -A, -B, -C, \ldots\}$ .

Some properties of game negative are intuitively clear:

involution : the negative of the negative of a game is identical to itself;
distributivity over + : the game -(G + H) is identical to (-G) + (-H).

But what about G + (-G) ? Unfortunately, this is clearly not identical to the zero game (it is in fact much more complicated in general). However, we will rectify this apparent anomaly in the up and coming sections. This will be via the concept of game equality.

The Zero Game

We will write the following notation for any game G.

If the second player wins in G, then G = 0. We say G is zero. Note that now, a zero game simply refers to any game where the second player wins, not just the empty game $G = \{\ |\ \}$ .

If Left wins in G regardless of who goes first, then G > 0. We say G is positive.

If Right wins in G regardless of who goes first, then G < 0. We say G is negative.

If the first player wins in G, then G || 0. We say G is fuzzy.

The above cases can be put more succintly in the following table (exercise: fill in the blanks yourself; to see the answer highlight over it):

		Left starts
		Left wins	Right wins
Right starts	Left wins	G > 0	G = 0
Right starts	Right wins	G \|\| 0	G < 0

The definition may appear puzzling at first: why do we regard a game in which the second player wins as a “zero game”? It turns out if G = 0 (i.e. second player win), then the outcome of G + H is the same as that of H for any game H, as can be seen in the following table:

Table 1: Results of Sums of Games

	G = 0	G > 0	G < 0	G \|\| 0
H = 0	G+H = 0	G+H > 0	G+H < 0	G+H \|\| 0
H > 0	G+H > 0	G+H > 0		*
H < 0	G+H < 0		G+H < 0	*
H \|\| 0	G+H \|\| 0	*	*

The table is symmetric about the main diagonal, which is expected since the game sum is commutative (i.e. G+H and H+G are identical games). Instead of proving every entry in the table, we’ll just do it for one entry since the remaining cases are similar.

To show that G>0 and H>0 implies G+H>0 : suppose Left wins in both G and H, regardless of who starts. Now, in the game sum G+H, he simply moves in game G and waits for his opponent for his next move. Whatever his opponent does, Left will simply respond in the same component, as if the other component didn’t exist. This strategy works because, by assumption, he’s guaranteed to have an available move in both G and H.

Note: actually, we can say something about the cases marked *; see exercise 4.

Furthermore, the negative of a game G behaves exactly as we expect it (see exercise 5).

Sum of a Game and Its Negative

Finally, we will explain what’s so nice about this new concept of the zero game:

For any game G, the sum G + (-G) = 0, i.e. G + (-G) is a second-player win.

Why is this so? Look at the two components G and -G and let’s try to figure out a winning strategy for the second player. Suppose the first player makes a move in G – then by definition of –G there is also a corresponding move for the second player in –G. Conversely, whatever the first player chooses to do in –G, the second player can mimic his play in G. In this way, the second player is guaranteed to have a move, so he wins.

[ For a rigourous proof, let’s suppose the first player moves G → A; then the second player counters with -G → -A which is guaranteed to be available by definition of negative. ]

Now we define the game difference of G and H to be

$G - H = G + (-H)$ .

We have just proven that $G + (-G) = 0$ .

Comparison Between Games

Now we extend the above notation to compare any two games G and H. Consider the difference game G – H, which is defined to be the sum G + (-H).

If the second player wins in G-H, then G = H. We say G and H are equal.

If Left wins in G-H, then G > H. We say G is more / larger than H.

If Right wins in G-H, then G < H. We say G is less / smaller than H.

If the first player wins in G-H, then G || H. We say G and H are incomparable.

It’s important to distinguish between “G and H are identical” and “G and H are equal”. The former means that the game options, and all the options’ options, and options’ options’ options etc, are all identical. Thus, if we expand G and H till we’re left with only brackets and “|”, the two strings are identical. On the other hand, if G and H are equal, then it just means G–H is a second-player win, e. g. convince yourself that:

After a few more lessons, you will be able to prove that in general,

Next: given the comparison between G and H, as well as H and K, how does G compare with K? As a precursor, let’s prove that if A=0, then A+B = B. This is quite easy: the difference $(A+B) + (-B) = A+(B+(-B))$ is a sum of two games which are zero. By table 1, the result is also a zero-game.

Now we’re ready to answer our question, for $(G-H) + (H-K)$ is identical to $G + (-H) + H + (-K)$ by commutativity and associativity. We already know that $(-H) + H = 0$ . Adding $G + (-K)$ to both sides, the precursor result tells us that $G + (-H) + H + (-K)$ is equal to $G+(-K) = G-K$ . In summary, table 1 gives us:

Table 2: Comparisons of Games

	G = H	G > H	G < H	G \|\| H
H = K	G = K	G > K	G < K	G \|\| K
H > K	G > K	G > K		*
H < K	G < K		G < K	*
H \|\| K	G \|\| K	*	*

Another important result is the following: if $G = \{A, B, C,\ldots | X, Y, Z,\ldots\}$ then we may replace any option (e.g. A) by another game which is equal (see exercise 6). This shows that we can replace a game G by any equal game G’ whenever it appears.

Application to Impartial Games

We will apply what we’ve learnt so far to rigourously formulate the notions of Nim values. As mentioned earlier, only finite games are considered: no loopy games (i.e. no draws). Let’s define what impartial games are.

A game G is said to be impartial if at every stage of the game, the options available to either player are exactly the same.

Recursively, this means that G is impartial if the set of Left options and the set of Right options are the same, and these options are all impartial.

An alternate definition can be: G is impartial if and only if –G is identical to G. Note that –G can be equal to G without being identical, ergo G can be equal to itself without being impartial.

Examples : all the games we’ve considered in the first four lessons are impartial: namely Nim, Nim-Square, Kayles, Dawson’s Kayles, Grundy’s Game etc.

Since an impartial game G does not distinguish between either player, it follows that either the first player wins, or the second player wins. In other words, G = 0 or G || 0. Notice that in a single Nim heap of n stones, we can remove any number of stones, thus leaving 0, 1, 2, …. or n-1 stones.

So if we wish to consider the special case of a Nim heap of n stones, we should define (recursively):

*0 is the game 0 = { | }.
*1 is the game {0 | 0}.
*2 is the game {0, *1 | 0, *1}.
*3 is the game {0, *1, *2 | 0, *1, *2}.
…
*n is the game {0, *1, … , *(n-1) | 0, *1, … , *(n-1) }.

Theorem. Any Impartial game is equal to *n for some n. Specifically, if G is the game

$\{*r_1, *r_2, \dots, *r_m | *r_1, *r_2, \ldots, *r_m \}$ ,

then G = *n, where $n = mex(r_1, r_2, \ldots, r_m)$ . Recall that the mex of a list of numbers is the smallest non-negative integer which does not occur in the list.

Proof.

We need to show that $G - (*n) = G + (*n)$ is a second-player win. Let’s consider the first player’s options.

If the first player moves $*n \to *m$ for some m < n, then by definition of mex, m occurs among one of the r_i‘s. So the second player counters by moving $G \to *m$ . This gives the game $*m + *m$ , i.e. Nim heaps (m, m) which is a second-player win.
If the first player moves , then we know that by definition of mex.
- If $r_i < n$ , then the second player moves $(*n) \to (*r_i)$ thus giving $(*r_i) + (*r_i)$ which is a second -player win.
- If $r_i > n$ , then the second player moves $(*r_i) \to *n$ , thus giving $(*n) + (*n)$ , which is also a second-player win.

Applying this theorem recursively, we see that any impartial game is equal to a single Nim heap. Next we look at the addition of two Nim heaps.

Theorem. The game sum *m + *n is equal to the game *r, where $r = m\oplus n$ . Recall that the $\oplus$ operation is given by “xor”, or “addition without carry” in binary.

To prove this theorem, we need to show that $(*m) + (*n) - (*r) = (*m) + (*n) + (*r)$ is a second-player win. But this follows from the Nim solution we gave in lesson 2, since by definition there are an even number of ones in every column, when we write r, m and n in binary form.

In short, we have just seen that: (a) any impartial game is equal to a Nim heap, and (b) the sum of two impartial games corresponds to the xor-operation on the corresponding two Nim heaps. This thoroughly justifies our approach used in the first four lessons. Note that it’s possible to skip those lessons and start straight from here, but we wish to provide some interesting examples before burdening you with all these formal definitions.

In a Nutshell

In this lesson, we have learnt that:

the formal definition of games and their negatives;
we can add games and subtract games;
we can compare games: the result can be equality, greater than, less than, or incomparable;
a seemingly complicated game configuration may be equal to a much simpler one;
the ordering and arithmetic operations on games behave consistently with our intuition from real numbers;
an impartial game is equal to a Nim heap *n.

In the next lesson, we will see that some games behave as if they were real numbers. Not only can we have integers, but even fractions. This would greatly simplify computations since we can add and subtract numbers easily.

Exercises

Consider the following diagrams in domineering. Fill in the appropriate symbol between G and 0 in each case, one of = < > or ||.

Prove some of the entries in Table 1.

Now, we extend the comparison notation:

$G \ge 0$ if either G = 0 or G > 0;
$G \le 0$ if either G = 0 or G < 0.

Prove that the notation $G \ge 0$ is equivalent to saying: if Right starts first in the game G, then Left can win. Write down a similar statement for $G \le 0$ . Note: this result will be used repeatedly in subsequent lessons, so do bear them in mind!
Prove that if G || 0 and H > 0, then either G+H || 0, or G+H > 0. Hence, fill in the areas marked * in Table 1. [ Hint: prove that if Left starts in the game sum, he can win. ]
Prove that if G = 0, then –G = 0 as well. Formulate three more statements for the cases G > 0, G < 0 and G || 0.
Prove that if $G = \{A, B, C, \ldots | X, Y, Z, \ldots\}$ is a game and A = A‘, then the game $G = \{A', B, C, \ldots | X, Y, Z, \ldots\}$ obtained by replacing A with A’ is also equal to G.