Skip to main content

Section 3.3 Sprague-Grundy Values for Nim

In this subsection, we explore the Sprague-Grundy values for the game of Nim. Let's start simply. What is the Sprague-Grundy value for a single heap nim game \(\nim{n}\text{?}\) Nim position \(\nim{1}\) only has one follower: \(\nim{0}\text{.}\) Therefore

\begin{equation*} \g(\nim{1}) = \mex \{ \g( \nim{0}) \} = \mex \{ 0 \} = 1. \end{equation*}

Nim position \(\nim{2}\) has two followers: \(\cF( \nim{2} ) = \{ \nim{0}, \nim{1} \}\text{,}\) so that

\begin{equation*} \g(\nim{2}) = \mex \{ \g( \nim{0}) , \g( \nim{1}) \} = \mex \{ 0, 1 \} = 2. \end{equation*}

Continuing this way, we find that

\begin{equation*} \g(\nim{3}) = \mex \{ \g(\nim{0}), \g(\nim{1}) , \g(\nim{2}) \} = \mex \{ 0, 1, 2 \} = 3. \end{equation*}

This same proof applies in general, and gives us the following lemma.

We leave this straight-forward proof by strong induction for the exercises.

You may be a little disappointed that the Sprague-Grundy value of a nim heap is so \(\ldots\) boring. But this is actually great news! Single heap Nim is the most fundamental combinatorial game, so we expect that its Sprague-Grundy values should be the easiest to calculate. Let's move on to some small two-heap games of Nim. We must build up these values recursively. Clearly

\begin{equation*} \g(\nim{0} \oplus \nim{0}) = 0, \end{equation*}

because \(\nim{0} \oplus \nim{0}\) is a terminal position, and

\begin{equation*} \g(\nim{n} \oplus \nim{0}) = \g( \nim{0} \oplus \nim{n}) = n \end{equation*}

because \(\nim{0} \oplus \nim{n}\) plays just like the one-pile game \(\nim{n}\text{.}\) Recursively, we have

\begin{equation*} \begin{array}{rcl} \g(\nim{1} \oplus \nim{1} ) &=& \mex \{ g(\nim{1} \oplus \nim{0}), g(\nim{0} \oplus \nim{1}) \} = \mex \{ 1, 1 \} = 0, \\ g(\nim{2} \oplus \nim{1} ) &=& \mex \{ g(\nim{1} \oplus \nim{1}), g(\nim{0} \oplus \nim{1}), g(\nim{2} \oplus \nim{0}) \} = \mex \{ 0,1,2 \} = 3, \\ g(\nim{2} \oplus \nim{2} ) &=& \mex \{ g(\nim{1} \oplus \nim{2}), g(\nim{0} \oplus \nim{2}), g(\nim{2} \oplus \nim{1}), g(\nim{2} \oplus \nim{0}) \} = \mex \{ 3, 2, 3, 2 \} = 0. \end{array} \end{equation*}

This is already getting pretty messy. The best way to calculate the Sprague-Grundy value is to use a game tree. We do this for nim position \(\nim{2} \oplus \nim{1}\) in Figure 3.3.2. The tree structure clearly shows the followers of each position. The recursive nature of the Sprague-Grundy definition is easy to chase through. Start by writing down value 0 at the leaves. Then move up the tree, calculating the mex of the followers of each position. Eventually, you will find the value of the root.

Figure 3.3.2. Calculating \(g(\nim{2} \oplus \nim{1})=3\) using the full game tree. Top: the game tree listing the positions and their followers. Bottom: the Sprague-Grundy values of those positions.

Continuing this way, we populate (3.3.1) for nim heaps \(*n \times *m\) up to size 3.

\begin{equation} \begin{array}{c|cccc} \g(\cdot) & \nim{0} & \nim{1} & \nim{2} & \nim{3} \\ \hline \nim{0} & 0 & 1 & 2 & 3 \\ \nim{1} & 1 & 0 & 3 & 2 \\ \nim{2} & 2 & 3 & 0 & 1 \\ \nim{3} &3 & 2 & 1 & 0 \end{array}\label{eqn-sgv}\tag{3.3.1} \end{equation}

As with the nim value, the Sprague-Grundy value is 0 if and only if we are in a \(\cP\)-position. In fact, if we compare these Sprague-Grundy values with the nim addition values in Table [cross-reference to target(s) "eqn-nim-add" missing or not unique], we see that they are identical! Could it be that these very different functions are actually one and the same? The answer is a resounding yes: \(n \oplus m = g(\nim{n} \oplus \nim{m})\) for all \(n,m \in \W.\) We prove this surprising fact in Section [cross-reference to target(s) "sec-sumgames" missing or not unique]. We close this section by revisiting our use of the game tree to find the Sprague-Grundy value. In Figure Figure 3.3.2, we see many positions that we recognize from our previous analysis. There is no need to expand the tree beneath a position with a known value. Instead, we can prune the tree at that position, and just write down the known Sprague-Grundy value for that position. This can save a lot of work, as show in Figure Figure 3.3.3 where we calculate \(g(\nim{1} \oplus \nim{4})\text{.}\)

Figure 3.3.3. Calculating \(g(\nim{2} \oplus \nim{4})=6\) using the partial game tree and the known values in Table (3.3.1). We stop drawing the game tree when we encounter positions with known values.

The definition of the Sprague-Grundy value is much more cumbersome that nim addition. So why should we bother with it? The reason is that the Sprague-Grundy function works for all impartial combinatorial games. Nim addition only applies to the game of Nim (and its disguised forms). In the next section, we will use the Sprague-Grundy value to find winning strategies are games that are distinct from Nim. We will see that for any combinatorial game, the Sprague-Grundy value is zero if and only if the position is a \(\cP\)-position.