# Calculating Sprague–Grundy numbers for impartial game with a loop

Suppose we have a two-player game with states $$\{A,B,C,D\}$$ and allowable moves: $$A \to B, B \to A$$ $$A \to C, B \to C$$ $$C \to D$$ Since there are no moves starting from $$D$$, if a player is in state $$D$$ the player loses. This seems to satisfy the definition for impartial game, so by applying Sprage Grundy naively we would expect each state of the game to be equivalent to a nimber.

However, suppose we start in state $$A$$ of the game. The first player cannot go to state $$C$$, as this would cause the second player to play $$C \to D$$, ending the game. So the first player plays $$A \to B$$. Similarly, the second player must play $$B \to A$$. So the game never ends.

How are Nimbers assigned in this particular case? I have also read here that for a game where the states and transitions form a poset we can define the nimbers inductively using 'mex', but this isn't applicable here because $$A \to B$$ and $$B \to A$$ means the game isn't a poset?

• From en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem: "For the purposes of the Sprague–Grundy theorem, a game is a two-player sequential game of perfect information satisfying the ending condition (all games come to an end: there are no infinite lines of play)" – automaticallyGenerated Apr 20 at 22:26
• @automaticallyGenerated ah I missed that - thanks. Does this mean though that Sprague-Grundy only applies to poset games? Is it supposed to be surprising that we can find equivalent nim games for poset games? – Joshua Lin Apr 20 at 22:36
• I don't think it only applies to poset games, but it only applies to games that end (poset games are just a subset of games that end). – automaticallyGenerated Apr 20 at 22:39
• @JoshuaLin Take care when speaking of "poset games". The phrase "poset game" has a strict definition that's much more narrow than "a game whose graph of positions and allowable moves (in the style of your example) is the graph of a poset". – Mark S. Apr 21 at 16:22

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.