## Lesson 9

Typically, at the end of a Domineering game, the board is divided into disjoint components, so the overall game is the (game) sum of the individual components. Suppose we have the following 6 components:

How should the next player respond? From an earlier exercise, you know that the components are (respectively):

{1|-1}, {0|0}, {0|-1}, {2|-1/2}, -1/2, {-1|-1}

Intuitively, the next player should pick the fourth component since it gives him 2 points; while if his opponent grabs the chance, it costs him 1/2 point. This creates a difference of 5/2 points depending on who gets to move there, which makes it rather critical.

Let’s take a closer look at games of the form {*a* | *b*}.

### Games of the Form {*a* | *b*}

First, the Simplicity Rule tells us that if *a* < *b*, then this game is a number. So let’s assume *a* ≥ *b*. We claim that the resulting game satisfies:

for any number *c*. Equivalently, we need to show that is a 2nd-player win.

**Proof**.

If the first player moves from the component {-*b*–*c* | –*a*–*c*} or {*a* | *b*}, his opponent can retaliate by moving from the other component to give a zero game. On the other hand, if *Left* starts first and moves *c* → *d*, then by an earlier observation, we may assume *d* < *c*. *Right* then counters by taking –*a*–*c*, thus leaving

.

What can *Left* do now? Taking {*a* | *b*} to *a* is suicidal since the result is a negative number. And if he moves (-*a-c+d*) to *x* with *x* < –*a-c+d* < –*a*, then *Right* counters by taking {*a* | *b*} to *b*, leaving the number *x+b* < *b-a* ≤ 0. Recall that this means if *Left* goes next, then *Right* wins. In conclusion, the first player loses even if he moves from the number component. ♦

Key observation: if *a* ≥ *b*, then we can write:

, where .

Notation: for convenience, we will use the shorthand ±*x* for the game {*x* | –*x*}. We’ll avoid this when *x*=0 though, since {0|0} = * and denoting it by ±0 may be awkward.

### Examples

- Recall that we saw games like {1 | 1}, {-1| -1}, {2 | 2} etc. By the above result, if
*m*is a number then {*m*|*m*} =*m*+ {0 | 0} =*m**. Thus, the sum {1|1} + {-1|-1} + {2|2} is simply 1 + (-1) + 2 + * + * + * = 2*. - We also saw many games of the form
*G*= {*a*|*b*} where*a*>*b*. For example:

The combined game is thus given by ±1 + (5/4) + (±3/4) = 5/4 + (±1) + (±3/4). What’s a good way to play this game? Before we can answer this question, let’s have a general result.

### Number Avoidance Theoerm

Suppose we have a sum of two games:

G = x + H,

where x is a number, and H is not. Assume that if Left starts in G, he has a winning strategy. Then he can pick his winning strategy by moving from H.

In short, if *Left* starts in *G*, there’s no reason for him to make a move from *x* at all. By symmetry, the same applies for *Right*: there’s no reason for *Right* to make a move from the number *x*.

**Proof**.

Let’s suppose: if *Left* starts in *G*, he can win by moving *x* to *y* (*y* is a number < *x*). Thus, *y*+*H* ≥ 0 (recall that a game ≥ 0 if and only if *Left* can win whenever *Right* gets to go next).

Successively, let *y*‘ be the Left option of *y*, let *y*” be the Left option of *y*‘ etc. Eventually, you’ll run out of options: *x* > *y* > *y*‘ > *y*” > … . Let *z* be the smallest of these such that *z* + *H* ≥ 0 (since *y* + *H* ≥ 0, we can definitely find such a *z*).

Now *H* is not a number, so *H* ≠ *-z*. Thus *z* + *H* > 0. If Left starts in the game *H*+*z*, he has a winning move. This move cannot be *z* → *z*‘ since by the minimality of *z*, we do not have *z*‘ + *H* ≥ 0. Hence, it must be to some *Left* option *A* of *H*: so *z* + *A* ≥ 0. But this gives:

so *Left* has a winning move in *x+H* by moving to *x+A*. ♦

In short, let’s say we have a sum of several games. If all components are numbers, then so is the sum and the outcome of the game is crystal-clear. Otherwise, there’s at least one component which is not a number, and the *Number Avoidance Theorem* says that the winning party only needs to look at those components which aren’t numbers. This is concisely summarised as follows.

Avoid making a move in the number,

unless there’s nothing else to do.

### Games of the Form ±*c*

Let’s go back to the game 5/4 + (±1) + (±3/4) in example 2. We’ll see who wins in this game. Suppose *Left* starts, with no loss of generality.

- By Number Avoidance,
*Left*should focus his effort on (±1) or (±3/4). - Suppose he picks the second component (±3/4) → 3/4. Then once again, by Number Avoidance, the only logical move for
*Right*is the remaining (±1) → -1. This gives a grand total of 5/4 + 3/4 – 1 = 1. - On the other hand, if
*Left*picks the first component (±1) → 1, the same analysis tells us that the resulting total is 5/4 – 3/4 + 1 = 3/2 which is clearly better. So*Left*ought to pick this option.

On the other hand, if *Right* starts, the final sum would be 5/4 – 1 + 3/4 = 1. In short, if *Left* starts, the final game value is 3/2, while if *Right* starts, it would be 1.

In summary, if we have a game x + (±a) + (±b) + (±c) + … , where x is a number and a ≥ b ≥ c ≥ …, the most logical thing for the first player is to play the largest a, then the next player goes for the next largest b, etc.

One can also think of a game (±*c*) as a cheque for an additional *c* moves for either player. From this point of view, it becomes clear that the best course of action is to pick the cheque with the largest value.

Now we’re ready to analyse the Domineering game we saw earlier:

with values given by:

±1, *, 1/2 + (±1/2), 3/4 + (±5/4), -1/2, -1*

The two stars cancel each other out, so the final sum is -1/4 + (±5/4) + (±1) + (±1/2).

- If
*Left*starts:*Left*takes ±5/4 to 5/4,*Right*takes ±1 to -1 and then*Left*takes ±1/2 to 1/2, thus giving a total of (-1/4) + (3/4) = 1/2:.*Left*wins - If
*Right*starts, the reverse happens and we get (-1/4) – (3/4) = -1:.*Right*wins

Warning! This does not mean the sum of the games is {1/2 | -1}. It just means that if these are the only components left, the above outcome would happen if both players were to play optimally.

### New Game: Toppling Dominoes

Here’s a new game, called **Toppling Dominoes**. We have several dominoes (coloured *Light* or *daRk*, corresponding to *Left* or *Right*) which are placed upright in one or more rows. Each player, at his turn, pushes one of his dominoes over either to its left or right – this will cause a chain reaction, toppling over all dominoes to its immediate left or right. Dominoes which have been toppled do not contribute to further gameplay.

E.g. here’s an example of a game where *Left* starts:

As usual, the player who runs out of legal moves loses the game. Clearly *Right* made a bad move above, since he could have toppled the third *daRk* domino to get rid of the *Light* domino to its right, thus leaving one additional free move for himself.

If in a row, there are *n* dominoes for Left and none for Right, then clearly the value of the row is exactly *n* since *Left* can start toppling from the leftmost domino one by one (to the

left), which gives him *n* free moves. The next interesting example is:

Let’s analyse this position:

*Left*starts: his best move is to topple all of*Right*‘s dominoes with a single move, leaving*n*-1 dominoes of his own. This gives*n*-1.*Right*starts: likewise, his best move is to topple all of*Left*‘s dominoes with a single move, leaving*m*-1 dominoes of his own. This gives -(*m*-1).

Thus, the resulting game is {*n*-1 | -(*m*-1)}, which we had analysed earlier. In particular, when *m* = *n* = 1, this is {0 | 0} = *. Next, consider the following:

If *Left* starts, he can topple all dominoes or leaves a pair of *Left*/*Right* dominoes. If *Right* starts, he has no choice but to leave 1. Hence, the game is: *G* = {0, * | 1}.

We will learn a new form of simplification in the next lesson, and see that it is equal to 1/2. For now, you can verify this by proving that {0, * | 1} + (-1/2) is a second-player win.

### Exercises

- Find a game
*H*= {*A*|*X*} which is a number, and a number*x*such that . - Consider the following game:
number + {2 | -1} + {0 | -3} + {1 | -1} + {3 | 2} + {0 | -1/4}.

*Left*gets to start. By the theory we learnt earlier, his best move should be in the component {2 | -1} or {0 | -3}. Yet he chooses to move in {1 | -1} → 1 instead. Explain why this move really isn’t bad. - Prove that if
*a*≥*b*≥*c*, then { {*a*|*b*} | {*b*|*c*} } =*b*. - Recall the following claim in Lesson VI:

Prove this by proving the more general assertions:

- Compute the following Domineering positions (use exercises 2 and 3 if necessary):

(**Hard**) Guess a general formula for such configurations and prove it.