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:

• Right goes first and moves –H → –D.  This results in the sum 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 G → A. Then 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).

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 form if 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. ]

1. 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 .

2. 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.
3. 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.
4. 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} = *.

5. 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.

6. 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.
7. 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.

Uniqueness of the Canonical Form

We have the following surprising result.

Theorem (Uniqueness of Canonical Forms). If games G and H are equal, and

are 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₀ of A. Then X₀–H is win for Right if Left starts. Thus, X₀–H ≤ 0 which means X₀ ≤ H = G. But this means that Left‘s move G → A reverses to X₀, 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

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

3. Given the following Toads-and-Frogs games:
   

write the following games in canonical form:

4. Given the following Domineering games:

write the following in canonical form:

5. Given the following Domineering games:

write the following in canonical form: