janmr blog

The Game of Nim

Introduction

I have known the game of Nim for many years. Once, a friend of mine beat me repeatedly in one game after another and I had no idea how he did it. Looking back, I am not sure he knew the perfect Nim-strategy, but he knew enough to frustrate me immensely. A year ago or so, I was flicking through Fascicle 1 of The Art of Computer Programming, Volume 4 by Donald E. Knuth, and I read about the strategy of Nim. The strategy is very simple but I could not possibly understand why it worked.

This article shows why the strategy works, introducing the necessary game theory along the way.

Nim

Nim is played by two players who take turns moving. The initial game position for Nim consists of a number of piles, each containing any number of sticks. A player moves by removing any positive number of sticks from a single pile, possibly emptying the pile. The first player to face an empty position, consisting of no sticks at all, loses. An example of a game of Nim, starting with three piles with 2, 3, and 4 sticks, can be seen in Figure 1.

Figure 1
Figure 1. A possible gameplay in Nim.

Nim is an important special case of impartial games.

Impartial Games

A combinatorial game is a game for two players where both players have perfect information, that is, everything about the game is visible at all times, and where no part of the game is left to chance. An impartial game is a combinatorial game with further restrictions:

  • Two players who take turns at moving.
  • The legal moves depend only on the position and not which player it is to move.
  • A player unable to move loses.
  • Any game will come to an end, that is, no sequence of moves are possible for which the game will continue forever.

Let an impartial game be identified by *the set of all the (sub)games that every legal move can lead to*. Note the recursive nature of this definition. The terminal game, where no legal move can be made, is thus the empty set, . As an aside, note how any (finite) set of sets is a game.

In Nim, we represent a game consisting of a single pile of sticks by . The set representation of this trivial, but important type of game is

  • .
  • .

For instance, , , and . A graph representation of all possible game positions in a Nim game starting with the position can be seen in Figure 2.

Figure 2
Figure 2. Graph representation of the Nim game

We can also construct a new game by adding two games. Given two games and the notation means that a move can be chosen from either or . If, e.g., a move is made in that leads to the game , the game for the added game becomes . In general we have

We see that , as it should be. These special cases, and the fact that set union is commutative, makes position adding commutative too. Likewise, since union is associative and and , we also have associativity for game adding.

Recall the initial Nim game in Figure 1 with three piles of 2, 3, and 4 sticks, respectively. We can now write that position as . It is possible to write out its set representation but it is quite large.

Properties of Impartial Games

Given an impartial game, let be the set of all possible game positions. We now introduce two subsets of in the following way:

  • consists of the terminal position , from where no legal move can be made, and every position for which every move will lead to a position in ().
  • consists of every position for which at least one move will lead to a position in ().

Consider a graph in which every game position is a node and where there is an arc (directed edge) from position to position if and only if . Since any game will terminate, this graph contains no cycles and is thus a Directed Acyclic Graph (DAG). This makes it possible to topologically sort the nodes/positions, starting from the terminal position and working backwards through every possible position, placing each position in or in the process. We have, in this way, divided into two disjoint subsets.

Such a graph for the game would consists of 27 vertices and 114 arcs. Only 4 of the vertices represent games/positions in .

From the definitions of and we have something essential. Given a position in , the next player to move will always win, assuming a perfect play on his/her part. Similarly, given a position in , the previous player will always win, again assuming a perfect play.

We now move on to different facts about impartial games. Some of them are interesting and useful in themselves, others simply stepping stones towards showing the central theorem, the Sprague–Grundy Theorem.

Theorem 1. for any game .

We use structural induction (we consider a topologically sorted graph of a game from the terminal game and backwards). For the statement is trivially true. Now assume that where for . If, in the position , the player to move chooses the position , the other player can make the same move in the “other part”, leading to , which was assumed to lie in . This shows that and since was chosen arbitrarily .

Next is the very important concept of equivalence between games.

Definition 2. The games and are equivalent, written , if and only if for all games .

It is clear that is an equivalence relation (it is reflexive, , symmetric, if and only if , and transitive, and implies ).

Theorem 3. For all we have .

Again, we use structural induction. If the result follows easily. Now assume that for all where and . If a move is made from to , where , we can go to a position where and . This last position lies in by assumption and then does too. By symmetry the same arguments can be used if a move is made in the part.

The following important theorem shows that any game in is equivalent to the terminal game.

Theorem 4. for all .

We need to show for all games . First we show so let and consider the position . But that follows immediately from Theorem 3.

Next we show which is equivalent to . So let and consider the position . We can now make a move to where and . From Theorem 3 follows that and thus .

The next theorem shows that we can add and “subtract” on both sides of a .

Theorem 5. for all games .

Let , meaning for all games . Now assume for some and by setting we have , showing that for all . Analogously we can show the same statement with and interchanged. Hence, . Now assume . We then have .

Finally a theorem essential for the next section.

Theorem 6. for all games and .

.

Characterizing Winning Positions

The goal is now to characterize or, equivalently, the games for which (see Theorem 4). If a player always chooses a move that leads to a position , then that player is going to win.

We do this by constructing a function such that

for all games . This will identify since we will have .

Naturally we have . Let us now define using an inductive approach. Since is already taken care of, we let and assume that the values are known. Using Theorem 8 this means that for all . We now wish to find such that .

We can get an idea of what we need from if we let be fixed and then consider the four possible classes of moves from the position :

  • with . We could now move to , implying .
  • with . We could now move to , implying .
  • with . We would like to avoid this situation since then , implying .
  • where . We would now like to choose a position for which since then , implying .

If these points are fulfilled then, since and could be chosen arbitrarily, we have covered all possible moves. We would then have .

These points actually give away the solution:

Theorem 7 (The Sprague–Grundy Theorem). For any impartial game we have with

where is the “minimal excludant” of .

Winning Nim

Let us now apply the theory to Nim. Since every game of Nim has the form

and since

for all games and , we have

This means that if we know the value of for all , then we can compute of every Nim-game . Let us introduce the notation . Using the Sprague–Grundy Theorem we have

This makes it possible to tabulate the values of the -operator:

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

This looks suspiciously like the binary exclusive-or (XOR) operator . And indeed it is, as shown by the following theorem (the theorem is slightly more general than needed, but it is actually a bit more concise this way).

Theorem 8 (The Sprague–Grundy Theorem). Let and . Then

where and .

We need to show two things: (a) and (b) for all .

To show (a) we assume for some . But this implies and by the definition of . Similarly is impossible. So .

To show (b) we choose a such that . We now set and where , , and are binary strings and . Let now and where (the ()th bits of and must be different and we assume, without loss of generality, that has a ). Note how we have and therefore and thus . We now see that .

From this theorem we see that if and we have the desired equality. We now have

and thus

Recalling the definitions of and we now have the ultimate strategy for Nim:

  • Given a position with () it is possible to choose a move such that ().
  • Given a position with (), any move will lead to a position for which ().

In other words, if a game has then the player to move is guaranteed to win—provided a perfect play on his/her part. On the other hand, if then the player to move can only hope that the other player makes a mistake.

Finishing Remarks

According to Fascicle 1 of The Art of Computer Programming, Volume 4, by Donald E. Knuth, the binary operator XOR, , was known long before operators such as binary AND and binary OR, because it is so intimately tied to the Nim game. For the same reason, the XOR operator has often been called the “nim sum”.

Note how the definition of the -games resembles one of the standard ways to construct the natural numbers. Other than its obvious relation to the Nim-game, this is perhaps one of the reasons that -games are sometimes called nimbers. Generalized numbers and games are the subject of the book On Numbers and Games by John H. Conway.

Wikipedia has some relevant pages in relation to this article, see impartial game, combinatorial game theory, and Sprague–Grundy Theorem. See also the blog entry on The Universe of Discourse.