In my current understanding, the idea of Sprague-Grundy is basically:
- There is Nim space $N$, and regular game space $G$ (which is a DAG where vertices are states and edges are possible actions)
- By using DFS over $G$, we can always yield answer. But this yield complexity proportional with state space size.
- Sprague-Grundy says if we use the homomorphism $f:N\rightarrow G$ that views every vertices in terms of their "equivalent Nim pile size" (equivalent loosely in terms of having same win/lose outcome as original game), the calculation can be greatly compressed if we can split game state into several independent subgames. Sometimes repetitions can be even found from observing such "Grundy number"s.
And the suggested homomorphism is $f(e)=MEX(f(G[e]))=MEX(XORSUM(Comp(G[e]))$ for nonleaf elements.
I think at this step I have trouble pinpointing exactly what invariance is the Grundy value trying to keep. Is it only making sure that for every state $X$, the outcome of it and outcome of its respective Nim game is the same? In that case, why can't I just map every winning game to 1 and losing game to 0?
Also I have trouble seeing why $MEX$ is homomorphism. How do I prove inductively that the possible actions of two representations are exactly the same?
Best Answer
Given an impartial game, $G$, let $n(G)$ be the Nim-heap equivalent to $G$. You mentioned that $n(G)$ has the same outcome as $G$. Another very important property of $n$ is that it satisfies $$ n(G+H)=n(G)+n(H)\tag{$*$} $$ On the left-hand side of $(*)$, the addition in $G+H$ refers to the disjunctive sum of games, meaning there is a copy of $G$ and a copy of $H$, and players can move on exactly one of them. Property $(*)$ is exactly the reason $n$ saves on computation time; as long as you can split $G$ into $G_1+G_2+\dots+G_m$, then you can reduce computing $n(G)$ to computing $n(G_1),\dots,n(G_m)$, which are much smaller games.
You were asking, why not define $\tilde n(G)=(\text{heap of size zero})$ when $G$ is losing and $\tilde n(G)=(\text{heap of size one})$ when $n$ is winning, and use $\tilde n$ as the Sprague-Grundy function? The reason is that $\tilde n(G+H)\neq \tilde n(G)+\tilde n(H)$ in general, so you would not have the useful property $(*)$.
Your second question is understanding exactly why the Sprague-Grundy theorem works, i.e. why we can get an equivalent game by replacing $G$ with Nim-heaps. I cannot help you there; the only way to understand this is to fully comprehend the proof of the Sprague-Grundy theorem. There are many proofs available on the internet and in print, written by people much more knowledgeable than me. If there is a particular place in a proof you found confusing, you could specifically ask about that, but asking for us to explain the entire thing is too much.