Lesson 12

Recall the following Domineering configuration in lesson 10:

The above game has a nice theory behind it.

Definition : For any game G, the game –_G (called miny–G) is defined to be:

 

The game +_G (called tiny–G) is defined to be the negative of miny-G:

The above Domineering position thus equals –₂. First, some easy results about tinies and minies:

1. miny-G is always negative; hence, tiny-G is positive.
2. 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 ≤ +₀. 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↓ + (+₂) 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

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

.

3. Prove that:
   1. if G, H, K are positive games and G < H, H << K, then G << K;
   2. if a > c are numbers, then ;
   3. if a > b > c are numbers, then .
4. We saw in last week’s notes that:

equals . We can generalise this result as follows:

1. Suppose a Toads-and-Frogs game G has exactly one empty square. Prove that if Left starts by making a jump, he’ll lose.
2. 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?
3. Consider the following game G_n for n ≥ 2:

Let H_n be the Toads-and-Frogs game obtained by letting Left move two toads consecutively. Prove that .

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