I have read about Sprague Grundy Theorem and understand the proof of its correctness. However, I am unable to see the motivation behind the definitions. How do Sprague and Grundy know that they should define the Grundy number in that manner? Why is it the case that xoring the Grundy numbers together work? I don't think they magically came up with this theorem, so I would like to get some intuition to better understand how the theorem is constructed.
Thank you very much!
The solution to Nim was known by 1901 (C. L. Bouton. "Nim, a game with a complete mathematical theory", Annals of Mathematics 3 (1901–02), 35–39), over 30 years before the Sprague-Grundy Theorem (1935, 1939). Once you have the idea that Nim might be the most general model for an impartial game, perhaps by reducing Nim variants to Nim, then which Nim heap corresponds to a game is pretty obvious: If an impartial game $G$ contains the option $\star n$ then $G+\star n$ is a first player win, so $G$ can't be $\star n$. By induction, adding the first excluded option makes the game a second player win, so that's what $G$ is.
I'll say a little more to motivate the solution to Nim, inspired by Mark Wildon's answer.
First, if you have two heaps of equal size, this is a second player win by mirroring.
Second, which sizes of heaps can't be expressed as arbitrary sums of smaller heaps? The "primes" in this sense are the powers of two.
Together, these motivate expressing $\star n$ as $\sum \star 2^{a_i}$, and prove that $\star m + \star n = \star x$ where the binary representation of $x$ is $\text{XOR}$ applied to the binary representations of $m$ and $n$.
You can make Zare's argument (above) a bit more precise. We wrote a pedagogical paper a few years ago on this topic, to understand it ourselves (and then never published it...). The basic idea is that if there is group of game values then they must involve base 2 and xor -- or more formally, products of Z^2.
Here's the link: http://www1.icsi.berkeley.edu/~ejf/pfiles/nimgroups.pdf
I don't know of a really intuitive explanation for the XOR rule, but maybe this short proof will be useful. It is sufficient to prove that if $0\le a_1 < \cdots < a_r$ and $n = \sum_{i=1}^r 2^{a_i}$ then
$$ \star n = \sum_{i=1}^r \star 2^{a_i}. $$
Assume inductively that this result is true for all $t < n$. By playing in $\star 2^{a_k}$ on the right-hand side, we get as options all nim piles of the form
$$\sum_{i \neq k} \star 2^{a_i} + \star t $$
where $0\le t < 2^{a_k}$. By induction the XOR rule holds for addition of $\star t$. So these options are exactly the nim pile of size $\star m$ where the binary expansion of $m$ is obtained from the binary expansion of $n$ by flipping the $1$ in position $a_k$ for some $k$, and also flipping any combination of less significant bits. Hence we can obtain $\star m$ if and only if $m < n$ and $\sum_{i=1}^r \star 2^{a_i}$ plays exactly like the nim pile $\star n$.
