Combinatorial Game Theory II

Lesson 2

In this lesson, we will focus on a special type of game called Nim. Although it’s only one out of infinitely many possible games, understanding it in depth will be very beneficial in analysing a much larger class of games, known as impartial games. (The exact definition of this term is deferred until a later lesson.)

The rules of this game are as follows:

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 as many stones as he wants from it, possibly even emptying the heap. However, he can remove stones from one and only one heap.

Here is an example of a game between two players:

(3,5,\mathbf{8}) \to (3,\mathbf{5},1)\Rightarrow (\mathbf{3},2,1) \to (0,\mathbf{2},1) \Rightarrow (0,\mathbf{1},1) \to (0,0,\mathbf{1})\Rightarrow (0,0,0).

Thus the second player wins in this match.

Of course, we could do our analysis as in the previous lesson: to check whether (3, 5, 8) is winning or losing, we could iteratively compute the status of (a, b, c) for 0 \le a \le 3, 0 \le b \le 5, 0 \le c \le 8. But this would require us to compute the status for 3 × 5 × 8 = 120 positions, even for a simple configuration like (3, 5, 8), which is way too much work. Thankfully, there is a beautiful solution for the problem.

Binary Representation

If you understand what binary representation is, you may skip this section entirely. The crux of the matter is the following result:

Every positive integer is uniquely representable as a sum of distinct powers of two (i.e. 1, 2, 4, 8, 16 … ).

The keyword here is “distinct”. To write a number n as a sum of distinct powers of 2, let m=2^r be the largest power of 2 which does not exceed n. Now consider the difference d = n - 2^r. If d = 0, then n=2^r and there is nothing left to do. Otherwise, d > 0. We claim that d < 2^r; indeed, if d \ge 2^r then n = d+2^r would be at least 2^r + 2^r = 2^{r+1} which contradicts the maximality of r. (q.e.d.)

Example : let’s take n=25. To take the largest power of two which is at most 25, we have to pick 2^4=16. The difference is:

25 - 2^4 = 9.

Now do the same with 9: the largest power of two not exceeding it is 2^3 = 8 and the difference is:

9 - 2^3 = 1.

Finally 1 = 2^0 so we can write 25 = 2^4 + 2^3 + 2^0. We will write this more compactly as follows:

25 = (11001)_2.

This is known as the binary representation of 25. We can add as many leading zeros as we want:

25 = (11001)_2 = (011001)_2 = (0011001)_2 = \ldots

which is akin to 37 = 037 = 0037 = … in decimal representation.

Solving Nim

Now we are ready to describe our strategy for playing Nim perfectly. For simplicity, we consider only three heaps of stones: (a, b, c), where a, b, c > 0, and take the example a = 17, b = 25, c = 13. First, write a, b, c in binary notation and align them on the right. E.g.

17 = (10001) = 16 +           1
25 = (11001) = 16 + 8 +       1
13 = (01101) =      8 + 4 +   1

Now count the number of ones in each column and note their parities. In our example, we have (from left to right): 2, 2, 1, 0, 3. Their parities are even, even, odd, even, odd respectively. The big theorem is as follows:

The above Nim configuration is a losing position if and only if there is an even number of ones in each column.

Hence, the above configuration is winning (i.e. first player wins) since there are an odd number of ones in the rightmost column. One naturally asks for a proof to this theorem. Instead of a rigourous proof, we will instead explain a winning strategy, from which the proof should be apparent. For now, let’s look at another example.

Example

Consider the Nim game (30, 15, 27, 10). To compute its status, let us write:

30 = (11110) = 16 + 8 + 4 + 2
15 = (01111) =      8 + 4 + 2 + 1
27 = (11011) = 16 + 8 +     2 + 1
10 = (01010) =      8 +     2

Now there are an even number of ones in every column, so the second player wins.

Playing Nim

Knowing the status of the game position is just half the battle won – you need to know how to exploit a winning position to obtain an eventual victory. Below, we will explain how to do this, by looking at the case of (17, 25, 13) above. As before, write:

17 = (10001)
25 = (11001)
13 = (01101)

Starting from the leftmost position, find the first column which has an odd number of ones:

17 = (10 [0] 01)
25 = (11 [0] 01)
13 = (01 [1] 01)

Next, pick a heap number m which has a one in that column. Such a heap must exist, since otherwise, there’d be no 1’s in that column (and thus, an even number of ones). In our example, we must take m = 13. Now remove the binary digits of m from column to the right.

17 = (10 001)
25 = (11 001)
 ? = (01 ***)

Fill in our desired binary digits in order to have an even number of ones in each column:

17 = (10 001)
25 = (11 001)
 ? = (01 000)

Note that this is a losing position by our theorem, so it would do us good to leave this configuration for our opponent. Also, such a move is always possible since we’re flipping the ‘1’ in column c to ‘0’, and no bits to the left of c are changed. So the resulting number is always smaller than m. Since (1000) = 8 in binary, in our example, a good move would be:

(17, 25, 13) → (17, 25, 8).

Thus, we see that given a winning position, it is always possible to move to a losing position for the opponent. That’s only half the theory; we also need to explain why every move from a losing position results in a winning one.

The XOR Operation

Given a Nim game G = (n_1, n_2, \dots, n_r) if n_1, n_2, \dots, n_{r-1} are fixed, then there’s only one possible n_r for which G is a losing position. Indeed, suppose r= 3 and n_1 = 37, n_2 = 52. Then to compute n_3, we write the binary representations:

n1 = 37 = (100101)
n2 = 52 = (110100)
n3 = ?? = (******)

For each column of n_3, there’s a unique bit such that the total number of ones in that column is even:

n1 = 37 = (100101)
n2 = 52 = (110100)
n3 = ?? = (010001)

This shows that n_3 = 17 is unique and also gives us a recipe for calculating it: simply add the two numbers in binary and ignore any carry which might occur. Addition has never been easier! Just perform 0+0 = 0, 0+1 = 1+0 = 1, 1+1 = 0 and forget the carry. This operation is called XOR for exclusive-or, or sometimes just addition without carry and denoted by n_3 = n_1 \oplus n_2.

Incidentally, this also explains why every losing position must lead to a winning one in the next move. For if (n_1, n_2, \dots, n_r) were a losing position, then:

n_1 \oplus n_2 \oplus \dots \oplus n_r = 0.

Another way of writing this would be n_r = n_1 \oplus n_2 \oplus \dots \oplus n_{r-1}. Hence, if the first player makes a move from n_r, then it would result in n_r' \ne n_1 \oplus n_2 \oplus \dots \oplus n_{r-1} which is a winning position. Since there’s nothing special about the last heap n_r, any move would also result in a winning position.

Exercises

  1. Determine the status of the following Nim games:
    • (17, 18, 13),
    • (18, 14, 9, 21).
  2. For the games in Q1 where the first player wins, find a good move for him.
  3. Given that the Nim game (15, 20, 7, m) is a second-player win, what is m?
  4. Mum has baked a large almond cake which is divided into unit squares as below:

weirdcake

Unfortunately, the black square is burnt and inedible. Now Alice and Bob play a game as follows: each child alternately cuts the cake into two (possibly unequal) pieces, by a horizontal / vertical cut which is along a gridline. He/she then eats the edible piece and leaves the other behind. Whoever is left with the burnt piece is deemed to have lost and must do the dishes. If Alice starts the game, can she avoid the dishes?

  1. In Northcott’s Game, each player controls counters of a certain colour (either black or white). At his turn, he may arbitrarily shift his counters left or right any number of squares. However, no counter may jump over another counter. The player who’s unable to make any move loses. If black starts first, who wins, or will the game never end?

northcott

  1. In Misere Nim, the rules are exactly the same as Nim with one caveat: the person who takes the last stick loses the game instead of winning. Based on your understanding of classical Nim, find a strategy for Misere Nim. Explain how the strategies for the two games differ.
  2. (Hard) In Nimble, we have coins in the following strip: each square contains at most one coin. Play alternates between two players. Each player, at his turn, picks up any coin and shifts it to some position on its left – without sliding off the strip and without jumping over another coin. Does the first or second player win in the following configuration?

nimblegame

  1. Analyse the following Chinese Chess position : who wins?

cchessgame

  1. This interesting mathematical game is the subject of some research recently. The game of Chomp is played as follows: start with an m-by-n grid of squares. Two players take turns cutting out a piece of the board by (i) picking any unit square on the board, and (ii) cutting away all squares to its right and below. Whoever is forced to take the top-left square loses.

chompgame

  • Find a winning strategy for the first or second player on an n-by-n square board.
  • Find a winning strategy for the first or second player on an 2-by-n square board.
  • Determine whether the first player wins in the following configuration. (P. S. The answer depends on a and b.)

chompgame2

  • (Hard) Prove that, in general, the first player wins on any m-by-n grid if mn > 1.
This entry was posted in Notes and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s