## Lesson 12

Recall the following Domineering configuration in lesson 10:

The above game has a nice theory behind it.

Definition: For any gameG, the game –_{G}(calledminy–G) is defined to be:

The game +

_{G}(calledtiny–G) is defined to be the negative of miny-G:

The above Domineering position thus equals –_{2}. First, some easy results about tinies and minies:

- miny-G is always negative; hence, tiny-G is positive.
- If G ≥ H, then ; hence .

**Proof**

(1) is trivial. For (2), since *G* ≥ *H*, we have {*G* | 0} ≥ {*H* | 0}. Hence it follows that:

.

The second part of (2) follows easily. ♦

*Warning*: it is not true that if *G* > *H*, then –_{G} > –_{H} (see exercise 1).

Next, we have:

Let G ≥ 0 be any game. Then +

_{G}is positive and less than any positive number r. Thus +_{G}is an infinitesimal and not a number.

**Proof.** Since *G* ≥ 0, we have +_{G} ≤ +_{0}. But . Hence, +_{G} is a positive game which is smaller than or equal to ↑, which is smaller than any positive number. ♦

### More on Minies and Tinies

Consider the games –_{m} and +_{m} for a number *m*. Note that if *m* is a negative number, then –_{m} and +_{m} are also numbers, which are not very interesting. Hence, we consider the case where m is a non-negative number. We introduce the following notation:

Let G and H be positive games. Write G << H if

G + G + … + G < H

for any finite number of copies of G.

In other words, if *G* << *H* then *G* is so much smaller than *H* that no matter how many copies of *G* you put together it’s still smaller than *H*. For example, we know that ↑ << *m* for any positive number *m*.

The key result of this section is:

Main Theorem. Let m > n be non-negative numbers. Then.

In short, even if m and n differ by just a little bit, the resulting games are miles apart.

**Proof**.

Let us consider the sum of many copies of +_{m} = {0 | {0 | –*m*}} and one –_{n} = { {*n* | 0} | 0 }:

{0 | {0 | –*m*}} + {0 | {0 | –*m*}} + …. + {0 | {0 | –*m*}} + {{*n* | 0} | 0}.

We wish to show that this game is negative, i.e. *Right* wins. *Right*‘s strategy, at his turn, is to move +_{m} → {0 | –*m*} if there’s such a component available. If *Left* ignores this component on his next move, then *Right* proceeds to take {0 | –*m*} to –*m*: when that happens, *Right* is guaranteed a win since none of the components has a number m or above (the best number for Left is *n* < *m*).

Hence *Left* has no choice but to passively take {0 | –*m*} to 0, and *Right* may keep repeating this strategy. Eventually, *Right*‘s left with {{*n* | 0} | 0} or {*n* | 0} for his next move. In either case he wins. ♦

*Notice that in the above proof, Right is the aggressive party and Left is forced to respond to each of Right’s threat. In Go terminology, we say that Right is sente (先手) and Left is gote (後手).*

Hence, we have:

.

For example, in Domineering we have:

Tiny games also occur rather frequently in Toads-and-Frogs (see exercise).

### Advanced Topics

Due to time constraints and practical considerations, we can’t delve into advanced materials. Here’s a sketch of what we’re missing out.

[ *Additional note: now that I’ve decided to place these notes online, it’s possible I’ll include some of these topics in a later installation.* ]

**1. Heating and Cooling**

Games like {3 | -1} are considered **hot** because the next player has a great incentive to move from there. In this game for example, *Left* and *Right* are fighting for a possible 4-point difference. Another more complicated example is { {5|1}, 2 | {-1|-2} }. If a game has several hot components, analysing their sum may be quite difficult. A common technique to do this is to cool the game, i.e. make the next player pay a penalty for moving in that component. E.g. cooling {10 | -2} by 6 gives {10 – 6 | -2 + 6} = {4 | 4} = 4*.

Heating is just the opposite of cooling.

**2. Thermograph**

By cooling a game incrementally and measuring how hot it is, we obtain the **thermograph** of the game. This is a rather useful device, for given the thermographs of various components *A*, *B*, *C*, … , there is a general strategy to *approximately* find the best component to play from. The method is convenient but it may go wrong on rare occasions.

**3. Go Endgame Analysis**

Analysis of *Go* (Weiqi) endgames has progressed significantly in the last 15 years. In a typical Go endgame, the board is divided into independent components which are then summed up. CGT is very useful for studying the value of each component and simplifying the sum. Usually, we cool a component by 1 in order to effectively evaluate this sum.

**4. Theory of Infinitesimals and Atomic Weights**

An infinitesimal can be assigned an atomic weight *m*, which roughly approximates it with *m* copies of up ↑. E.g., ↑, 2↑ + *, 5↓ + (+_{2}) have atomic weights 1, 2, -5 respectively.

**5. Impartial Misere Games**

In **misere** games, the player who makes the last move loses, i.e. the player who’s unable to make a move wins! In 2005, Thane Plambeck found an ingenuous way of analysing misere games via the theory of monoids. As a result, games previously considered too difficult to analyse (e.g. Misere Kayles) have been effectively solved. This is a huge subject which is impossible to do justice to within a lesson or two.

**6. Other Games to Analyse**

Various other games are also of interest to researchers. E.g. clobber, konane, ski-jumps, amazons, fox-and-geese. A rather startling application was also found in the children’s game **Dots-and-Boxes** via the theory of nimstrings, which enabled deep analyses of complex positions. What’s rather ironic is that the theory is based on impartial games, although Dots-and-Boxes itself is clearly a partial game.

### Exercises

- Find games
*G*>*H*, such that –_{G}= –_{H}. Can you pick your*G*and*H*to be infinitesimals? (Hint: let*G*be ↑ ) - Generalise the main theorem: prove that if are all numbers, then

.

- Prove that:
- if
*G*,*H*,*K*are positive games and*G*<*H*,*H*<<*K*, then*G*<<*K*; - if
*a*>*c*are numbers, then ; - if
*a*>*b*>*c*are numbers, then .

- if
- We saw in last week’s notes that:

equals . We can generalise this result as follows:

- Suppose a Toads-and-Frogs game
*G*has exactly one empty square. Prove that if*Left*starts by making a jump, he’ll lose. - Suppose a Toads-and-Frogs game
*G*has exactly one empty square, and the only legal first moves are jumps. What can you say about*G*? - Consider the following game
*G*for_{n}*n*≥ 2:

Let *H _{n}* be the Toads-and-Frogs game obtained by letting

*Left*move two toads consecutively. Prove that .

- Prove that if
*n*≥ 4, then . Hence, .