In
combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
, the Sprague–Grundy theorem states that every
impartial game In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference betw ...
under the
normal play convention
A normal play convention in a game is the method of determining the winner that is generally regarded as standard. For example:
*Preventing the other player from being able to move
*Being the first player to achieve a target
*Holding the highest va ...
is equivalent to a one-heap game of
nim, or to an infinite generalization of nim. It can therefore be represented as a
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
, the size of the heap in its equivalent game of nim, as an
ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the least n ...
in the infinite generalization, or alternatively as a
nimber
In mathematics, the nimbers, also called ''Grundy numbers'', are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with ''nimber addition'' and ' ...
, 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 Grundy value or nim-value of any impartial game is the unique nimber that the game is equivalent to. In the case of a game whose positions are indexed by the natural numbers (like nim itself, which is indexed by its heap sizes), the sequence of nimbers for successive positions of the game is called the nim-sequence of the game.
The Sprague–Grundy theorem and its proof encapsulate the main results of a theory discovered independently by
R. P. Sprague (1936)
and
P. M. Grundy (1939).
[ Reprinted, 1964, 27: 9–11.]
Definitions
For the purposes of the Sprague–Grundy theorem, a ''game'' is a two-player
sequential game
In game theory, a sequential game is a game where one player chooses their action before the others choose theirs. The other players must have information on the first player's choice so that the difference in time has no strategic effect. Sequen ...
of
perfect information
In economics, perfect information (sometimes referred to as "no hidden information") is a feature of perfect competition. With perfect information in a market, all consumers and producers have complete and instantaneous knowledge of all market pr ...
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. 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
(for Alice) and
(for Bob), we would denote their positions as
, since the set of moves each player can make is empty.
An ''
impartial game In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference betw ...
'' 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 (we'll call them Alice and Bob), 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
Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. 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
* At step 6 of the game (when all of the heaps are empty) the position is
, because Bob has no valid moves to make. We name this position
.
* At step 5, Alice had exactly one option: to remove one object from heap C, leaving Bob with no moves. Since her ''move'' leaves Bob in position
, her ''position'' is written
. We name this position
.
* At step 4, Bob had two options: remove one from B or remove one from C. Note, however, that it didn't really matter which heap Bob removed the object from: Either way, Alice would be left with exactly one object in exactly one pile. So, using our recursive definition, Bob really only has one move:
. Thus, Bob's position is
.
* At step 3, Alice had 3 options: remove two from C, remove one from C, or remove one from B. Removing two from C leaves Bob in position
. Removing one from C leaves Bob with two piles, each of size one, i.e., position
, as described in step 4. However, removing 1 from B would leave Bob with two objects in a single pile. ''His'' moves would then be
and
, so ''her'' move would result in the position
. We call this position
. Alice's position is then the set of all her moves:
.
* Following the same recursive logic, at step 2, Bob's position is
* Finally, at step 1, Alice's position is
Nimbers
The special names
,
, and
referenced in our example game are called ''
nimber
In mathematics, the nimbers, also called ''Grundy numbers'', are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with ''nimber addition'' and ' ...
s''. 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 ''nim''ber 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 (the one whose turn it is) wins (an
''- position''), or the previous player wins (a
''- position''). 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
First or 1st is the ordinal form of the number one (#1).
First or 1st may also refer to:
*World record, specifically the first instance of a particular achievement
Arts and media Music
* 1$T, American rapper, singer-songwriter, DJ, and rec ...
and
second
The second (symbol: s) is the unit of time in the International System of Units (SI), historically defined as of a day – this factor derived from the division of the day first into 24 hours, then to 60 minutes and finally to 60 seconds ...
games above, we can show that on every turn, Alice has a move that forces Bob into a
-position. Thus, both
and
are
-positions. (Notice that in the combined game, ''Bob'' is the player with the
-positions. In fact,
is a
-position, which as we will see in Lemma 2, means
.)
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
(which exists by virtue of
being a
-position), and respond to moves in
according to their winning strategy for
(which exists for the analogous reason). 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
(which is equal to
by
commutativity
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
of addition) 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
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
and commutativity, the right-hand sides of these results are equal. Furthermore,
is an
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each 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 Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural nu ...
. 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 (minimum exclusion) 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