There are already many wonderful resources online for learning the basics to combinatorial game theory, but the intention I have for this guide in particular is to try to make them more intuitive. Why does XOR work for Nim? Why does mex produce the Grundy numbers? When it was taught to me, it was more or less just as 'magic' to memorize, but now I think I have a decent understanding of why they are true, so now that I have a grasp of the intuition behind it, I decided I should record my thoughts into a blog.
Nim games
Suppose we are playing a Nim game. As we know, Nim games usually follow this sort of template:
There are $$$n$$$ piles of stones, and each pile contains $$$p_1, p_2, p_3, \cdots p_n$$$ stones, where each of the $$$p_i$$$ is some nonnegative integer.
There are two players who take turns removing stones. The current turn player may remove as many stones as they wish, so long as all the stones come from the same pile. More formally, they choose a pile $$$i$$$ and a number of stones to remove $$$0 < s \leq p_i$$$, then replace $$$p_i$$$ with $$$p_i-s$$$. You cannot pass your turn doing nothing. Then, it is the other player's turn to remove stones, and so on.
The game ends when there are no stones left on the board. The winner is the one who took the last stone; alternative, the loser is the first one who cannot take a stone on their turn.
The question usually goes something like this: Given an initial board state $$$p_1, p_2, p_3, \cdots p_n$$$, is there a winning strategy the first player can take so that they always win, or is it always possible for the second player to win?
We could attack this problem using DP, however, a lot of Nim-type problem will have bounds such as $$$N$$$ up to $$$2\cdot10^5$$$ and $$$p_i$$$ up to $$$10^9$$$ or even $$$10^{18}$$$. That's obviously impossible to DP.
There exists a fairly standard $$$O(N)$$$ formula to solving the Nim game, and here is my attempt to naturally and intuitively derive for ourselves what this magic formula is.
You can only take stones from one pile at a time, so it seems like a good idea to find some property for each pile of the game, then find some way to compose that information together to describe the board state as a whole. It's rather mathy, but as an analogy, think about multiplicative functions---to evaluate a multiplicative function at $$$n$$$, we decompose $$$n$$$ into its prime powers, more easily evaluate the function with each prime power, then find some way to compose the answers for each $$$p^k$$$ together to get the answer for $$$n$$$.
So, what we will do is:
For each game state $$$g$$$, let us assign to it some integer "Nim-value" $$$G$$$ which tells us whether this is a winning state or a losing state.
Given two game states $$$a$$$ and $$$b$$$, let $$$a+b$$$ be the game state that is simply the piles of $$$a$$$ together with the piles of $$$b$$$. If their Nim-values are $$$A$$$ and $$$B$$$ respectively, then define $$$A\oplus B$$$ to be the Nim value of the game state $$$a+b$$$. We are assuming (and hoping) that there does in fact exist some operator that allows us to compose different games together easily.
Now, let's tackle the simplest possible game---one that consists of a single pile with $$$p$$$ stones in it.
Intuitively, since the only information that distinguishes piles from one another is $$$p$$$, let's say that the Nim-value of a game that consists of only a single pile is $$$p$$$.
We see that a single pile is a winning state if $$$p>0$$$, and is a losing state if $$$p=0$$$. That's something we'd like to see reflected in the Nim-values as well---a Nim-value $$$G$$$ corresponds to a winning game state when $$$G>0$$$, and corresponds to a losing game state when $$$G=0$$$.
Next step, let's find a way to compose Nim-values together with this operator $$$A \oplus B$$$. We should notice the following properties about it though:
$$$(A \oplus B) \oplus C = A\oplus(B \oplus C)$$$, and $$$A \oplus B = B \oplus A$$$. That is to say, $$$\oplus$$$ is associative and commutative. Since we're just combining the piles together, order doesn't really matter, so this should be apparent.
$$$A \oplus 0 = A$$$. That is to say, the identity for this operator is 0. We obviously want this to be true since if you place an empty pile next to an existing game, you should still effectively have the same game.
$$$A \oplus A = 0$$$. That is to say, the inverse of each game state is itself. Think about why this is true---suppose we have two piles that each have $$$p$$$ stones in them. The second player always has a winning strategy here, which is to just mirror the first player's move! For some generic game state $$$A$$$, note that the game state $$$A\oplus A$$$ guarantees a respective 'mirror image' for each pile; if the first player makes a move on some pile, the second player can always take the same number of stones from the 'mirror image' of that pile. Thus, the first player will always be the one to run out of moves first, therefore this is a losing state, and therefore $$$A \oplus A = 0$$$.
You'll notice that all of these properties define a group over the nonnegative integers! In fact, take a look at that last property in particular, that $$$A \oplus A = 0$$$. The inverse of every element is itself, i.e. every non-zero element in the group has order 1. This is actually a huge hint because it turns out the only group that has this property is the set $$${0,1}$$$ with the operation of addition modulo 2, or some ordered $$$n$$$-tuple of $$${0,1}$$$ with the operation of addition modulo 2 done between each corresponding component; aka, the logical XOR and the bitwise XOR.
Bingo! It seems our operator $$$A\oplus B$$$ is just the bitwise XOR of the two Nim-values. In fact, since XOR is just addition modulo 2, in literature the Nim-values are usually called the Nim-sums of the game state. However most of what I gave consists of heuristics and intuitions---now that we have this operator as a candidate, let's try to formally prove that our magic formula works.
**Given a game of Nim whose current game state consists of $$$n$$$ piles with $$$p_1, p_2, p_3, \cdots, p_n$$$, then the current game state is a winning state if the Nim-sum $$$p_1 \oplus p_2 \oplus p_3 \oplus \cdots \oplus p_n$$$ is non-zero, and a losing state if the Nim-sum is zero, where $$$\oplus$$$ is the bitwise XOR operation.
The empty board is a losing state with Nim-sum 0. This follows from our observations earlier.
If the current Nim-sum is 0, then any move will make it non-zero. Recall that a move replaces $$$p_i$$$ with $$$p_i-s$$$. So, keeping in mind that the XOR-inverse of each integer is itself, that means the new Nim-sum after a move is made becomes $$$p_1 \oplus p_2 \oplus p_3 \oplus \cdots \oplus p_n \oplus p_i \oplus (p_i-s)$$$; we remove $$$p_i$$$ from the Nim-sum, then add in $$$p_i-s$$$. But, if the current Nim-sum was 0, then this is just $$$p_i \oplus (p_i-s)$$$, and this is only equal to 0 when $$$p_i=p_i-s$$$, but the rules state you have to always take at least one stone on your turn, so $$$s \neq 0$$$.
If the current Nim-sum is non-zero, then there always exists a move to make it equal to 0. Suppose the current Nim-sum is $$$N>0$$$. We need to choose $$$p_i$$$ and $$$s$$$ such $$$p_i \oplus (p_i-s)=N$$$, subject to the constraint that $$$0 < s \leq p_i$$$. Consider the fact that $$$N$$$, since it is nonzero, must have a greatest significant bit, the $$$g$$$th bit. Furthermore, at least one of the piles $$$p_i$$$ will have the $$$g$$$th bit as a 1 as well; if all the piles had a 0 there, then it couldn't have been the greatest significant bit of their XORsum after all. So, we choose one such pile as our $$$p_i$$$, and we construct our $$$p_i-s$$$ as the following:
All bits greater than the $$$g$$$th bit we keep the same as $$$p_i$$$.
The $g$th bit is set to 0.
All bits less than the $$$g$$$th bit we make match those of $$$N \oplus p_i$$$.
Notice that this construction is always less than $$$p_i$$$, since we know their first difference is at the $$$g$$$th bit, therefore this is a valid choice of $$$p_i-s$$$, from which we can easily recover what the $$$s$$$ should be. We can see that the new Nim-sum is 0 because
All bits in $$$N$$$ greater than the $$$g$$$th bit were already 0 (since the $$$g$$$th bit was defined to be the greatest significant bit). Then, we know that all bits in $$$p_i \oplus (p_i-s)$$$ greater than the $g$th bit are also 0, since that was how we constructed it.
The $$$g$$$th bit in $$$N$$$ 1, by definition as the greatest significant bit, and the $$$g$$$th bit in $$$p_i \oplus (p_i-s)$$$ is also 1, since it is 1 in $$$p_i$$$ and 0 in $$$p_i-s$$$.
All bits in $$$p_i \oplus (p_i-s)$$$ less than the $$$g$$$th bit, are guaranteed to match that of $$$N$$$, since $$$p_i \oplus (p_i-s) = p_i \oplus (p_i \oplus N) = N$$$ in this range.
The best way to convince yourself and see that this does in fact set the new Nim-sum to 0 is to write it out yourself and try it with some concrete values.
Now, with these tools in hand, we can see that:
If the current turn player has a zero state, they have no choice but to 'disturb' it into a nonzero state.
The next player then, given a nonzero state, always is able to 'restore' it back into a zero state.
Thus, if the players know what they are doing, the first player is always stuck with a game state whose Nim-sum is 0; since this remains invariant and there are only a finite number of moves, eventually when the game ends with the empty game whose Nim-sum is 0, we know the current turn player, and loser, is the first player.
Similarly, if the current turn player has a nonzero state, they can restore it to a zero state and pass the board over to the second player, who by our logic, must be the loser.
This proves our theorem.
