It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.
The Sprague–Grundy theorem and its proof encapsulate the main results of a theory discovered independently by R. P. Sprague (1936)[1] and P. M. Grundy (1939).
[2] For the purposes of the Sprague–Grundy theorem, a game is a two-player sequential game of perfect information satisfying the ending condition (all games come to an end: there are no infinite lines of play) and the normal play condition (a player who cannot move loses).
At any given point in the game, a player's position is the set of moves they are allowed to make.
, since the set of moves each player can make is empty.
In nim, there are one or more heaps of objects, and two players (we'll call them Alice and Bob), take turns choosing a heap and removing 1 or more objects from it.
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.
A move can be associated with the position it leaves the next player in.
For example, consider the following game of Nim played by Alice and Bob.
referenced in our example game are called nimbers.
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.
For the second example game, we'll label the starting position
Positions in impartial games fall into two outcome classes: either the next player (the one whose turn it is) wins (an
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
(Notice that in the combined game, Bob is the player with the
As an intermediate step to proving the main theorem, we show that for every position
options, and we conclude from the previous paragraph that adding
By associativity and commutativity, the right-hand sides of these results are equal.
We prove that all positions are equivalent to a nimber by structural induction.
By the induction hypothesis, all of the options are equivalent to nimbers, say
We do so by giving an explicit strategy for the previous player.
was the minimum excluded number, the previous player can move in
Finally, suppose instead that the next player moves in the component
is a position of an impartial game, the unique integer
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
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.
[3][4] 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.