Feature Column from the AMS

Solving Nim

4. Solving Nim

The rules of Nim are extremely simple. If you play a few rounds with different configurations of numbers of stones you may glean some ways to play the game well. If a mathematician wants to analyze something complex, he/she will often try some special cases first to see what insight they bring. For Nim, one place to start would be how to play if there is only one pile of stones. The solution in this case, regardless of the number of stones, is to take them all. Your opponent has no stones to take, hence, no move, therefore you win!

What about the case of two piles with equal numbers of stones? If the two piles each have one stone, then you must take the stones in one pile and you will lose when your opponent takes the other pile. If one has two piles with equal numbers of stones and it is the first player's move, then the second player can take the same number of stones from the remaining pile as the first player did on the move before. This means that at each stage the second player will always have a followup move, and hence, must have a win! Despite these insights it's not so clear how to play when there are different numbers of stones in different piles.

In a tour de force using elementary mathematics in a brilliant way, C. L. Bouton, a mathematician at Harvard University, gave a complete analysis of Nim in 1902. His clever approach belies the possibility that seemingly hard and perplexing problems may not succumb to just the right way of looking at the problem. Bouton's complete analysis of Nim is built on representing the number of stones in each pile using binary numbers and displaying the result in vertical position. Now one adds the columns of the binary representations without carries (i.e. 1 added to 1 is 0 and no carry occurs), a process sometimes described as nim-addition. In the next section we will investigate ideas related to nim-addition in more detail. The result of this process gives a binary string which I will call the indicator of the current position of the game.

Bouton observed (and proved) that:

Fact 1. If the indicator of the current game position consists of all 0's, then any move will result in an indicator value which does not consist of all 0's.

Fact 2. If the indicator of the current game position does not consist of all 0's, then one can remove a number of stones from one of the piles so that the new position obtained will have an indicator consisting of all 0's.

These two observations mean that if the indicator value at the start of the game does not consist of all 0's, then the first player can win (but might lose if he/she does not play optimally), and the second player must lose if the first player plays optimally. Furthermore, the way to play so that one achieves a win from a winning position follows from Bouton's analysis. (This means that if you are looking at a position and know that you can not win, you can still exploit any mistake your opponent who could win with optimal play might make.) The first player should remove stones so that the resulting indicator is all 0's, and continue in this manner until each pile is empty.

Rather than go through Bouton's analysis in general, let's consider a typical example. First, note that an indicator added to itself (in binary without carries), results in an indicator with all 0's.

Suppose we have three piles of stones of size 37, 20, and 29. We first compute the binary representation for each of these numbers:

37 = 1 0 0 1 0 1
20 = 0 1 0 1 0 0
29 = 0 1 1 1 0 1

Adding the columns of these binary numbers without carries gives:

1 0 1 1 0 0

This binary string is the indicator value of the position. It does not consist of all zeros, and, thus, the first player has a winning position. The question is, what move or moves can the first player make to achieve the win? To answer this question we proceed as follows:

Locate the leftmost position with a 1 in the indicator value's binary string, and find a pile which has a 1 in this position of its binary representation (such a pile exists because there are no carries in nim-addition). In this case there is only one choice, the pile with 37 stones. Next we add (without carries) the binary representations of the other piles:

0 1 0 1 0 0
0 1 1 1 0 1

to get:

0 0 1 0 0 1.

The result is the string 0 0 1 0 0 1 which represents the number 9. Thus, if the first pile had exactly 9 stones, the new indicator would consist of all 0's. So we remove 37 - 9 = 28 stones from the first pile. By doing this, we are left with piles of stones of size 9, 20, and 29. When we write these numbers in binary we know that the addition of 20 and 29 gives the indicator string above (001001) which is 9, so when we add the binary string for 9 to the indicator string for the sum of 20 and 29 we must get a string with all 0's! Hence, the first player A has given player B a position with indicator string all 0's to move from. By Fact 1, any move B makes results in an indicator string which is not all 0's and by repeating the process just used above, player A has a move that will again give B a string with all 0's. Hence, A can win the game.

The reason why this approach always works is that when we perform the next move in a pile that has a 1 in the leftmost position of the indicator value, this pile must have enough stones to remove (to create a position with indicator value all 0's) because even if the indicator sum of all the remaining piles consists of i ones, its value is smaller than the binary number with a 1 followed by i zeros. For example, 1 1 1 1 has value 15 which is less than 1 0 0 0 0, which has decimal equivalent 16.

The method described above gives one move from an initial position where the indicator value is not all 0's to a position whose indicator value is all 0's. However, in many cases there will be other moves that will achieve the same goal. We will see in the next section that Bouton's analysis of one game in a striking but seemingly artificial manner is more much important and powerful than it might seem at first glance.

Bouton also gave an analysis for the misère version of Nim when the piles do not all have size 1, which is easy to treat. The way to play optimally is to play as if one is playing ordinary (standard) Nim until all the piles of stones have one stone with one exception. At this point take all the stones from the exceptional pile or all the stones except one with the goal of having an odd number of piles with one stone.

Bouton's elegant analysis of standard and misère Nim has tempted people to believe that the misère form of other impartial games can be played the way the standard version is played until the end when something specialized but simple can be done. However, Richard Guy (now retired from the University of Calgary) points out that this is not true. Despite a relatively recent analysis of some important misère version games by John Conway and Thane Plambeck using an idea of William Sibert's, finding good ways of solving misère games is still elusive.

It has become traditional in combinatorial game theory to classify positions of impartial games into two categories: N-positions and P-positions. These two categories stand for next player wins (N-positions) and previous player wins (P-positions). The way to think of this dichotomy is that when you are looking at the board and it's your move, if the position is an N-position, then by optimal play you can win; if the position you are looking at is a P-position, then no matter what move you make, when your opponent plays optimally you must lose. In particular, the position with no move at all is a P-position for standard play. When it's your move, N-positions make you happy, P positions do not. Connecting this with the W and L notation of the previous section, W-positions are P-positions and L-positions are N-positions. Bouton's analysis of Nim shows that the P-positions are those for which nim-addition on the sizes of the piles is 0. His analysis shows that the N-positions are those for which nim-addition on the sizes of the piles is greater than 0.