# 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

## 1 Answer

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.