Games: The Sprague-Grundy Theorem

Section 3.5 The Sprague-Grundy Theorem

We frequently we have put together smaller combinatorial games to make bigger games. For example, we created multi-heap Nim by playing with multiple heaps simultaneously (although we can only move in one heap at a time). We make this idea more formal in this section, and refer to this construction as the sum of games. The main goal of this section is to prove the Sprague-Grundy Theorem, which shows how to find the Sprague-Grundy value of the sum of games. Once we have this result in hand, we can finally show that the nim sum of the pile sizes in Nim is truly equal to the Sprague-Grundy value of the game.

Given two combinatorial games $\cG_1, \cG_2\text{,}$ we can define a new game as follows. A player's turn consists of choosing one of the two games and then making a move in that game. The winner is the person who makes the last move overall (when there are no moves possible in either $\cG_1$ or $\cG_2$). The resulting game is called the sum of games, and is denoted by $\cG_1 \oplus \cG_2\text{.}$

Of course, we can also take the sum of any number of games $\cG_1, \cG_2, \ldots \cG_k\text{.}$ The game

\begin{equation*} \cG_1 \oplus \cG_2 \oplus \cdots \oplus \cG_k \end{equation*}

is defined as follows. The $\cG_i$ are called the component games. The positions are of the form $(X_1, X_2, \ldots , X_k)$ where $X_i \in \cG_i$ is a position in the corresponding component game. A valid move consists of picking one of the component games $\cG_i$ and making a valid move in that game:

\begin{equation*} (X_1, \ldots , X_{i-1}, X_i, X_{i+1}, \ldots, X_k) \rightarrow (X_1, \ldots , X_{i-1}, Z, X_{i+1}, \ldots , X_k) \end{equation*}

where $Z \in \cF(X_i)\text{.}$ We leave all the other games untouched. We play until every component game has completed, meaning that there are no moves available in any component. The winner is the player who makes the last move.

Looking back, we realize that we have been playing with sums of games all along. Multi-heap nim is a sum of single-heap nim games. Indeed, a move in nim consists of picking a heap (component) and then making a valid nim move for that heap (component). For example, the notation $* 3 \oplus *5 \oplus *8$ for a particular 3-pile nim is consistent with the more general notation for a sum of games. This multi-heap nim game is the sum of the component games $*3\text{,}$ $*5$ and $*8\text{.}$

This brings us to the Sprague-Grundy Theorem, which tells us how to find the Sprague-Grundy value of the sum of games. This theorem says that the Sprague-Grundy value of the sum of games equals the nim sum of the values of the component games!

Theorem 3.5.1.

Suppose that we have games $\cG_1, \cG_2, \ldots , \cG_n$ with respective Sprague-Grundy functions $g_1, g_2, \ldots g_n\text{.}$ Then the sum of games

\begin{equation*} \cG_1 \oplus \cG_2 \oplus \cdots \oplus \cG_n \end{equation*}

has Sprague-Grundy function

\begin{equation*} g(X_1, X_2, \ldots, X_n) = g_1(X_1) \oplus g_2(X_2) \oplus \cdots \oplus g_n(X_n) \end{equation*}

Proof.

The sum of games has some (unknown) Sprague-Grundy function $g: \cG \rightarrow \W\text{.}$ Let $X=(X_1, X_2, \ldots , X_n)$ be a position in the sum of games $\cG =\cG_1 \oplus \cG_2 \oplus \cdots \oplus \cG_n\text{.}$ Let $b \in \W$ be the value

\begin{equation*} b = g_1(X_1) \oplus g_2(X_2) \oplus \cdots \oplus g_n(X_n). \end{equation*}

In order to prove that $g(X)=b$ we must show that

For every $a \in \W$ such that $a < b\text{,}$ there is a follower $Y \in \cF(X)$ with $g(Y)=a\text{.}$
No follower $Z \in \cF(X)$ has value $g(Z)=b\text{.}$

First, we prove (1). Let $d = a \oplus b\text{.}$ Let $k$ be the number of digits in the binary expansion for $d\text{,}$ so that $2^{k-1} \leq d < 2^k$ and $d$ has a 1 in the $k$th position from the right. Since $a<b\text{,}$ the binary expansion of $b$ has a 1 in the $k$th position and $a$ has a 0 there.

Recall that $b =g_1(X_1) \oplus g_2(X_2) \oplus \cdots \oplus g_n(X_n)\text{,}$ which means that the binary expansion of at least one $g(X_i)$ also has a 1 in the $k$th position. To keep our argument simple, we assume that $i=1\text{,}$ because we can just rearrange the $X_i$ so that $i=1$ without effecting the gameplay of $G\text{.}$ We have $d \oplus g_1(X_1) < g_1(X_1)$ because the leftmost binary digit that changes the $k$th digit, which goes from 1 to 0. Because $g_1$ is the Sprague-Grundy function for $\cG_1\text{,}$ there is a move from $X_1$ to $Y_1 \in \cF_{\cG_1}(X)$ where $g_1(Y_1) = d \oplus g_1(X_1).$ The move

\begin{equation*} (X_1, X_2, \ldots, X_n) \rightarrow (Y_1, X_2, \ldots X_n) \end{equation*}

is a legal move in $\cG = \cG_1 \oplus \cG_2 \oplus \cdots \oplus \cG_n$ and $$ \begin{array}{rcl} & & g_1(Y_1) \oplus g_2(X_2) \oplus \cdots \oplus g_n(X_n) \\ &=& \big( d \oplus g_1(X_1) \big) \oplus g_2(X_2) \oplus \cdots \oplus g_n(X_n) \\ &=& d \oplus \big(g_1(X_1) \oplus g_2(X_2) \oplus \cdots \oplus g_n(X_n) \big)\\ &=& d \oplus b \, = \, a. \end{array} $$ In summary, we have found a follower of $(X_1, X_2, \ldots, X_n)$ whose Sprague-Grundy value is $a\text{.}$

Next, we prove (2). Let $s(X)$ be the size of the game tree rooted at $X\text{.}$ We prove (2) by strong induction on $s(X)\text{.}$ The statement holds for the terminal positions of the game, which form our base cases. Assume that

\begin{equation*} g\left( (Z_1, Z_2 , \ldots Z_n) \right) = g_1(Z_1) \oplus g_2( Z_2 ) \oplus \cdots \oplus g_n(Z_n) \end{equation*}

for every position $Z=(Z_1, Z_2, \ldots, Z_n)$ with $s(Z) < m\text{.}$

Consider $X=(X_1, X_2, \ldots , X_n)$ with $g(X)=b\text{.}$ Suppose that the game tree rooted at position $X$ has $s(X)=m$ total vertices. Assume for the sake of contradiction that (2) is false: that $X$ has a follower whose Sprague-Grundy value is $b\text{.}$ Again for simplicity of notation, we assume that this follower is obtained by a move in the first game. In other words, there exists $Y_1 \in \cF_{\cG_1}(X_1)$ such that $b= g ( Y_1, X_2 , \ldots, X_n)\text{.}$ Note that $s(Y_1, X_2 , \ldots, X_n) < m$ because we have moved down one level of the game tree. By induction $b= g_1( Y_1) \oplus g_2(X_2) \oplus \cdots g_n(X_n)\text{.}$ This means that

\begin{equation*} g_1( X_1) \oplus g_2(X_2) \oplus \cdots g_n(X_n) = g_1( Y_1) \oplus g_2(X_2) \oplus \cdots g_n(X_n) \end{equation*}

which forces $g_1(X_1) = g_1(Y_1)$ by the cancellation law of Lemma 2.2.4. This is a contradiction because $Y_1$ is a follower of $X_1$ in $\cG_1$ and $g_1$ is the Sprague-Grundy function of $\cG_1\text{.}$ This means our assumption is false, so (2) is true! This completes the proof.

This theorem also resolves the mystery behind why the nim sum of the heap sizes tell us who wins the game of Nim: this is just a special case of the Sprague-Grundy Theorem. We can finally prove that the nim sum of the heap sizes in Nim equals the Sprague-Grundy value of the game!

Corollary 3.5.2.

For the Nim position $*n_1 \oplus *n_2 \oplus \cdots \oplus *n_k\text{,}$ we have

\begin{equation*} g(*n_1 \oplus *n_2 \oplus \cdots \oplus *n_k) = g(n_1) \oplus g(n_2) \oplus \cdots \oplus g(n_k). \end{equation*}

Proof.

We showed that $g(*n)=n$ in Lemma 3.3.1. Theorem 3.5.1 states that we get the Sprague-Grundy value of the sum of games by taking the nim sum of their respective Sprague-Grundy values.