Preliminaries
First, you may want to read a short introduction to the problem space such as this one.
Traditionally, the Nim game is introduced prior to deriving the Sprague-Grundy theorem. In this post, we will instead show how Nim naturally arises from a greedy algorithm to categorize games. Specifically, we will first motivate the usage of XOR, then the usage of MEX.
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 impartial games can be represented as DAGs (directed acyclic graphs).
The positions are labelled according to the following rules:
- All terminal states (i.e. states with no out-degree) are P-positions.
- If a state has an edge to any P-position, it is an N-position.
- Otherwise, it is a P-position.
Sums of games
We define the sum of two games as a new game in which the games and are played in parallel: on each playerβs turn, they can choose to move in exactly one of the two games, 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 over the space of impartial games, 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: position equivalence
iff for all positions , and belong to the same outcome class.
To assist with the following inductive proofs, we introduce the notion of the size of a position as the total number of reachable positions from after one more more moves. Importantly, this means that if position can move to position , .
We will also refer to the previous player and next player as Players P and N, respectively.
We can now prove our first theorem:
Theorem: P-positions
For any P-position , ( denotes the empty game, which is also a P-position).
Proof. By definition, we must show that for all , and have the same winner. We split this into two cases:
- is a P-position, so we want to show is also a P-position.
- If player N moves , player P must be able to make the move where is a P-position. By induction on , is also a P-position.
- Symmetric reasoning for if player N moves instead.
- Therefore, no matter how player N moves in , player P can always return it to a P-position.
- is an N-position, so we want to show that is also an N-position.
- If is an N-position, there must exists a move such that is a P-position. From the first case, is also a P-position, therefore in both games player N can move to a P-position, as desired.
Importantly, this means that all P-positions are still equivalent to one another.
Corollary
For all games , .
Proof. We just need to show is a P-position, which is true because player P can always just mirror the moves of player N.
Now that weβve now discovered the inverse of (specifically, ), note that our notions of equivalence and sum define a group:
- The operation is both associative and commutative.
- The identity element is .
- The inverse of an element is itself.
Corollary
iff is a P-position, i.e. .
Proof. By elementary group properties.
XOR?
The fundamental reason that XOR shows up is the fact that . In particular, consider a set of positions and the following two sums:
- ; we encode this as .
- ; we encode this as .
Then we have that .
Note that this XOR property holds for any choice of . However, weβd also like an additional condition:
Any non-empty sum of distinct elements of should not be equivalent to .
or, alternatively:
Every position should have a unique representation as a sum of distinct .
In linear algebra terms, we want to be an independent basis of all possible positions. If this holds, then we have the nice property that iff .
Therefore, it remains to solve the following question: how do we actually find such a basis?
MEX!
Let me first describe a simple algorithm to find a basis:
- Topologically sort all game states.
- 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:
Theorem
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. 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 . 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.