## Lesson 10

In lesson 7, we learnt that if *A*, *B* are Left’s options in a game with *A* ≥ *B*, then we can drop *B* from the list of options and the game remains equal. In this lesson, we will learn a second type of simplification.

### Simplification (II)

This is called **move reversal** and it takes a certain amount of practice to get used to.

Let G be a game. Suppose there is a Left option A of G, and a Right option X of A satisfying X ≤ G. Then we can replace the Left option A of G with all the Left options of X.

The following diagram illustrates this replacement.

The idea behind the replacement is that if *Left* makes the move *G* → *A*, then it does not hurt for *Right* to make the move *A* → *X*. Hence, we can replace the option *A* by all Left options of *X* to obtain the resulting game.

**Proof.**

We wish to show that these two games are equal:

and

For that we consider *G* – *H*. For most moves that the first player makes, the second player has a corresponding move in the other component to bring the game to zero. Exceptions are:

. This results in the sum*Right*goes first and moves –*H*→ –*D**G*–*D*. On the other hand, this could have occurred if*Right*moves first in*G*–*X*and takes –*X*→ –*D*. Since*G–X*≥0,*Right*loses if he starts in*G-X*. Hence*Left*wins if he goes first in*G–D*.**Left goes first and moves a move**. Then*G*→*A**Right*counters with the move*A*→*X*thus giving the game*X*–*H*. Now consider the game*X–G*≤ 0 : if*Left*starts first in this game,*Right*wins. Now let us switch back to*X – H*, where*Left*goes next.- If
*Left*moves –*H*→ –*Y*, then the resulting game*X – Y*could have arrived from*Left*‘s move –*G*→ –*Y*in*X – G*. Thus*Right*wins if he goes next in*X – Y*. - If
*Left*moves*X*→*D*, then*Right*can counter –*H*→ –*D*thus giving a zero sum (and winning).

- If

This completes the proof that second player wins in *G-H*. ♦

By symmetry, we have the following move reversal as well.

Suppose there is a Right option X of G, and a Left option A of X satisfying A ≥ G. Then we can replace the Right option X of G with all the Right options of A and the game remains equal.

Note: it may not seem advantageous to replace one option by so many options. But now *D*, *E*, *F* are much simpler than the initial option *A*, so further simplifications can be obtained easily. You’ll see this for yourself in lots of examples.

Let G be a game. An expression is said to be in

canonical formif it cannot be simplified using (I) (in lesson 7) or (II) above.

It turns out that the canonical form of a game is essentially unique! This will be proven at the end of the lecture.

### Examples

[ Note: the following examples are much more effective when presented on the board. Otherwise, to get a more in-depth understanding, you should work out the reasoning yourself. ]

- Consider the Domineering position:

*Left*‘s options are 0 and *, while *Right*‘s option is *. So the above game is: .

From *Left*‘s option *G* → *, *Right* can move * → 0. Is it true that 0 ≤ *G* ? Indeed, it is easy

to see that if *Right* starts in G then *Left* wins. Hence, the *Left* option * reverses to 0 and we

have to replace it by all *Left* options of 0. Since 0 has no options, we get .

- Consider the game
*G*= {* | 1}. The*Left*option*G*→ * has the*Right*option * → 0. Is it true that 0 ≤*G*? Yes: clearly if*Right*starts in*G*, then*Left*wins. So as before, we shall replace * by all*Left*options of 0. This gives*G*= { | 1} = 0. - What about
*G*= {↑ | 1} ? The*Left*option ↑ has the*Right*option ↑ → *. Now is * ≤*G*? To answer this question, we look at*G*– * =*G*+ *. If*Right*starts this game, he has two options: either*G*→ 1 or * → 0: either way, the result is positive and he loses. So indeed, we have * ≤*G*. This means we can replace the option ↑ by all*Left*options of *, i.e. 0. This gives*G*= {0 | 1} = 1/2. - Next consider the Frogs-and-Toads position from lesson 8:

We recall that this game is given by *G* = {↑ | ↓}. Can we simplify this further? Now, *Left* has the option *G* → ↑, which has the *Right* option ↑ → *. Is it true that * ≤ *G*? Let’s check out *G* + *. *Right* has two possible moves: either *G* → ↓ or * → 0.

- In the first case,
*Left*gets ↓* which is a first-player win, i.e.*Left*wins. - In the second case,
*Left*gets*G*and promptly responds with*G*→ ↑ to win.

Hence, * ≤ *G* indeed and we can replace the *Left* option ↑ by the *Left* options of *, namely 0. This gives *G* = {0 | ↓}. Repeat this to get *G* = {0 | 0} = *.

- Consider the following
**Toppling Dominoes**position in the previous lesson.

Recall that this game is *G* = {0, * | 1}. Let’s consider the *Left* option *. Here, there exists a *Right* option * → 0 and we ask whether 0 ≤ *G*. Indeed, if *Right* starts in *G*, he has to move *G* → 1 and *Left* wins, so 0 ≤ *G*. As a result we can replace * by all *Left* options of 0, namely nothing. So *G* = {0 | 1} = 1/2.

- Consider the game G = {0 | *, ↓}.
*Left*‘s move to 0 has no*Right*option.*Right*‘s move to * has a*Left*option 0. Now is 0 ≥*G*? Clearly not:*Left*wins in*G*if he starts, so*Right*‘s move to * cannot reverse to 0.*Right*‘s move to ↓ has*Left*option *. Is * ≥*G*? Looking at*G*+ *:- If
*Left*starts by moving*G*to 0, then*Right*moves * to 0 and wins. - If
*Left*starts with * to 0, then*Right*moves G to ↓ leaving a negative game and wins. - Hence,
*Right*‘s move to ↓ has to be replaced by all the*Right*options of *, namely 0. This gives us G = {0 | *, 0}. Check that it cannot be reduced any further.

- If

- Consider the game
*G*= { {2 | 1/4} | {3 | 1} }.*Left*‘s move to {2 | 1/4} gives*Right*the option to move to 1/4. Now is 1/4 ≤*G*? Indeed, take*G*+ (-1/4).- If
*Right*starts by taking*G*→ {3 | 1}, then*Left*can counter with {3 | 1} → 1 and win. - If
*Right*starts with (-1/4) = {-1/2 | 0} → 0, then*Left*wins since*G*is positive. - So
*Left*‘s move reverses to 1/4, and we may replace {2 | 1/4} by the*Left*options of 1/4 = {0 | 1/2}, i.e. 0. Hence,*G*= {0 | {3|1}}. Similarly, we can replace {3 | 1} by the*Right*options of 3, so*G*= {0 | } = 1.

- If

### Uniqueness of the Canonical Form

We have the following surprising result.

Theorem (Uniqueness of Canonical Forms). If games G and H are equal, andare both in canonical form, then after some reordering, we have A = A’, B = B’, …. , X = X’, Y = Y’, … .

**Proof**

It suffices to show: for each *Left* option *A* of *G*, there is a Left option *A’* of *H* such that *A*=*A’*. For this, let’s look at *G-H*. Since this is a 2nd-player win, the game *A–H* is a win for *Right* if he starts. What could *Right*‘s winning move be?

- Suppose
*Right*‘s winning move is for some*Right*option*X*_{0}of*A*. Then*X*_{0}–*H*is win for*Right*if*Left*starts. Thus,*X*_{0}–*H*≤ 0 which means*X*_{0 }≤*H*= G. But this means that*Left*‘s move*G*→*A*reverses to*X*_{0}, which contradicts our claim that*G*is already in canonical form. - Suppose
*Right*‘s winning move is for some*Right*option –*A’*of –*H*. As in the first case, we now have*A*–*A’*≤ 0 which means*A*≤*A’*.

In conclusion, for any *Left* option *A* of *G*, we can find a *Left* option *A’* of *H* such that A ≤ *A’*. By symmetry, this means we can also find a Left option *A”* of *G* such that *A’* ≤ *A”*. But this means: *A* ≤ *A’* ≤ *A”*.

Since *G* is already in canonical form, and *A* ≤ *A”* are both *Left* options of *G*, we see that they’re in fact equal. Thus *A = A’ = A”*. ♦

### Exercises

- Simplify the following games as much as you can (using the two methods of simplifications, and/or any shortcut you can think of):
- {* | 1/4}
- {0, * | 1}
- {0, ±1 | 4}
- {0, *, *2, ↑ | ↑ }
- { {5|0}, {4|1} | {2|3} }

- Prove that if
*G*= {*A*,*B*, … |*X*,*Y*, … } and there is a number*m*such that

*A*, *B*, … < *m* < *X*, *Y*, …

then *G* itself is a number. Hint: use the number avoidance theorem from last week. Using this, go back to question 1. Can you tell at one glance which games must be numbers?

- Given the following Toads-and-Frogs games:

write the following games in canonical form:

- Given the following Domineering games:

write the following in canonical form:

- Given the following Domineering games:

write the following in canonical form: