I'm trying to understand the concept of equivalent games in the context of Sprague Grundy theory. Suppose we have an impartial game $G_1$ that is equivalent to another impartial game $G_2$, that is, $G_1 \approx G_2$, and also suppose that it is possible to move to some position $G_1'$ from $G_1$ in a single move. Then does there always exist a position $G_2'$ that can be reached from $G_2$ in a single move, such that $G_1' \approx G_2'$?
The concept of equivalent games in Sprague-Grundy theorem
combinatorial-game-theorygame theory
Related Solutions
It’s not hard to use Jyrki’s suggestion to make a table of Sprague-Grundy values of small single heaps:
$$\begin{array}{rcc} \textbf{heap size}:&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \textbf{S-G value}:&0&0&0&1&0&2&3&4&0&5&6&7&8&9&10&11&12 \end{array}$$
- For $n=6$ the possible splits are $\langle 5,1\rangle,\langle 4,2\rangle$, and $\langle 3,2,1\rangle$, with S-G values $2$, $0$, and $1$, respectively, so the S-G value of $6$ is $3$.
- For $n=7$ the possible splits are $\langle 6,1\rangle,\langle 5,2\rangle,\langle 4,3\rangle$, and $\langle 4,2,1\rangle$, with respective values $3$, $2$, $1$, and $0$, so the value of $7$ is $4$.
- For $n=8$: $\langle 7,1\rangle,\langle 6,2\rangle,\langle 5,3\rangle,\langle 5,2,1\rangle$, and $\langle 4,3,1\rangle$, with respective values $4$, $3$, $2\oplus 1=3$, $2$, and $1$, so the value of $8$ is $0$.
- For $n=9$; $\langle 8,1\rangle,\langle 7,2\rangle,\langle 6,3\rangle,\langle 5,4\rangle,\langle 6,2,1\rangle,\langle 5,3,1\rangle$, and $\langle 4,3,2\rangle$, with values $0$, $4$, $3\oplus1=2$, $2$, $3$, $2\oplus 1=3$, and $1$, so the value of $9$ is $5$.
- For $n=10$: $\langle 9,1\rangle,\langle 8,2\rangle,\langle 7,3\rangle,\langle 6,4\rangle,\langle 7,2,1\rangle,\langle 6,3,1\rangle,\langle 5,4,1\rangle,\langle 5,3,2\rangle$, and $\langle 4,3,2,1\rangle$, with respective values $5$, $0$, $4\oplus1=5$, $3$, $4$, $3\oplus1=2$, $2$, $2\oplus 1=3$, and $1$, so the value of $10$ is $6$.
- For $n=11$ the values of the reachable positions are $6,5,1,4,1,0,5,3,2,2,3$, so the value of $11$ is $7$.
- For $n=12$ the values of the reachable positions are $7,6,4,0,6,5,1,4,1,5,3,3,2,2$, so the value of $12$ is $8$.
- For $n=13$ the values of the reachable positions are $8,7,7,5,2,7,6,4,0,6,1,2,5,3$, so the value of $13$ is $9$.
- For $n=14$ the values of the reachable positions are $9,8,6$, $6,7,3$, $7,7,5$, $2,7,4$, $0,6,5$, $0,1$, $4,1,3$, so the value of $14$ is $10$.
- For $n=15$ the values of the reachable positions are $10,9,9$, $7,4,6$, $4,8,6$, $6,7,3$, $7,5,2$, $7,1,7$, $1,4,0$, $6,2,3$, so the value of $15$ is $11$.
- For $n=16$ the values of the reachable positions are $11,10,8$, $8,5,5$, $1,9,9$, $7,4,6$, $4,6,6$, $7,3,4$, $3,6,6$, $7,5,2$, $7,5,0,2$, so the value of $16$ is $12$.
I had hoped that the S-G value of $16$ would be $0$, suggesting a pattern of values increasing by $1$ but dipping to $0$ at each power of $2$. Since that failed, I have no reasonable guess at the actual pattern.
It’s probably worth investigating the possibility that for $n\ge 9$ the S-G value of a heap of $n$ is simply $n-4$; I do intend to give it some thought.
As pointed out in the comments, the Sprague-Grundy Theorem only applies to "non-loopy" impartial games that do not admit infinite runs. However, there is a generalization which can handle loopy games, discovered by Cedric Smith and independently by Aviezri Fraenkel. It is covered in detail in section IV.4 of the textbook Combinatorial Game Theory by Aaron N. Siegel.
I have a more elaborate summary in a Mathoverflow post, but basically, you try to build up finite "nimbers", temporarily assigning $\infty$ to anything you don't know yet. You can replace an $\infty$ with a mex $m$ when all of the options of value higher than $m$ (including $\infty$) can move to $m$. When you can't get rid of any more $\infty$s, the process stops and you just note which finite nimbers each $\infty$ can move to (so you can decide who wins in a sum).
In the game posted in the question, $D$ gets nimber $0$ because there are no options. $C$ gets nimber $1$ because its only option is $D=0$. Can $A$ and $B$ be changed from $\infty$? Well, $A$ would have to get the nimber $\mathrm{mex}\{1,\infty\}=0$, but $B$ doesn't have an option of $0$, so $A$ stays as an $\infty$. And similarly for $B$ by symmetry. Therefore, $A$ and $B$ don't get a finite value, but could be denoted as $\infty\{1\}$ for "an $\infty$ whose only finite nimber option is $1$".
Since $A$ is an $\infty$ and can't move to $0$ (which would be a winning move), it's a "drawn" position, rather than a win for either player. And since $A$ is $\infty\{1\}$, if we add $A$ to something with nimber $1$ (like $C$) then we get a game where the first player can win: simply move from $A$ to $C$, leaving the opponent with a sum of two nimber-$1$ games, which is a losing position by the usual Sprague-Grundy theory.
For a different example where there are no $\infty$s in the end, despite a loop, see my answer to a similar question.
Best Answer
No. Get $G_1$ be the Nim game with two piles of size $1$, and $G_2$ be the Nim game where you have already lost, i.e., where there are no piles.
$G_1$ and $G_2$ both have nim-value $0$, but there are moves from position $G_1$ while $G_2$ has no available moves.
$G_1$ and $G_2$ both having nim-value $0$ only means they can't move to another position with nim-value $0$; they could move to many other positions, possibly different ones from each other.
For a more involved example, let $G_1$ be the game $\{8,9\}$ and $G_2$ the game $\{2,3\}$; both have nim-value $1$, but $G_1$ can move to a position with nim-value $8$ while $G_2$ cannot.
You could define an equivalence of games as you describe, at least for games whose positions are guaranteed to go on for finite time (and which are bounded for each position, as opposed to something like Chomp on a $1\times\omega$ board). You can define "strong equivalence" by saying that two games are equivalent if they both have no moves available, or if the set of positions they can move to can be put in a bijection with each pair being strong-equivalent.
However, as the name suggests, this would be a very hard condition to satisfy, and wouldn't let you reduce impartial games very usefully in most cases. (It would also take longer to check.)