Editing Sprague–Grundy theorem (section)

==Definitions==
For the purposes of the Sprague&ndash;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.  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 <math>A</math> (for Alice) and <math>B</math> (for Bob), we would denote their positions as <math>(A, B) = (\{\}, \{\})</math>, 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 (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]] 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 <math>\{\}</math>, 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.

=== {{anchor|firstExample}}Example Nim Game ===
{{Pre|
 Sizes of heaps  Moves
 A B C
 &nbsp;
 1 2 2           Alice takes 1 from A
 0 2 2           Bob   takes 1 from B 
 0 1 2           Alice takes 1 from C 
 0 1 1           Bob   takes 1 from B 
 0 0 1           Alice takes 1 from C
 0 0 0           Bob   has no moves, so Alice wins
}}

* At step 6 of the game (when all of the heaps are empty) the position is <math>\{\}</math>, because Bob has no valid moves to make.  We name this position <math>*0</math>. 
* 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 <math>*0</math>, her ''position'' is written <math>\{ *0 \}</math>.  We name this position <math>*1</math>.
* 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: <math>*1</math>.   Thus, Bob's position is <math>\{*1\}</math>.
* 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 <math>*1</math>.  Removing one from C leaves Bob with two piles, each of size one, i.e., position <math>\{*1\}</math>, 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 <math>*0</math> and  <math>*1</math>, so ''her'' move would result in the position <math>\{*0, *1\}</math>.  We call this position <math>*2</math>.  Alice's position is then the set of all her moves: <math>\big\{*1, \{*1\}, *2\big\}</math>.
* Following the same recursive logic, at step 2, Bob's position is <math display="block">\big\{ \{*1, \{*1\}, *2\}, *2\big\}.</math>
* Finally, at step 1, Alice's position is <math display="block">\Big\{
    \big\{*1, \{*1\}, *2\big\},
    \big\{*2, \{*1, \{*1\},*2\} \big\},
    \big\{\{*1\}, \{\{*1\}\}, \{*1, \{*1\}, *2\}\big\}
\Big\}.</math>

===Nimbers===
The special names <math>*0</math>, <math>*1</math>, and <math>*2</math> referenced in our example game are called '''''[[nimber]]s'''''.  In general, the nimber <math>*n</math> corresponds to the position in a game of nim where there are exactly <math>n</math> objects in exactly one heap.  
Formally, nimbers are defined inductively as follows:  <math>*0</math> is <math>\{\}</math>, <math>*1 = \{*0\}</math>, <math>*2 = \{*0, *1\}</math> and  for all <math>n \geq 0</math>, <math>*(n+1) = *n \cup \{*n\}</math>.

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&ndash;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 <math>A'</math>, <math>B'</math>, and <math>C'</math>.

===={{anchor|secondExample}}Example Game 2====
{{Pre|
Sizes of heaps    Moves
&nbsp;
A' B' C'
1  1  1           Alice takes 1 from A'
0  1  1           Bob takes one from B'
0  0  1           Alice takes one from C'
0  0  0           Bob has no moves, so Alice wins.
}}

We can combine it with our [[#firstExample|first example]] to get a combined game with six heaps: <math>A</math>, <math>B</math>, <math>C</math>, <math>A'</math>, <math>B'</math>, and <math>C'</math>:

===={{anchor|thirdExample}}Combined Game====
{{Pre|
 Sizes of heaps     Moves
 A  B  C  A' B' C'  
 &nbsp;
 1  2  2  1  1  1   Alice takes 1 from A
 0  2  2  1  1  1   Bob takes 1 from A'
 0  2  2  0  1  1   Alice takes 1 from B'
 0  2  2  0  0  1   Bob takes 1 from C'
 0  2  2  0  0  0   Alice takes 2 from B
 0  0  2  0  0  0   Bob takes 2 from C
 0  0  0  0  0  0   Alice has no moves, so Bob wins.
}}

To differentiate between the two games, for the [[#firstExample|first example game]], we'll label its starting position <math>\color{blue}S</math>, and color it blue:
<math display="block">\color{blue}S = \Big\{
    \big\{*1, \{*1\}, *2\big\},
    \big\{*2, \{*1, \{*1\},*2\} \big\},
    \big\{\{*1\}, \{\{*1\}\}, \{*1, \{*1\}, *2\}\big\}
\Big\}</math>

For the [[#secondExample|second example game]], we'll label the starting position <math>\color{red}S'</math> and color it red:
<math display="block">
\color{red}S' = \Big\{\{*1\}\Big\}.
</math>

To compute the starting position of the [[#thirdExample|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:
<math display="block">
\color{blue}S \color{black} + \color{red}S' \color{black}= 
\Big\{
    \color{blue}S\color{black} + \color{red} \{*1\} \color{black}
\Big\} \cup \Big\{
     \color{red}S'\color{black} + \color{blue}\{*1, \{*1\}, *2\} \color{black}, 
     \color{red}S'\color{black} + \color{blue} \{*2, \{*1, \{*1\},*2\} \} \color{black},
     \color{red}S'\color{black} + \color{blue} \{\{*1\}, \{\{*1\}\}, \{*1, \{*1\}, *2\}\} \color{black}
\Big\}
</math>

The explicit formula for adding positions is: <math>S+S'=\{S+s'\mid s'\in S'\}\cup\{s+S'\mid s\in S\}</math>, 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 <math>\boldsymbol{\mathcal{N}}</math>'''''- position'''''), or the previous player wins (a <math>\boldsymbol{\mathcal{P}}</math>'''''- position''''').  So, for example, <math>*0</math> is a <math>\mathcal{P}</math>-position, while <math>*1</math> is an <math>\mathcal{N}</math>-position.

Two positions <math>G</math> and <math>G'</math> are '''''equivalent''''' if, no matter what position <math>H</math> is added to them, they are always in the same outcome class.  
Formally,
<math>G \approx G' </math> if and only if <math>\forall H </math>, <math>G + H</math> is in the same outcome class as <math>G' + H</math>.

To use our running examples, notice that in both the [[#firstExample|first]] and [[#secondExample|second]] games above, we can show that on every turn, Alice has a move that forces Bob into a <math>\mathcal{P}</math>-position. Thus, both <math>\color{blue}S</math> and  <math>\color{red}S'</math> are <math>\mathcal{N}</math>-positions.  (Notice that in the combined game, ''Bob'' is the player with the <math>\mathcal{N}</math>-positions. In fact, <math>\color{blue}S \color{black} + \color{red}S' </math> is a <math>\mathcal{P}</math>-position, which as we will see in Lemma 2, means <math> \color{blue} S \color{black} \approx \color{red} S'</math>.)