Before we begin, you should probably familiarize yourself with a traditional explanation of the Sprague-Grundy theorem first, such as this one.
Note
Game states will henceforth be referred to as positions. Note that any position can be thought of as a game itself: just take the subgraph of the overall DAG that is reachable from the current position.
Theoretically, to solve any impartial game, we need only to determine a single bit of information about every possible position: whether the next player (about to make a move) wins, or loses. If the next player wins, the state is called an N-position; otherwise, if the previous player wins, the state is a P-position. Together, N-positions and P-positions comprise the two possible outcome classes of any impartial game.
An example of a simple game, with positions labeled N or P. Recall that all games can be represented as DAGs (directed acyclic graphs).
However, letβs say we want equivalence classes that are a bit more fine-grained. Why? Well, consider the operation of combining two positions and (henceforth denoted as ) in parallel, which means that these two positions will be played side-by-side: on each playerβs turn, they can choose to move on exactly one of the positions, and leave the other unchanged (a classic example of this would be a two-pile Nim game).
Note
Considering the positions as DAGs, this operation corresponds precisely to a Cartesian product:
A simple Cartesian product, illustrated. Each edge corresponds to a move on exactly one of the two parallel positions.
Note that the operation as defined here is both commutative and associative. It is also closed, since the Cartesian product of two DAGs is still a DAG.
Importantly, under our current definition of equivalence by outcome classes (i.e. all N-positions are equivalent, as are all P-positions), equivalent positions might not produce equivalent results when combined with other positions. Specifically, two N-positions combined could produce either an N-position or a P-position.
Two N-positions combined donβt always yield equivalent results.
This motivates a new definition of equivalence:
Definition
iff for all positions , and belong to the same outcome class.
Note that this also means that if , as well, since
Here, we use the fact that is associative.
And the equivalence classes of positions under this definition are precisely what the Sprague-Grundy theorem helps us find!
Note
While the Sprague-Grundy theorem is often thought of as a very general result, itβs only really useful when games are being combined in parallel. Otherwise, the Grundy number has no real meaning.
Letβs consider the identity equivalence class, , defined such that for every position in this class, for all games . A trivial example of such a game is the empty position , but there are actually more. In fact:
Lemma 1
is exactly the set of all P-positions.
Proof: Letβs pick some P-position . We wish to prove that for all positions , . Note that this is actually equivalent to proving the simpler statement that for all positions , and belong to the same outcome class.
If is an N-position, the first player can win like so:
- Always play in according to their original strategy for .
- If the second player plays in , the first player will always have a response since is a P-position.
A similar argument holds for the case when is a P-position.
On the contrary, no N-position can be in : a simple counter-case is .
Another useful lemma:
Lemma 2
For all positions , .
Proof: Player 2 can always simply mirror Player 1βs move. Thus, is a P-position and therefore is in .
β¦Wait a minute. ? This operation is starting to look suspiciously like XOR! In fact, Lemma 2 is precisely the reason why XOR appears in the Sprague-Grundy theorem: not because of the nim-sum, but because of this much more fundamental βmirrorβ property.
By the way, this property also gives us an easier way to check equivalence:
Lemma 3
iff .
Proof: For all , . Here, weβve used the fact that is associative.
Now, letβs define a basis of games such that every game is equivalent to the sum of exactly one subset of . Essentially, the games in must all be independent, as well as span all possible games under the operation.
Then, using this basis, every equivalence class has a unique binary representation , where the th bit of denotes whether is a member of the equivalent subset or not. Importantly, combining two games in parallel then corresponds to simply XOR-ing these binary representations!
So, are these binary representations the Grundy numbers, then?
Well, not quite. See, we donβt just have one choice of basis. Consider the game of Nim, for instance. The classic basis is where denotes a single pile of size . In this basis, we would represent the game as . However, we could also use something like , in which case would be represented as instead. Yet, no matter what basis we choose, remember that always equals due to Lemma 2.
What basis should we use then? And how do we even ensure our basis elements are independent?
Enter: mex! Just like XOR, the use of the mex function in the Sprague-Grundy theorem is typically justified by converting all games into Nim. However, there again exists a more fundamental reason for its use: it encapsulates a clever greedy algorithm that helps us quickly find a valid basis.
Whaa? OK, let me describe this greedy algorithm to you first, without using mex at all.
- Topologically sort all game states (guaranteed to be possible since game is a DAG).
- Initialize our basis as an empty list, (because order matters!).
- In reverse topological order, check if our current game is independent of . If yes, append to the end of .
And thatβs it!
Wait, what? Thatβs it? How is this even remotely related to mex? And how do we check whether a game is independent of ? The key idea is to show that because of this specific greedy approach, the th basis element has the property that it can transition to an equivalent state of every subset of the first basis elements. That is, for every , can transition to a state such that . This will enable us to implement a much faster check for independence.
In fact, together with the properties of XOR, this claim generalizes to the following:
Lemma 4
For every state and every , can transition to some state such that .
Do you see where mex could come in now?
Proof: We induct. Letβs say this claim is true for every state weβve encountered so far in our reverse topological order: the base case is rather simple. Now, let our current state be , and the set of possible next states as . Let be the mex of over all . We wish to show that .
To do this, consider some game in equivalence class and spanned by our current basis . If no such game exists, is independent of and thus will be added as a new element to the basis. Note that this also means we can transition to every game currently spanned by , so our inductive hypothesis still holds.
Otherwise, we then need to prove is that , or that . We can show this by splitting into two cases:
- The first player moves either or to a state with . The second player can then match this value by moving on the other game. Both states will have value and will thus form a P-position.
- The first player moves either or to a state with . The second player can then move this state back to one with value . Both games will now have value and will thus form a P-position.
Since the second player can always force the first player to begin their next turn on a P-position, it follows that must be a P-position itself. Therefore, , as desired.
OK, that was a lot. But the primary takeaway is that the entire reason mex is used is because of the (surprisingly elegant) greedy strategy we used in order to find a valid basis. In fact, (donβt quote me on this) this may be one of the only efficient strategies to compute a valid basis because of the issue of checking independence. If was just some arbitrary basis, this could have taken forever to check, and maybe even have been impossible. Thankfully, due to the nice structure our greedy algorithm imposes on , we instead end up with a very quick and elegant way of evaluating independence.
The best part? We derived all these beautiful results without referencing the game of Nim at all! The XOR relation arose naturally from the βmirrorβ nature of combining identical impartial games, and mex showed up as a direct result of the simple greedy strategy we defined to find a valid basis. This, I believe, is truly the best way to understand the fundamental nature of the Sprague-Grundy theorem.