I am really confused about something in the Sprague-Grundy theorem for combinatorial games. I define $G(n)$ to be the Sprague-Grundy number for a single game of size $n$.
Is this correct:
The Sprague-Grundy value of a more complex game (e.g. something with $k$ games at the same time, such as a game of $k$ piles) is equal to $G(a_1) \oplus G(a_2) \oplus ... \oplus G(a_k)$. No need to use the "mex" function here.
The Sprague-Grundy value of a single game is equal to the minimal excluded value (the "mex" function) of the set of Sprague-Grundy values of all the positions you can reach. So $G(a_k) = \text{mex}(\{G(b_1) , G(b_2) , ... , G(b_m)\})$. where the $b$'s are just other positions reachable from $a$.
Because I am also confused when we start talking about regular Nim, where the answer doesn't seem to depend on Sprague-Grundy at all; the answer is the xor of all the pile sizes.
So my questions are:
-Are my earlier 2 points correct?
-Why does it seem like some Nim games don't involve Sprague-Grundy at all and you can just take the straight xor of everything without involving things like mex()?
Both are correct.
Nim with $p$ piles is a complex game: each pile is a simple game, and at each move you choose one of the $p$ piles and make your move in that simple game. Thus, your first point applies. However, that leaves the problem of determining the Sprague-Grundy value of a single pile of $n$ stones, and it’s here that you apply your second point: this is calculated using the minimum excluded value. For $n=0$ the set of moves is empty, and $\operatorname{mex}(\varnothing)=0$, If $n=1$, the only possible move is to $0$, so the set of values of possible outcomes is $\{0\}$, and clearly $\operatorname{mex}(\{0\})=1$. It’s straightforward in this way to show by induction that the Sprague-Grundy value of a pile of $n$ stones is
$$\operatorname{mex}(\{0,\ldots,n-1\})=n\;.$$
Thus, calculating the Sprague-Grundy value of a single pile turns out to be trivial. These values are in fact the basis of Sprague-Grundy theory.