Combinatorial Game Theory III

Lesson 3

We’ve learnt Nim and we’ve learnt the Square Game. Now, let’s combine them and consider the following game, which we shall name Nim Square.

Start with r heaps of stones, of sizes $n_1, n_2, \dots, n_r > 0$ . Play alternates between two players: at each player’s turn, he must pick a heap and remove $m^2$ stones from it, where m is a positive integer. As before, he can remove stones from one and only one heap.

Here is an example of a play between two players for (1, 2, 9):

$(1,\mathbf{2},9) \to (1,\mathbf{1},9) \Rightarrow (1,0,\mathbf{9}) \to (1,0,\mathbf{5}) \Rightarrow (1,0,\mathbf{1}) \to (\mathbf{1},0,0) \Rightarrow (0,0,0).$

Thus the second player wins again. It turns out there is a very neat method of solving Square Nim, which is generalisable to a vast class of games called impartial games. A more exact definition of this term will be given in future lessons.

Nim Value

Let us return to the original Square Game, which can be played on any number n. Now, to each n we assign a value *m to it, where m is a non-negative integer. Called the Nim value of n, it is recursively defined as follows:

The number 0 has Nim value *0 (also written *0 = 0).

For each n, we look at all possible moves from n, and label the results $m_1, m_2, \dots$ . Suppose these numbers have Nim values $*r_1, *r_2, \dots$ respectively, then the Nim value of n is defined to be *r, where r is the smallest non-negative integer which does not occur among $r_1, r_2, \dots$ .

For convenience, we will write $r = mex(r_1, r_2, \dots)$ . E.g. mex(0, 1, 2, 6, 2, 10) = 3 since 3 is the smallest non-negative integer which does not occur in the list. Also, note that mex( ) = 0.

As a demonstration, suppose we have the Nim values for n=0, … 13:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	*1	0	*1	*2	0	*1	0	*1	*2	0	*1	0	*1	?

Let us compute the Nim value of 14: now 14 has moves to 13, 10, 5, which have Nim values of *1, 0, 0 respectively. Hence the Nim value of 14 is *2. Check that the Nim value of 15 is 0.

Now we are ready to describe our strategy for Nim Square (after which, the explanation will follow). Let’s consider the above configuration (1, 2, 9).

Replace every number by its corresponding Nim value: i.e. (*1, 0, *2).

Now imagine yourself playing this Nim game. What would be the appropriate response in this game? In our case it’s got to be *2 → *1.

Find the corresponding move in the Nim Square game. Here, *2 → *1 translates to 9 → 8. In general, there may be more than one possibility.

Thus, a correct response for the first player is (1, 2, 9) → (1, 2, 8).

Why Does It Work?

It’s natural to inquire how it works. Here’s a brief sketch:

Suppose it’s the winning player’s turn. He figures out the correct Nim move: *r → *s where s < r and *r refers to the Nim value of the number n. Why can he find a corresponding move in n? Because, by definition of the Nim value, any number s < r must appear as a Nim value for one of the moves n → m, since r is the smallest value which does not occur as a Nim value of its moves.
Suppose it’s the losing player’s turn. He makes a move corresponding to the Nim move *r → *s, where s ≠ r by definition of r. If s < r, then this move indeed does correspond to a move in the Nim game. But what if s > r? Then since the current number now has Nim value *s with s > r, there’s definitely a move from this number to another with Nim value *r. In short, it does not matter if the Nim value increases, we just bring it back down.

Example

Let’s look at our example of (1, 2, 9) again, and see how the game proceeds. Take note of the interplay between the original game and the corresponding Nim game.

First player		Second player
Nim Square	Nim	Nim Square	Nim
(1,2,9) → (1,2,8)	(1,0,2) → (1,0,1)	(1,2,8) → (1,2,4)	(1,0,1) → (1,0,2)
(1,2,4) → (1,2,3)	(1,0,2) → (1,0,1)	(1,2,3) → (1,1,3)	(1,0,1) → (1,1,*1)
(1,1,3) → (1,1,2)	(1,1,1) → (1,*1,0)	(1,1,2) → (1,0,2)	(1,1,0) → (*1,0,0)

As stated earlier, the winning player (in this case, the first player) always imagines himself to be playing the corresponding Nim game, then translates the Nim move to a move in the original game. Notice that unlike the case of Nim, the nim values here may actually bob up and down. If the losing second player attempts to raise the nim value and confuse the enemy, the first player calmly restores it back to the original nim value.

Exercises

Calculate the Nim values for Wythoff’s game for the positions (m, n), where $0 \le m, n \le 8$ .
Consider the game Wythoff’s Queens (also known as Wyt’s Queens). Each queen is allowed to move, in three possible directions, an arbitrary number of squares.

Now consider the chessboard below: at each player’s turn, he picks just one queen and moves an arbitrary number of moves either left, down or diagonally left-down. Each square is allowed to hold any number of queens at any time. The winner of the game is the one who puts all the queens on the lower-left square. Who wins in the board below?

Unlike a queen, a rook can only move downwards or left. Replace the queens in Wythoff’s Queens with rooks instead. Solve the resulting game Wythoff’s Rooks.
Compute the Nim values of the following:
- Square Game for n = 0, …, 20.
- Cube Game for n = 0, …, 20: the Cube Game is exactly the same as the Square Game, except that at each turn, a player must subtract a perfect cube instead of perfect square. E.g. 15 → 7 is a valid move since 8 is a perfect cube.
The game of White Knights is played on chessboard with a (surprise, surprise!) white knight situated on a square. Unlike a real chess knight, our knight here has only four valid moves (see diagram below). Furthermore, though he started off with some luggage, he has the uncanny habit of losing his belongings over time. Now, two players alternately move by doing (A) or (B), but not both:
1. Take away an arbitrary number of pieces of luggage.
2. Make a move of the knight.
Whoever makes the knight rest on one of the four home squares with no belongings, wins the game. Starting with the configuration below, who wins? If the first player wins, describe a winning move.

Consider the Nim-Square-Cube combination: start with three heaps of stones, of sizes (a, b, c) respectively. Two players alternately make a move by performing one of the three possible actions:
- removing any number of stones from the first heap; or
- removing a positive square number of stones from the second heap; or
- removing a positive cube number of stones from the third heap.
An example of a game play might be:

$(7,9,9) \to (7,5,9) \Rightarrow (7,4,9) \to (7,4,1) \Rightarrow (5,4,1) \to (5,0,1) \Rightarrow \dots$

In each of the following games, who wins – the first or second player? If the first player wins, find a good move for him.
- (3, 11, 17);
- (9, 14, 19).
The game of Binary Nim is played as follows: start with three heaps of stones of sizes (100000, 100001, 100002). At each player’s turn, he takes away a number of stones from one and only one heap, where the number is a power of two ( $2^r$ , for some non-negative integer r). Who wins in this game?

Combinatorial Game Theory III