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 The Art of Computer Programming, Volume 4A 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 nn sticks by n\star n. The set representation of this trivial, but important type of game is

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

For instance, 1={{}}\star 1 = \{\{\}\}, 2={{},{{}}}\star 2 = \{\{\},\{\{\}\}\}, and 3={{},{{}},{{},{{}}}}\star 3 = \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}. A graph representation of all possible game positions in a Nim game starting with the position 4\star 4 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 GG and HH the notation G+HG + H means that a move can be chosen from either GG or HH. If, e.g., a move is made in GG that leads to the game gGg \in G, the game for the added game becomes g+Hg + H. In general we have

G+H={G+hhH}{g+HgG}G + H = \{ G + h \mid h \in H \} \cup \{ g + H \mid g \in G \}

We see that G+{}={}+G=GG + \{\} = \{\} + 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+{})+HG + (\{\} + H) = (G + \{\}) + H and G+(H+{})=(G+H)+{}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 2+3+4\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 S\mathcal{S} be the set of all possible game positions. We now introduce two subsets of S\mathcal{S} in the following way:

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

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

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

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

Proof. We use structural induction (we consider a topologically sorted graph of a game from the terminal game and backwards). For G={}G = \{\} the statement is trivially true. Now assume that G={G1,G2,,Gn}G = \{ G_1, G_2, \ldots, G_n \} where Gk+GkSPG_k + G_k \in \mathcal{S}_P for k=1,2,,nk = 1, 2, \ldots, n. If, in the position G+GG + G, the player to move chooses the position Gj+GG_j + G, the other player can make the same move in the “other part”, leading to Gj+GjG_j + G_j, which was assumed to lie in SP\mathcal{S}_P. This shows that Gj+GSNG_j + G \in \mathcal{S}_N and since jj was chosen arbitrarily G+GSPG + G \in \mathcal{S}_P. ◼

Next is the very important concept of equivalence between games.

Definition 2. The games GG and HH are equivalent, written GHG \sim H, if and only if G+XSPH+XSPG + X \in \mathcal{S}_P \Leftrightarrow H + X \in \mathcal{S}_P for all games XX.

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

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

Proof. Again, we use structural induction. If G={}G = \{\} the result follows easily. Now assume that G+HSPG'' + H \in \mathcal{S}_P for all GSPG'' \in \mathcal{S}_P where GGG'' \in G' and GGG' \in G. If a move is made from G+HG + H to G+HG' + H, where GGG' \in G, we can go to a position G+HG'' + H where GGG'' \in G' and GSPG'' \in \mathcal{S}_P. This last position lies in SP\mathcal{S}_P by assumption and then G+HSPG + H \in \mathcal{S}_P does too. By symmetry the same arguments can be used if a move is made in the HH part. ◼

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

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

Proof. We need to show G+XSPXSPG + X \in \mathcal{S}_P \Leftrightarrow X \in \mathcal{S}_P for all games XX. First we show XSPG+XSPX \in \mathcal{S}_P \Rightarrow G + X \in \mathcal{S}_P so let XSPX \in \mathcal{S}_P and consider the position G+XG + X. But that G+XSPG + X \in \mathcal{S}_P follows immediately from Theorem 3.

Next we show G+XSPXSPG + X \in \mathcal{S}_P \Rightarrow X \in \mathcal{S}_P which is equivalent to XSNG+XSNX \in \mathcal{S}_N \Rightarrow G + X \in \mathcal{S}_N. So let XSNX \in \mathcal{S}_N and consider the position G+XG + X. We can now make a move to G+XG + X' where XXX' \in X and XSPX' \in \mathcal{S}_P. From Theorem 3 follows that G+XSPG + X' \in \mathcal{S}_P and thus G+XSNG + X \in \mathcal{S}_N. ◼

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

Theorem 5. GHF+GF+HG \sim H \Leftrightarrow F + G \sim F + H for all games F,G,HF, G, H.

Proof. Let GHG \sim H, meaning G+XSPH+XSPG + X \in \mathcal{S}_P \Leftrightarrow H + X \in \mathcal{S}_P for all games XX. Now assume F+G+YSPF + G + Y \in \mathcal{S}_P for some YSY \in \mathcal{S} and by setting X=F+YX = F + Y we have H+X=H+F+YSH + X = H + F + Y \in \mathcal{S}, showing that F+G+YSPF+H+YSPF + G + Y \in \mathcal{S}_P \Rightarrow F + H + Y \in \mathcal{S}_P for all YSY \in \mathcal{S}. Analogously we can show the same statement with GG and HH interchanged. Hence, F+GF+HF + G \sim F + H. Now assume F+GF+HF + G \sim F + H. We then have G=G+{}G+(F+F)=(G+F)+F(H+F)+F=H+(F+F)H+{}=HG = G + \{\} \sim G + (F + F) = (G + F) + F \sim (H + F) + F = H + (F + F) \sim H + \{\} = H. ◼

Finally a theorem essential for the next section.

Theorem 6. GHG+HSPG \sim H \Leftrightarrow G + H \in \mathcal{S}_P for all games GG and HH.

Proof. GHG+HH+H{}G+HSPG \sim H \Leftrightarrow G + H \sim H + H \sim \{\} \Leftrightarrow G + H \in \mathcal{S}_P. ◼

Characterizing Winning Positions

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

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

GE(G)G \sim \star E(G)

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

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

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

  • Gj+kpj+kG_j + \star k \sim \star p_j + \star k with k>pjk > p_j. We could now move to pj+pjSP\star p_j + \star p_j \in \mathcal{S}_P, implying Gj+kSNG_j + \star k \in \mathcal{S}_N.
  • Gj+kpj+kG_j + \star k \sim \star p_j + \star k with k<pjk < p_j. We could now move to k+kSP\star k + \star k \in \mathcal{S}_P, implying Gj+kSNG_j + \star k \in \mathcal{S}_N.
  • Gj+kG_j + \star k with k=pjk = p_j. We would like to avoid this situation since then Gj+kSPG_j + \star k \in \mathcal{S}_P, implying G+kSNG + \star k \in \mathcal{S}_N.
  • G+kG + \star k' where k<kk' < k. We would now like to choose a position GjG_j for which E(Gj)=kE(G_j) = k' since then Gj+kSPG_j + \star k' \in \mathcal{S}_P, implying G+kSPG + \star k \in \mathcal{S}_P.

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

These points actually give away the solution:

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

E(G)=mex({E(G)GG}),E(G) = \text{mex}(\{ E(G') \mid G' \in G \}),

where mex(S)=min{kk0 and k∉S}\text{mex}(S) = \min\{k \mid k \geq 0 \text{ and } k \not\in S \} is the “minimal excludant” of SS.

Winning Nim

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

G=p1+p2++pn,pj0,G = \star p_1 + \star p_2 + \cdots + \star p_n, \quad p_j \geq 0,

and since

E(G+H)=E(E(G)+E(H))E(G + H) = E(\star E(G) + \star E(H))

for all games GG and HH, we have

E(G)=E(p1+E(p2++E(pn1+pn))).E(G) = E(\star p_1 + \star E(\star p_2 + \cdots + \star E(\star p_{n-1} + \star p_n) \cdots )).

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

xy=mex({x(y1),,x1,x0}{(x1)y,,1y,,0y}).x \circ y = \text{mex}(\{ x \circ (y-1), \ldots, x \circ 1, x \circ 0 \} \cup \{ (x-1) \circ y, \ldots, 1 \circ y, \ldots, 0 \circ y \}).

This makes it possible to tabulate the values of the \circ-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 \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=mex(S)x = \text{mex}(S) and y=mex(T)y = \text{mex}(T). Then

xy=mex((Sy)(xT)),x \oplus y = \text{mex} \left( (S \oplus y) \cup (x \oplus T) \right),

where Sy={xyxS}S \oplus y = \{ x \oplus y \mid x \in S \} and xT={xyyT}x \oplus T = \{ x \oplus y \mid y \in T \}.

Proof. We need to show two things: (a) xy∉(Sy)(xT)x \oplus y \not\in (S \oplus y) \cup (x \oplus T) and (b) k(Sy)(xT)k \in (S \oplus y) \cup (x \oplus T) for all 0k<xy0 \leq k < x \oplus y.

To show (a) we assume xy=syx \oplus y = s \oplus y for some sSs \in S. But this implies s=xs = x and x∉Sx \not\in S by the definition of mex\text{mex}. Similarly xyxTx \oplus y \in x \oplus T is impossible. So xy∉(Sy)(xT)x \oplus y \not\in (S \oplus y) \cup (x \oplus T).

To show (b) we choose a kk such that 0k<xy0 \leq k < x \oplus y. We now set xy=(α1α)2x \oplus y = (\alpha 1 \alpha')_2 and k=(α0α)2k = (\alpha 0 \alpha'')_2 where α\alpha, α\alpha', and α\alpha'' are binary strings and α=α|\alpha'| = |\alpha''|. Let now x=(β1β)2x = (\beta 1 \beta')_2 and y=(γ0γ)2y = (\gamma 0 \gamma')_2 where β=γ=α|\beta| = |\gamma| = |\alpha| (the (α+1|\alpha|+1)th bits of xx and yy must be different and we assume, without loss of generality, that xx has a 11). Note how we have βγ=α\beta \oplus \gamma = \alpha and therefore ky=(β0β)2<xk \oplus y = (\beta 0 \beta'')_2 < x and thus kySk \oplus y \in S. We now see that k=(ky)ySyk = (k \oplus y) \oplus y \in S \oplus y. ◼

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

E(p1+p2++pn)=p1p2pn,E(\star p_1 + \star p_2 + \cdots + \star p_n) = p_1 \oplus p_2 \oplus \cdots \oplus p_n,

and thus

G=p1+p2++pnSPp1p2pn=0.G = \star p_1 + \star p_2 + \cdots + \star p_n \in \mathcal{S}_P \quad \Leftrightarrow \quad p_1 \oplus p_2 \oplus \cdots \oplus p_n = 0.

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

  • Given a position G=p1+p2++pnG = \star p_1 + \star p_2 + \cdots + \star p_n with p1p2pn0p_1 \oplus p_2 \oplus \cdots \oplus p_n \neq 0 (GSNG \in \mathcal{S}_N) it is possible to choose a move G=p1+p2++pnGG' = \star p'_1 + \star p'_2 + \cdots + \star p'_n \in G such that p1p2pn=0p'_1 \oplus p'_2 \oplus \cdots \oplus p'_n = 0 (GSPG' \in \mathcal{S}_P).
  • Given a position G=p1+p2++pnG = \star p_1 + \star p_2 + \cdots + \star p_n with p1p2pn=0p_1 \oplus p_2 \oplus \cdots \oplus p_n = 0 (GSPG \in \mathcal{S}_P), any move will lead to a position G=p1+p2++pnGG' = \star p'_1 + \star p'_2 + \cdots + \star p'_n \in G for which p1p2pn0p'_1 \oplus p'_2 \oplus \cdots \oplus p'_n \neq 0 (GSNG' \in \mathcal{S}_N).

In other words, if a game has p1p2pn0p_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 p1p2pn=0p_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 The Art of Computer Programming, Volume 4A, 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 n\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 n\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.