Lesson 5

We did mention in the first lesson that CGT covers games without draws. Here, we’ll break this rule and look at loopy games, i.e. games with possible draws. [ To be specific, loopy games are those where it’s possible to move to a state which was previously attained in the game (think of the infinite-check in chess). ]

Let’s start with a specific example.

Square-But-One is a modified version of Square-Game. Start with n > 0 stones. At each player’s turn, he makes one out of two possible moves:
(a) remove a positive square number of stones from the heap; or
(b) if there are a positive even number of stones, he may add one stone.
As before, a player loses if he cannot make a legal move.

Notice that condition (b) gives the possibility of an infinite loop: e.g. convince yourself that 2 will result in a draw. We will still apply our logic from the first lesson:

• If n is winning, then there is a move from n to a losing position.
• If n is losing, then all possible moves from n lead to a winning position.

Based on this definition, we proceed as before:

• 0 is clearly losing.
• Therefore, 1, 4, 9, 16, …  are all winning since they can reach 0.
• 5 is losing because all possible moves (to 1 or 4) are winning.
• Therefore, 6, 9, 14, 21, … , ….  are winning positions.

Are there any more deductions? It turns out there aren’t – to achieve the next step, we need to find a losing number n, one from which all possible moves lead to winning numbers. It can be proven this is impossible (see exercise 2). So all remaining numbers (numbers not of the form or ) are draws!

Nim’s Island

The following is a map of Nim’s Island:

On the island, there is a large swamp surrounding Nim’s house where she stays with her friends, Kim and Tim. Thanks to some stone platforms erected in the swamp, the kids can still freely move about via the above routes. Each platform is large enough to hold any number of people.

Now, two players alternately move one of the three characters along one of the routes. The player who successfully guides all three home, wins the game. Who wins in the above configuration, where the three kids are placed on the gray platforms? Due to the presence of cycles, the game may end in a draw!

Once again, we will label the platforms and house with Nim values, but now we must be extra careful in our analysis! First, the house gets the Nim value of 0.

At each stage, consider an unlabelled (i.e. without Nim value) platform T. Take the set of all platforms accessible from T. Assume that:

• the labelled platforms accessible from T have Nim values , and let (recall that the mex of a list is the smallest non-negative integer which does not occur in the list);
• every unlabelled platform accessible from T has a path to some other platform which is labelled with *r.

Then we can label the platform T with *r.

Finally, after we’ve labelled all that we can, the remaining platforms are given a Nim value of ∞.

Let’s see how this works in practice. After a while we get these Nim values:

Can we replace the ‘?’ symbol with a Nim value?

• There is a labelled platform accessible from it. The Nim value there is given by *2. So we’re inclined to label ‘?’ with mex(2) = 0.
• There is an unlabelled platform accessible from it. Furthermore, the unlabelled platform connects to the house (Nim value = 0).

So by definition, we should replace the ‘?’ symbol with 0. After some effort, we get the following:

Winning Positions

It’s a little tricky to interpret the Nim values now, since some of these are infinite (∞)! What should we do with them? Here’s the recipe:

1. If all Nim values are finite, play as if we’re playing Nim.
2. If exactly one Nim value is infinite ∞,
   1. if there is a path from this ∞ to a finite Nim value *m, such that *m together with all the other Nim values is a losing position, then the original game is a winning position;
   2. if no such path exists, it’s a draw.
3. If at least two Nim values are infinite, the game is a draw.

The three positions in our problem give 0, *1, *2, which is a win for the first player. The winning move is given by *2 → *1.

Winning Strategy

Let’s figure out why the above recipe works, by considering various cases.

Take case 1 in the recipe, where all three positions have Nim values. If your opponent shifts one of the Nim values to , what should you do?

Answer: if your opponent shifts *r to ∞, then by definition, there must be a move from this ∞ to a different *r. Make that move. Can your opponent delay his defeat indefinitely by moving to ∞ repeatedly? No, because all the *r labels were obtained after finitely many iterations of the labelling process.

Take case 2(i) in the recipe: suppose two positions are labelled *r and *s but the third one is labelled ∞, such that there is a move from ∞ to . What should you do?

Answer: this case is quite obvious. Make the move . The resulting Nim game is a losing position by case 1.

Take case 2(ii) in the recipe: suppose we still have *r, *s and ∞, but now there is no move from ∞ to . What can you do?

Answer: first, you can’t win here. Regardless of what you do, you’ll end up with case 2(i) , case 2(ii), or case 1 with a non-zero Nim sum – all of which are either draws or winning positions for your opponent!

So the best you can hope for is a draw, which you can attain by adopting the following.

• Consider all possible Nim values reachable from ∞. If one of these values is not *t’, where , then just move the Nim part (*r, *s) to *t’. You’re still in case 2(ii) so you’re safe.

• If not, then the Nim values 0, *1, *2, … , *(t-1) are all reachable from ∞. By assumption, *t is not reachable from ∞. Now why is the position ∞ and not *t? It follows that there is a move from ∞ to another place c (also labelled ∞) such that there is no move from c to *t. The resulting position is then in case 2(ii).

Take case 3 in the recipe: suppose we have two or more ∞. What can we do?

Answer: not much, since cases 2(i) and 2(ii) are either draw or first-player win. Your safest bet is to loiter around case 3 by moving from ∞ to another ∞. Ok, maybe you can move to case 2(ii), but why take the risk?

Exercises

1. Consider a modification of Square-But-One: begin with n > 0 stones as before. Each player, at his turn, either (a) removes a square number of stones, or (b) add a stone if the number of stones is odd. Analyse this game for n < 40: which numbers are winning numbers, which are losing numbers, and which result in a draw?
2. (Hard) Prove the assertion that in Square-But-One, any number not of the form or ends in a draw. One possible approach:
   • Prove that if n > 5, then n-1 and n-4 cannot both be squares.
   • Prove that if n > 10, we cannot have and for some integers a, b.
   • Using (a), (b) and two more such results, prove that any number not of the form or ends in a draw.
3. Take the game of Snakes-and-Adders. Start with some counters scattered on the board (e.g. as below). Two players alternately make a move, by advancing a counter at least 1 step, and at most 4 steps ahead. There’re no constraints on which counter to pick from and the number of steps to move, as long as it does not go beyond “HOME”. When a counter reaches the tail of an arrow, it must follow it to its head (like snakes-and-ladders). The player who moves all the counters HOME wins. Each square can hold any number of counters. Analyse the board and label each square with its Nim value (either *r or ∞).

4. The game “Fair Shares and Varied Pairs” is played as follows: start with 6 almonds and arrange them in some heaps. Two players alternately make one of two possible moves, either (a) divide any heap into two or more equal-sized heaps, or (b) merge two heaps of different sizes to form a single heap. A player wins when his opponent cannot make a legal move, i.e. when he leaves (1, 1, 1, 1, 1, 1) for his opponent. Analyse the game and find all winning positions, losing positions and draw positions – no need to compute the Nim values. Note: there are altogether 11 positions.
5. If you know programming, analyse “Fair Shares and Varied Pairs” for 1-15 almonds. Can you formulate a general result?
6. In Epstein’s Put-or-Take-a-Square, we’re given a heap of n stones (n > 0). Let be the largest square number which does not exceed n. Now, the next player may choose to either add or subtract stones to the heap. E.g. with 7 stones, you’re allowed to put or take 4 stones. Explore this game for heaps of remoteness 3 or below. [ Note : the case of n = 92 is interesting because it has remoteness 11. ]
7. (Hard) A horsefly moves on a board extended downwards infinitely (see diagram below). At each move, a player picks up a horsefly and makes one out of at most six possible moves. Furthermore, a horsefly may not reverse its previous move. Now the objective of this game is slightly different from previous games: the first player to move any horsefly home wins the game. As before, a square can hold any number of horseflies. What is a good move for the first player in the starting position below? [ Note: my earlier homepage had a detailed – and excruciatingly wordy – analysis of this game. ]