Combinatorial Game Theory VII

Lesson 7

[ Warning: another long post ahead. One of the proofs will also require mathematical induction. ]

In this lesson, we will see how some games can be represented by numbers (which can be integers or fractions). We will also introduce the following game.

Hackenbush

Draw a diagram with Light and daRk edges, which is attached to the ground. E.g.

The two players alternately remove an edge from the diagram. After a move, any component which is disconnected from the ground is eliminated. Furthermore, player Left can only remove Light edges while Right can only remove daRk edges. A player wins if he gets to clear the diagram. Hackenbush can also be played with bLue and Red edges.

Integers

First, consider the following configuration.

It is clear that Left is the winning party. In fact, Left has n free moves available to him while Right doesn’t have any. Hence, it makes sense to label the above game by n. Indeed, we will define the following games as positive integers:

Definition. The game 1 is defined to be {0 | }. And we recursively define the games 2, 3, … as follows:

2 = 1 + 1, 3 = 2 + 1, 4 = 3 + 1, ….

On the other hand, consider the negation of 1, i.e. -1. This is obtained by flipping the colours (Light to daRk and vice versa), so we have the following:

Definition. The game -1 is defined to be { | 0}. And we recursively define the games -2, -3, … as follows:

-2 = (-1) + (-1), -3 = (-2) + (-1), -4 = (-3) + (-1), ….

So the following configuration is equal to –n.

Since -1 is defined to be the negative of 1, we know that 1 + (-1) = 0 by the results in the previous lesson. In other words, when we add and subtract the above games, we are just performing the usual addition and subtraction on integers.

What are the options available for a game which is a positive integer?

From the Hackenbush games above, it is clear that if n is a positive integer, then Left has a single possible move n → n-1 while Right has no available move. Hence, we could also have defined inductively:

1 = {0 | }, 2 = {1 | }, 3 = {2 | }, … , n = {n-1 | }.

Games With Value 1/2

This is our first example of a fraction occurring in a game. Consider the following game G:

Looking at the options of G, we get G = {0 | 1}. It is very tempting to write this as G = 1/2. To check that this is consistent with addition, we need to verify G + G = 1, or equivalently, G + G + (-1) is a second-player win. This is an easy exercise which we’ll leave to the reader.

Definition. The game {0 | 1} is denoted by 1/2.

What about -1/2? By definition, it is the negation of 1/2, so it is {-1 | -0} = {-1 | 0}.

Warning : it is not true that 1/2 is the only game G for which G + G = 1 (see exercise 2).

Clearly, 1/2 is a win for Left, so 1/2 > 0. On the other hand, 1/2 + 1/2 = 1, so adding -1/2 on both sides gives us 0 < 1/2 = 1 + (-1/2). Adding 1/2 on both sides again, we get 1/2 < 1. We have, thus, proven:

0 < 1/2 < 1.

Before proceeding to define other fractions, we shall introduce the first method of simplifying games.

Simplification (I)

Consider a general game expressed in this form:

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

We claim that if B ≥ A then we can erase A from our list of Left options to obtain $G = \{B, C, \ldots | X, Y, Z, \ldots\}$ . On a heuristic level, this seems obvious since A is a “better” move for Left compared to B. But let’s prove it carefully.

Proof. We write:

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

We need to show that G = H, i.e. G + (-H) is a second-player win. Note that by definition of negation:

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

Now, the second player has an easy strategy as follows: whatever the first player does, he does the reverse in the other component. The only problem occurs if Left starts by taking G → A. Although Right has no corresponding move –H → –A, he can do even better: take –H → -B. The resulting game is now:

$A - B \le 0.$

Recall from last lesson’s exercise that in such a game, if Left starts, then Right wins. But now it’s precisely Left‘s turn, so Right gets to win. Conclusion: G – H is a second-player win, which completes the proof. ♦

Note that the above simplification rule has a twin brother: If X and Y are Right‘s options in the game G, and X ≥ Y, then we can erase X from the list of Right options and the game is still equal to G.

More Fractions

The next step is to look at the game:

Writing the options of G, we get G = {0 | 1/2, 1}. By the simplification rule we just covered, we can remove 1, so G = {0 | 1/2}. A bit of work should convince you that G + G + (-1/2) = 0 (i.e. is a second-player win). So let’s define 1/4 = {0 | 1/2}.

More generally, let’s consider the following game:

$hacken_frac$

We would like to label $G_n = 1/2^n$ . To do that, we need to show that $G_n + G_n = G_{n-1}$ for n = 1, 2, 3… . The proof will be carried out by induction.

Proof. Suppose we already know that $G_n + G_n = G_{n-1}$ for n = 1, 2, … t-1. Then for n = t, we have:

$G_t = \{0\ | \ G_0, G_1, G_2, \dots, G_{t-1}\}.$

It is easy to see that $G_0 > G_1 > G_2 > \ldots$ (it’s not that hard, so we’re leaving it as an exercise) so the game simplfies to $G_t = \{ 0\ |\ G_{t-1}\}$ . Hence it remains to show that:

$\{0\ |\ G_{t-1}\} + \{0\ |\ G_{t-1}\} + (-G_{t-1}) = 0.$

Note that $-G_{t-1} = \{-G_{t-2}\ |\ 0\}$ . To prove that the above game is a second-player win:

Suppose Left starts.
- If Left takes $\{0\ |\ G_{t-1}\} \to 0$ , then Right can take $\{0\ |\ G_{t-1}\} \to G_{t-1}$ , thus leaving the sum 0 and win.
- If Left takes $(-G_{t-1}) \to (-G_{t-2})$ , then Right takes $\{0\ |\ G_{t-1}\} \to G_{t-1}$ . By induction hypothesis, $G_{t-1} - G_{t-2} = -G_{t-2}$ so the game is now $G_t - G_{t-2} < 0$ . Right wins.
Suppose Right starts.
- If Right takes $\{0\ | \ G_{t-1}\} \to G_{t-1}$ , Left takes $\{0 \ |\ G_{t-1}\} \to 0$ , thus leaving 0 and win.
- If Right takes $(-G_{t-1}) \to 0$ , then Left takes $\{0 | G_{t-1}\} \to 0$ also. This gives $\{0\ |\ G_{t-1}\} = G_t$ which is clearly positive. So Left wins.

This completes the proof. ♦

In conclusion, we may label $G_n = 1/2^n$ . Formally, we get the following recursive definition:

1/2 ={0 | 1}, 1/4 = {0 | 1/2}, 1/8 = {0 | 1/4}, 1/16 = {0 | 1/8}, …

More Fractions

Now that we’ve successfully defined fractions of the form 1/2, 1/4, 1/8, 1/16, … , we can now define any rational number of the form $m/2^n$ via addition and subtraction. We call such rational numbers dyadic rational numbers.

Now, one is inclined to naïvely think that we can just take averages: $\{a | b\} = \frac{a+b}2$ . Unfortunately, this is not true in general as the following examples illustrate.

Examples

Consider the game G = {-5 | 2}. If Left starts, he leaves a negative number and Right wins. If Right starts, he leaves a positive number and Left wins. So the 2nd player wins! This means G = 0.
Consider G = {1/4 | 1}. We claim G = 1/2. Indeed, we just need to show G – 1/2 = G + {-1|0} is a 2nd-player win. This is easy (try it!).

Despite this minor setback, we can take averages in some cases.

If p is an integer and m is a non-negative integer, then:

$\{ \frac p {2^m} \ | \ \frac{p+1}{2^m}\} = \frac{2p+1}{2^{m+1}}.$

Proof. First consider the case 2p+1 > 0. Write the RHS (right-hand-side) as a sum of (2p+1) terms, each equal to $1/2^{m+1} = \{0 \ |\ 1/2^m\}$ . Thus, in this game sum, if Left starts, he has no choice but to play $\{0 \ |\ 1/2^m\} \to 0$ . Likewise, if Right starts, his only move is $\{0\ |\ 1/2^m\} \to 1/2^m$ . By considering these options, we get the game $\{\frac{2p}{2^{m+1}}\ |\ \frac{2p}{2^{m+1}} + \frac 1 {2^m}\}$ which is precisely the LHS. The case where 2p+1 < 0 is similar and is left to the reader.♦

Simplicity Rule

As mentioned earlier, we cannot take averages in a game to simplify it to a number. Due to this subtlety, we need the notion of simplicity:

We introduce an ordering among the set of dyadic rational numbers: the notion of simplicity. This ordering is “partial” in the sense that for some dyadic rational r, s, we are unable to say whether r<s or s>r.

If r has a smaller denominator than s (in reduced fractions), then r is simpler than s.

Among integers, if |a| < |b|, then a is simpler than b.

0 is the simpler than any r.

Examples

-2 is simpler than 3 by criterion 2.
5/2 is simpler than 1/4 by criterion 1.
7/8 and 1/8 cannot be compared; neither is simpler than the other.
4/8 = 1/2 is simpler than 3/8 by criterion 1.

Now we have the following theorem.

Theorem (Simplicity Rule). Suppose G is a game

G = {a, b, c, … | x, y, z, … }

whose options a, b, c, …, x, y, z, … are all numbers. If there is an r such that a<r, b<r, c<r, … and r<x, r<y, r<z, … then G is also a number, and is equal to the simplest dyadic rational r satisfying these inequalities.

As you can tell, this is a highly non-trivial result. The proof will come in three steps:

There exists a simplest dyadic rational r satisfying the inequalities, in the sense that: you cannot find a number s which is simpler than r such that the inequalities hold.
The r found in step 1 satisfies G = r.
Hence such an r must be unique. [ Note that step 1 does not imply that r is unique, since the ordering is only partial. ]

Examples

{-2 | 5} = 0. [ Alternatively : the second player wins so it’s a zero game. ]
{1/2 | 17/4} = 1.
{1/4 | 13/16} = 1/2.
{-1/4 | -1/16} = -1/8.
{17/2 | } = 9.
{-17/2 | } = 0.

Proof of Simplicity Rule

Before start the proof let’s use the following observation.

Let G be a game equal to some dyadic rational number r. Then we can write G as one of the following forms:

{m | n}, where m < n are numbers simpler than r, and m < r < n;

{m | }, where m is a number simpler than r and m < r;

{ | n}, where n is a number simpler than r and r < n;

{ | }.

Why is this true? Well, 0 goes to case (d). If n is a positive integer, then we already know n = {n-1 | } and –n = { | -(n-1)} which are in cases (b) and (c). Finally, any dyadic non-integer can be written as $\frac {2p+1}{2^r}$ for some integer p and positive integer r. But we saw earlier that $G = \frac{2p+1}{2^r} = \{ \frac{p}{2^{r-1}} | \frac{p+1}{2^{r-1}} \}$ .

Now let’s follow the above 3 steps. Recall that:

$G = \{ a, b, c, \ldots | x, y, z, \ldots \}$ ,

where the options a, b, c, …, x, y, z, … are all numbers.

Step 1. This is easy: consider the set of all dyadic rational numbers r satisfying the inequalities a<r, b<r, c<r, … and r<x, r<y, r<z, … . Since the denominator of each r is finite, there must be an element with a smallest denominator (though possibly non-unique). If the smallest denominator is 1 (i.e. r is an integer), break ties by picking the one with the smallest absolute value.

Step 2. We need to show that G + (-r) is a 2nd player win. Suppose Left starts. Since any Left option is less than r, moving in the G-component would result in a negative value (Right wins – bad). On the other hand, suppose he moves in the second component (-r). By the above observation, we may assume the move is (-r) → (-n), where n is simpler than r and r<n. By our choice of r, it follows that either a≥n for some Left option a of G, or n≥x for some Right option x of G.

But n > r > a so the first case is out. We thus have n≥x and Right may win in the resulting game G+(-n) by picking the first component, thus leaving x-n ≤ 0. [ Recall that if a game G satisfies G≤0, then Right wins if Left gets to start first. ] In conclusion, if Left starts in G-r, Right wins.

One can show similarly that if Right starts, Left wins.

Step 3. This follows from the fact that no two distinct numbers are equal, even as games.

In a Nutshell

Here’s a recap of what we’ve learnt.

Impartial games: 0, *1, *2, *3, … .

Numbers: e.g. 1/2, 3/8, 7/16, -5/32, … .

Simplifying a game by removing redundant options.

How to simplify games to numbers using the simplicity rule.

Here’re some further notational simplifications: *1 is usually denoted as just *, while the game G+* is also denoted G*.

Exercises

Jen considers the game G = {1/8 | 1} as well as G – 1/4. She reasons that if Left starts, he could move G → 1/8, leaving 1/8 – 1/4 < 0; and if Right starts, he could move G → 1, leaving 1 – 1/4 > 0. Thus, the 2nd player wins and so G= 1/4. However, this is wrong.
- Use the Simplicity Rule to find the actual value of G.
- Where did Jen’s reasoning go wrong?
Prove that there are infinitely many games G, no two of which are equal, satisfying G + G = 1. Thus, 1/2 is not the only G satisfying this equality.
Prove that for any positive integers n, r, we have $-\frac 1 {2^r} < *n < +\frac 1 {2^r}$ .
Use the simplicity rule to simplify the following games to numbers.
- {-1/2 | 3/8 };
- {-5/2 | -1/2 };
- { 1/2 | 13/16 };
- {5/2 | }.
Analyse the following Hackenbush positions and verify their values.

Analyse the following Hackenbush positions and find their values.

Consider the game of Cutcakes. Given a cake, divided into m × n unit squares, each player at his turn takes a piece of cake and slices it along the edges of the squares, thus dividing the cake into two pieces. In addition, Left can only cut vertically, while Right can only cut horizontally. A typical game may proceed as follows if Left starts. Find the values for m × n Cutcakes, for 1 ≤ m, n ≤ 6.

Each of the following Domineering positions is either a number or a game of the form {m | n}, where m ≥ n are numbers. Compute them.