Hey,
I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less resources available on net which mentions GSG Theorem. Plus it would be really helpful if anyone can provide me any link containing code (preferably in python) to find Sprague-Grundy Number of a position.
Thank you
The Generalized Sprague-Grundy Theory is used to analyze finite loopy impartial games under normal play, and was first developed by Cedric Smith in the 60s. In this context, a game is a finite directed graph with a vertex to start from (a pointed digraph), and plays just follow the edges. An "option" of a game in this context is just the vertex (on the same graph) that can be reached by following exactly one edge. A player who cannot move on their turn loses, and if that never happens, the game is "drawn".
It turns out that every game is either one in which the next player to move has a winning strategy (an $\mathcal N$-position), the player who is not next to move does (a $\mathcal P$-position), or under best play the game is drawn (a $\mathcal D$-position).
The "loopy nim value" of a game $G$, denoted $\mathcal G(G)$ can be built up iteratively: After each stage, it's the minimal excludant $m$ of the values of the options (treated as $\infty$ when unknown), provided that if any of those options have a value $>m$, they themselves have an option with value exactly $m$ (the problematic options "reverse out"), or $\infty$ if that condition doesn't hold. If after finitely many stages, the value of a game is found to be some natural number $m$, then $\mathcal G(G)=m$. If that never happens, then the loopy nim value is $\mathcal G(G)=\infty(\mathcal A)$, where $\mathcal A$ is the set of natural number values of options of $G$.
The loopy nim value tells you what type of position you have: $\mathcal P$-positions have $\mathcal G(G)=0$, $\mathcal N$-positions have $0\ne\mathcal G(G)\in\mathbb N$ or $\mathcal G(G)=\infty(\mathcal A),0\in\mathcal A$. $\mathcal D$-positions are all the rest ($\mathcal G(G)=\infty(\mathcal A),0\notin\mathcal A$). More importantly, they tell you exactly how games interact when played together: Given two games $G,H$, define their sum $G+H$ to be the cartesian product of the games. This is analogous to putting the games side by side and moving in one of them at a time. Suppose $\mathcal G(G)=x$ and $\mathcal G(H)=y$. Then, using $\oplus$ to denote bitwise xor, we have $$\mathcal{G}\left(G+H\right)=\begin{cases} x\oplus y & \text{ if }x,y\in\mathbb{N}\\ \infty\left(\mathcal{A}\oplus y\right) & \text{ if }x=\infty\left(\mathcal{A}\right)\text{ and }y\in\mathbb{N}\\ \infty\left(\emptyset\right) & \text{ if }x,y\notin\mathbb{N} \end{cases}$$
If we say that two games are equivalent if they affect the outcomes (under perfect play) of sums in identical ways, then a corollary of the above is that the loopy nim values exactly characterize the equivalence classes. This fact could be called "the generalized Sprague-Grundy Theorem".
The above is essentially a paraphrasing of some of section IV.4 in Siegel's Combinatorial Game Theory. The beginning of Chapter 12 of Winning Ways has a less formal treatment with many more example games.
As dspyz mentioned, if you know the nim values of all of the options, then writing a program to calculate nim values for traditional nonloopy games is very straightforward. If you know the nim values for only some options, and/or want to enter the whole game graph cgsuite can find the nim values, if you know the conventions for entering these graphs. For example, entering {0,{0|0}|0,{0|0}} where both players can either move to a position of nim value 0 or a position where either player can move to a position of nim value 0, produces *2, denoting a nim value of 2. {0,{0,{0|0}|0,{0|0}}|0,{0,{0|0}|0,{0|0}}} produces *, meaning the nim value is 1, etc.
I don't know of an existing program to calculate the loopy nim values of games. However, CGsuite 0.7 can usually test such games for equivalence. For example, the pointed digraph for the 4-almond version of fair shares and varied pairs (probably first introduced in Winning Ways) can be entered as g:=a:{0,b:{c:{d:{a,0|a,0},0|d:{a,0|a,0},0}|c:{d:{a,0|a,0},0|d:{a,0|a,0},0}}|0,b:{c:{d:{a,0|a,0},0|d:{a,0|a,0},0}|c:{d:{a,0|a,0},0|d:{a,0|a,0},0}}}. This produces a:{0,{0,{0,a|0,a}|0,{0,a|0,a}||0,{0,a|0,a}|0,{0,a|0,a}}|0,{0,{0,a|0,a}|0,{0,a|0,a}||0,{0,a|0,a}|0,{0,a|0,a}}} immediately, and then entering g=={0|0} returns true, showing that the game has loopy nim value 1.
I think by generalized Sprague Grundy Theorem, you mean including bogus nim heaps. The only difference between a bogus nim-heap and a regular nim-heap is that players may add stones back to a bogus nim heap. As Winning Ways explains in Ch. 3 in the section "Bogus Nim-Heaps and the Mex Rule", a bogus nim heap is no different from a normal nim heap because any such adding move is reversible.
Here's a simple one-liner python method for finding the Sprague-Grundy number of a nim position:
from operator import xor
def sgnumber(piles):
return reduce(xor,piles);
Ex.
>>> sgnumber([7,5,3])
1
