Sputsoft

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: 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 n sticks by \star n. The set representation of this trivial, but important type of game is

• \star 0 = \{\}.
• \star n = \{ \star (n-1), \star (n-2), \ldots, \star 0 \}.

For instance, \star 1 = \{\{\}\}, \star 2 = \{\{\},\{\{\}\}\}, and \star 3 = \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}. A graph representation of all possible game positions in a Nim game starting with the position \star 4 can be seen in Figure 2.

Figure 2: Graph representation of the Nim game

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

We see that G + \{\} = \{\} + G = G, 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 G + (\{\} + H) = (G + \{\}) + H and G + (H + \{\}) = (G + H) + \{\}, 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 \star 2 + \star 3 + \star 4. It is possible to write out its set representation but it is quite large.

Properties of Impartial Games

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

• {\cal S}_P 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 {\cal S}_N (\{G_1,\ldots,G_n\} \in {\cal S}_P \Leftrightarrow \forall k: G_k \in {\cal S}_N).
• {\cal S}_N consists of every position for which at least one move will lead to a position in {\cal S}_P (\{G_1,\ldots,G_n\} \in {\cal S}_N \Leftrightarrow \exists k: G_k \in {\cal S}_P).

Consider a graph in which every game position is a node and where there is an arc (directed edge) from position G to position g if and only if g \in G. 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 {\cal S}_P or {\cal S}_N in the process. We have, in this way, divided {\cal S} into two disjoint subsets.

Such a graph (png) for the game \star 2 + \star 3 + \star 4 would consists of 27 vertices and 114 arcs. Only 4 of the vertices represent games/positions in {\cal S}_P.

From the definitions of {\cal S}_P and {\cal S}_N we have something essential. Given a position in {\cal S}_N, the next player to move will always win, assuming a perfect play on his/her part. Similarly, given a position in {\cal S}_P, 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. G + G \in {\cal S}_P for any game G.

Next is the very important concept of equivalence between games.

Definition 2. The games G and H are equivalent, written G \sim H, if and only if G + X \in {\cal S}_P \Leftrightarrow H + X \in {\cal S}_P for all games X.

It is clear that \sim is an equivalence relation (it is reflexive, G \sim G, symmetric, G \sim H if and only if H \sim G, and transitive, G \sim F and F \sim H implies G \sim H).

Theorem 3. For all G, H \in {\cal S}_P we have G + H \in {\cal S}_P.

The following important theorem shows that any game in {\cal S}_P is equivalent to the terminal game.

Theorem 4. G \sim \{\} for all G \in {\cal S}_P.

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

Theorem 5. G \sim H \Leftrightarrow F + G \sim F + H for all games F, G, H.

Finally a theorem essential for the next section.

Theorem 6. G \sim H \Leftrightarrow G + H \in {\cal S}_P for all games G and H.

Characterizing Winning Positions

The goal is now to characterize {\cal S}_P or, equivalently, the games G for which G \sim \{\} (see Theorem 4). If a player always chooses a move that leads to a position G \in {\cal S}_P, then that player is going to win.

We do this by constructing a function E: {\cal S} \rightarrow \{0, 1, 2, \ldots \} such that

for all games G. This will identify {\cal S}_P since we will have G \sim \{\} \Leftrightarrow E(G) = 0.

Naturally we have E(\{\}) = 0. Let us now define E(G) using an inductive approach. Since G = \{\} is already taken care of, we let G=\{G_1, G_2, \ldots, G_n\} and assume that the values p_j=E(G_j) are known. Using Theorem 8 this means that G_j + \star p_j \in {\cal S}_P for all j. We now wish to find k such that G + \star k \in {\cal S}_P.

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

• G_j + \star k \sim \star p_j + \star k with k > p_j. We could now move to \star p_j + \star p_j \in {\cal S}_P, implying G_j + \star k \in {\cal S}_N.
• G_j + \star k \sim \star p_j + \star k with k < p_j. We could now move to \star k + \star k \in {\cal S}_P, implying G_j + \star k \in {\cal S}_N.
• G_j + \star k with k = p_j. We would like to avoid this situation since then G_j + \star k \in {\cal S}_P, implying G + \star k \in {\cal S}_N.
• G + \star k’ where k’ < k. We would now like to choose a position G_j for which E(G_j) = k’ since then G_j + \star k’ \in {\cal S}_P, implying G + \star k \in {\cal S}_P.

If these points are fulfilled then, since G_j and k’ could be chosen arbitrarily, we have covered all possible moves. We would then have G + \star k \in {\cal S}_P.

These points actually give away the solution:

Theorem 7 (The Sprague–Grundy Theorem). For any impartial game G we have G \sim \star E(G) with

where \mbox{mex}(S) = \min\{k \mid k \geq 0 \mbox{ and } k \notin S \} is the “minimal excludant” of S.

Winning Nim

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

and since

for all games G and H, we have

This means that if we know the value of E(\star x + \star y) for all x, y \geq 0, then we can compute E(G) of every Nim-game G. Let us introduce the notation x \circ y = E(\star x + \star y). Using the Sprague–Grundy Theorem we have

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

This looks suspiciously like the binary exclusive-or (XOR) operator \oplus. 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 x = \mbox{mex}(S) and y = \mbox{mex}(T). Then

where S \oplus y = \{ x \oplus y \mid x \in S \} and x \oplus T = \{ x \oplus y \mid y \in T \}.

From this theorem we see that if S = \{ 0, 1, \ldots, x-1 \} and T = \{ 0, 1, \ldots, y-1 \} we have the desired equality. We now have

and thus

Recalling the definitions of {\cal S}_P and {\cal S}_N we now have the ultimate strategy for Nim:

• Given a position G = \star p_1 + \star p_2 + \cdots + \star p_n with p_1 \oplus p_2 \oplus \cdots \oplus p_n \neq 0 (G \in {\cal S}_N) it is possible to choose a move G’ = \star p’_1 + \star p’_2 + \cdots + \star p’_n \in G such that p’_1 \oplus p’_2 \oplus \cdots \oplus p’_n = 0 (G’ \in {\cal S}_P).
• Given a position G = \star p_1 + \star p_2 + \cdots + \star p_n with p_1 \oplus p_2 \oplus \cdots \oplus p_n = 0 (G \in {\cal S}_P), any move will lead to a position G’ = \star p’_1 + \star p’_2 + \cdots + \star p’_n \in G for which p’_1 \oplus p’_2 \oplus \cdots \oplus p’_n \neq 0 (G’ \in {\cal S}_N).

In other words, if a game has p_1 \oplus p_2 \oplus \cdots \oplus p_n \neq 0 then the player to move is guaranteed to win—provided a perfect play on his/her part. On the other hand, if p_1 \oplus p_2 \oplus \cdots \oplus p_n = 0 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, \oplus, 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 \star n-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 \star n-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.