Sprague–Grundy theorem


In combinatorial game theory, the Sprague-Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to. In the case of a game whose positions are indexed by the natural numbers, the sequence of nimbers for successive heap sizes is called the nim-sequence of the game.
The theorem and its proof encapsulate the main results of a theory discovered independently by R. P. Sprague and P. M. Grundy.

Definitions

For the purposes of the Sprague-Grundy theorem, a game is a two-player sequential game of perfect information satisfying the ending condition and the normal play condition.
At any given point in the game, a player's position is the set of moves they are allowed to make. As an example, we can define the zero game to be the two-player game where neither player has any legal moves. Referring to the two players as and , we would denote their positions as, since the set of moves each player can make is empty.
An impartial game is one in which at any given point in the game, each player is allowed exactly the same set of moves. Normal-play nim is an example of an impartial game. In nim, there are one or more heaps of objects, and two players, take turns choosing a heap and removing 1 or more objects from it. The winner is the player who removes the final object from the final heap. The game is impartial because for any given configuration of pile sizes, the moves Alice can make on her turn are exactly the same moves Bob would be allowed to make if it were his turn. In contrast, a game such as checkers is not impartial because, supposing Alice were playing red and Bob were playing black, for any given arrangement of pieces on the board, if it were Alice's turn, she would only be allowed to move the red pieces, and if it were Bob's turn, he would only be allowed to move the black pieces.
Note that any configuration of an impartial game can therefore be written as a single position, because the moves will be the same no matter whose turn it is. For example, the position of the zero game can simply be written, because if it's Alice's turn, she has no moves to make, and if it's Bob's turn, he has no moves to make either.
A move can be associated with the position it leaves the next player in.
Doing so allows positions to be defined recursively. For example, consider the following game of Nim played by Alice and Bob.

Example Nim Game

The special names,, and referenced in our example game are called nimbers. In general, the nimber corresponds to the position in a game of nim where there are exactly objects in exactly one heap.
Formally, nimbers are defined inductively as follows: is,, and for all,.
While the word nimber comes from the game nim, nimbers can be used to describe the positions of any finite, impartial game, and in fact, the Sprague-Grundy theorem states that every instance of a finite, impartial game can be associated with a single nimber.

Combining Games

Two games can be combined by adding their positions together.
For example, consider another game of nim with heaps,, and.

Example Game 2

We can combine it with our [|first example] to get a [|combined game] with six heaps:,,,,, and :

Combined Game

To differentiate between the two games, for the [|first example game], we'll label its starting position, and color it blue:
For the [|second example game], we'll label the starting position and color it red:
To compute the starting position of the combined game, remember that a player can either make a move in the [|first] game, leaving the [|second] game untouched, or make a move in the second game, leaving the first game untouched. So the combined game's starting position is:
The explicit formula for adding positions is:, which means that addition is both commutative and associative.

Equivalence

Positions in impartial games fall into two outcome classes: either the next player wins, or the previous player wins. So, for example, is a -position, while is an -position.
Two positions and are equivalent if, no matter what position is added to them, they are always in the same outcome class.
Formally,
if and only if, is in the same outcome class as.
To use our running examples, notice that in both the first and second games above, we can show that on every turn, Alice has a move that forces Bob into a -position. Thus, both and are -positions.

First Lemma

As an intermediate step to proving the main theorem, we show that for every position and every -position, the equivalence holds. By the above definition of equivalence, this amounts to showing that and share an outcome class for all.
Suppose that is a -position. Then the previous player has a winning strategy for : respond to moves in according to their winning strategy for , and respond to moves in according to their winning strategy for . So must also be a -position.
On the other hand, if is an -position, then is also an -position, because the next player has a winning strategy: choose a -position from among the options, and we conclude from the previous paragraph that adding to that position is still a -position. Thus, in this case, must be a -position, just like.
As these are the only two cases, the lemma holds.

Second Lemma

As a further step, we show that if and only if is a -position.
In the forward direction, suppose that. Applying the definition of equivalence with, we find that is in the same outcome class as. But must be a -position: for every move made in one copy of, the previous player can respond with the same move in the other copy, and so always make the last move.
In the reverse direction, since is a -position by hypothesis, it follows from the first lemma,, that. Similarly, since is also a -position, it follows from the first lemma in the form that. By associativity and commutativity, the right-hand sides of these results are equal. Furthermore, is an equivalence relation because equality is an equivalence relation on outcome classes. Via the transitivity of, we can conclude that.

Proof

We prove that all positions are equivalent to a nimber by structural induction. The more specific result, that the given game's initial position must be equivalent to a nimber, shows that the game is itself equivalent to a nimber.
Consider a position. By the induction hypothesis, all of the options are equivalent to nimbers, say. So let. We will show that, where is the mex of the numbers, that is, the smallest non-negative integer not equal to some.
The first thing we need to note is that, by way of the second lemma. If is zero, the claim is trivially true. Otherwise, consider. If the next player makes a move to in, then the previous player can move to in, and conversely if the next player makes a move in. After this, the position is a -position by the lemma's forward implication. Therefore, is a -position, and, citing the lemma's reverse implication,.
Now let us show that is a -position, which, using the second lemma once again, means that. We do so by giving an explicit strategy for the previous player.
Suppose that and are empty. Then is the null set, clearly a -position.
Or consider the case that the next player moves in the component to the option where. Because was the minimum excluded number, the previous player can move in to. And, as shown before, any position plus itself is a -position.
Finally, suppose instead that the next player moves in the component to the option. If then the previous player moves in to ; otherwise, if, the previous player moves in to ; in either case the result is a position plus itself.
In summary, we have and. By transitivity, we conclude that, as desired.

Development

If is a position of an impartial game, the unique integer such that is called its Grundy value, or Grundy number, and the function which assigns this value to each such position is called the Sprague–Grundy function. R.L.Sprague and P.M.Grundy independently gave an explicit definition of this function, not based on any concept of equivalence to nim positions, and showed that it had the following properties:
It follows straightforwardly from these results that if a position has a Grundy value of, then has the same Grundy value as , and therefore belongs to the same outcome class, for any position. Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it follows directly from their results and is credited to them.
These results have subsequently been developed into the field of combinatorial game theory, notably by Richard Guy, Elwyn Berlekamp, John Horton Conway and others, where they are now encapsulated in the Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.