Introductory Combinatorial Game Theory

Lesson 2 (Game of Nim)

 The game of Nim is played with a few piles of stones. At each player's turn, he/she may remove any number of stones, subjected to the condition that all the stones must be from a single pile. A player who is unable to remove any stones loses. An example of a game of Nim (with red/green highlighting the moves of A/B) is:

(7,8,10) (3,8,10) (3,2,10) (3,2,0) (2,2,0) (2,0,0) (0,0,0)

So the second player wins in this case. As we shall soon see, the above game is actually a win for the first player. We may perform analysis similar to the game earlier to determine whether each configuration is winning or losing. In practice however, it is far too tedious. Here we offer a straightforward method to compute the outcome of each game of Nim.

Suppose the game consists of piles (7, 8, 10). We arrange the piles as sums of powers of 2 as below:

  8 4 2 1 Sum
Pile 1   7
Pile 2       8
Pile 3     10

The first player A attempts to make a move so that the number of stars in each column is even. This is accomplished by taking away 5 sticks from the first pile, leaving:

  8 4 2 1 Sum
Pile 1       2
Pile 2       8
Pile 3     10

Now B is forced to break this parity, so that at least one column must be odd! Suppose for instance, he chooses 3 sticks from the third pile, so that we have

  8 4 2 1 Sum
Pile 1       2
Pile 2       8
Pile 3   7

Player A may now retaliate by taking 3 sticks from the second pile, so that the number of stars in each column is again even.

  8 4 2 1 Sum
Pile 1       2
Pile 2     5
Pile 3   7

Thus play goes on until player A leaves (0,0,0) and wins. Hence the key to winning Nim is as follows :

A configuration is losing if and only if the number of stars in each column is even. Otherwise, it is winning.



We shall give an explicit method of expressing the above results. Let m and n be two non-negative integers. We shall define the XOR operation (called the 'exclusive-or' operation) between m and n, denoted m * n. Write down the binary representations of m and n, one below the other and in the third row, write 0 if the 2 digits in the column are the same, and 1 if the 2 digits are different.

For example, to find 21 * 39, we write the binary representations as follows:

       010101
       100111
       110010

Since (110010)2 = 50, we have 21 * 39 = 50. Incidentally, the XOR operation is also known as addition without carry - it is not hard to see why this is named so. Now in general, we have the following rule:

A configuration is losing if and only if the configuration consists of k piles of sticks, containing m1, m2 ... mk sticks respectively, such that
m1 * m2 * ... * mk = 0

In the above example, we have 7 = (111)2, 8 = (1000)2, 10 = (1010)2. Thus, 7 * 8 * 10 = (101)2 which is not zero 0 and (7, 8, 10) must be a winning configuration.



Finding the Winning Move

Here we shall give an algorithm for finding the winning move (to a losing position) in a particular configuration. Suppose the piles consist of m1, m2 ... mk sticks respectively so that m = m1 * m2 * ... * mk is non-zero. Our objective is then to reduce one of the values mi so that their XOR-sum is zero. We shall illustrate the steps using the example, (19, 25, 12), with binary representations (10011)2, (11001)2 and (01100)2. Thus their XOR-sum is (00110)2 = 6.
  1. Find the first leading non-zero digit of the XOR-sum, and remove all digits prior to that column.
    Hence, in our example we have the digits in green:
           10011
           11001
           01100
           00110

  2. Among the remaining summands, find the one with the largest value.
    In our case, we must take the last summand which is (01100).

  3. Change this summand to the desired value.
    In order to obtain (00000) in the final XOR-sum, we must replace the green digits of the third summand by 010. This gives us (01010) which is 10 in binary. Hence, we must 2 sticks from the last pile.



Nim Variants

Now we shall describe some games which are actually variants of Nim.
  1. Mom has just baked a large almond cake which is divided into m-by-n unit squares. Unfortunately, one of the squares is mouldy and must not be consumed. Her two sons, Alfred and Bob, decide to play a game - at each turn one of them would cut the cake into two (by a single horizontal/vertical slice) and consume the part which does not contain the mouldy square. Whoever is left with the mouldy piece is deemed to have lost and must perform forfeit by washing the dishes. Suppose Alfred starts the game for the cake below. Who wins?

                       
                      
                      
                       
                      
                      
                      
                      
                      
                      
                      
                      


  2. In Northcott's Game, each player controls counters of a certain colour. At his turn, he may arbitrarily shift his counters left or right any number of squares. However, no counter may jump over another counter. Suppose red starts first. Who wins, or does the game end in a draw? (Many players do not know the point behind this game and end up shifting the counters aimlessly left and right. However, a skilled player can easily win.)

             
           
           
           
           
           
           
           


  3. Nimble - In the following strip, each square can contain at most one coin. On a player's turn, he must pick a coin and shift it an arbitrary number of squares to the left, without jumping over any other coin and without sliding it off the strip. Analyze the game : who wins?

                    


  4. Suppose we change the rules of Nim so that the person to take away the last stick loses. How would the analysis change? (Note : this is an example of misere play, which we shall explore in further detail in subsequent lessons.)


  5. Analyse the following Chinese Chess configuration.






    6. Back to the main page...