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

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

1. Find a game H = {A | X} which is a number, and a number x such that .
2. 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.

3. Prove that if a ≥ b ≥ c, then { {a | b} | {b | c} } = b.
4. Recall the following claim in Lesson VI:

Prove this by proving the more general assertions:

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

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