View source for Sprague-Grundy function

<!--This article has been texified automatically. Since there was no Nroff source code for this article, 
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
was used.
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.

Out of 155 formulas, 155 were replaced by TEX code.-->

{{TEX|semi-auto}}{{TEX|done}}
''Grundy–Sprague function, Grundy function''

The function $g : V \rightarrow \mathbf{Z} ^ { 0 }$ from the vertex set $V$ of a digraph $G = ( V , E )$ into the non-negative integers ${\bf Z} ^ { 0 }$ defined inductively by: $g = \operatorname { mex } g ( F ( u ) )$, where for any subset $S \subset \mathbf{Z} ^ { 0 }$, $S \neq \mathbf{Z} ^ { 0 }$, $\operatorname {mex} S= \operatorname { min } \overline{S} =$ least non-negative integer not in $S$, $F ( u ) = \{ v \in V : ( u , v ) \in E \}$ is the set of (directed) followers of $u$ and $g ( F ( u ) ) = \{ g ( v ) : v \in F ( u ) \}$. Informally, $g ( u ) =$ least non-negative integer not among the values $g ( F ( u ) )$. Note that $g ( u ) = 0$ if $u$ is a leaf of $G$, i.e., if $F ( u ) = \emptyset$. In the earlier literature the function was referred to as the Grundy function, [[#References|[a7]]]. Only later the more obscure but earlier reference [[#References|[a10]]] became known, whence the name changed to Sprague–Grundy function, or $g$-function.

A digraph is locally walk-bounded if for every vertex $u_i$ there is a bound $b _ { i } \in \mathbf{Z} ^ { 0 }$ such that the length of every (directed) walk emanating from $u_i$ does not exceed $b _ { i }$. Every locally walk-bounded digraph has a unique $g$-function. Moreover, $g ( u _ { i } ) \leq b _ { i }$. In particular, every finite acyclic digraph has a unique $g$-function.

Many two-player impartial games can be described by means of their game graph (see [[Two-person zero-sum game|Two-person zero-sum game]]), which is a digraph $G = ( V , E )$ whose vertices are all the game positions, and $( u , v ) \in E$ if and only if there is a legal move from position $u$ to position $v$. The $g$-function determines the strategy of such games if the game does not have cycles, i.e., no game position can be repeated. For a normal play, i.e., if the player making the last move wins, the connection is given by:

\begin{equation*} \mathcal{P} = \{ u \in V : g ( u ) = 0 \}, \end{equation*}

\begin{equation*} \mathcal{N} = \{ u \in V : g ( u ) > 0 \}, \end{equation*}

where $\mathcal{P}$ is the set of all $P$-positions of the game and $\mathcal{N}$ is the set of all its $N$-positions. Informally, a $P$-position is any game position $u$ from which the  "p" {}revious player can force a win, that is, the opponent of the player moving from $u$. An $N$-position is any position $v$ from which the  "n" {}ext player can force a win, that is, the player who moves from $v$. More precisely, suppose one is given a finite or infinite game with game-graph $G = ( V , U )$, which may be cyclic. Denote by $\mathcal{O}$ the set of all non-negative ordinals not exceeding $| V |$. By recursion on $n \in \mathcal{O} $, define

\begin{equation*} P _ { n } = \left\{ u \in V : n = \operatorname { min } m , F ( u ) \subseteq \bigcup _ { i < m } N _ { i } \right\}, \end{equation*}

\begin{equation*} N _ { n } = \left\{ u \in V : n = \operatorname { min } m , F ( u ) \bigcap \bigcup _ { i < m } P _ { i } \neq \emptyset \right\}, \end{equation*}

and $\mathcal{P} = \cup _ { n \in \mathcal{O} } P _ { n }$ and $\mathcal{N} = \cup _ { n \in \mathcal{O} } N _ { n }$.

If $G$ is finite, acyclic and connected, there is a depth-first $O ( | E | )$ algorithm for computing $g$. However, there is an algorithm of the same complexity for computing $\mathcal{P}$ and $\mathcal{N}$ directly, so who needs $g$? (Cf. also [[Complexity theory|Complexity theory]].)

The answer lies in the important concept of a sum of games. Let $\{ \Gamma _ { 1 } , \dots , \Gamma _ { m } \}$ be a finite disjoint collection of games with game-graphs $\{ G _ { 1 } = ( V _ { 1 } , E _ { 1 } ) , \dots , G _ { m } = ( V _ { m } , E _ { m } ) \}$, which may have cycles or loops, or may be infinite. Then the sum-game $\Gamma = \Gamma _ { 1 } + \ldots + \Gamma _ { m }$ is the two-player game in which a position has the form $( u _ { 1 } , \ldots , u _ { m } )$ with $u_i \in V_i$ for all $i$, and a move consists of selecting some $\Gamma_{i}$ and making a legal move $u _ { i } \rightarrow v _ { i }$ in it ($( u _ { i } , v _ { i } ) \in E_i$).

The sum-graph $\mathbf{G} = G _ { 1 } + \ldots + G _ { m }$ is the digraph $ \mathbf{G} = ( \mathbf{V} , \mathbf{E} )$ defined as follows:

\begin{equation*} {\bf V} = \{ ( u _ { 1 } , \dots , u _ { m } ) : u _ { i } \in V _ { i } , i \in \{ 1 , \dots , m \} \}; \end{equation*}

if $\mathbf{u} = ( u _ { 1 } , \dots , u _ { m } ) , \mathbf{v} = ( v _ { 1 } , \dots , v _ { m } ) \in \mathbf{V}$, then $( \mathbf{u} , \mathbf{v} ) \in \mathbf{E}$ if there is some $j \in \{ 1 , \dots , m \}$ such that $v _ { j } \in F ( u _ { j } )$, that is, $( u _ { j } , v _ { j } ) \in E _ { j }$, and $u_i = v_i$ for all $i \neq j$.

Informally, the sum of games is a game in which a move consists of selecting one of the $\Gamma_{i}$ and making a move in it. For example, Nim is the sum of its heaps, and sums arise naturally in many games. The game-graph of a sum is normally exponential in the size of the $\Gamma_{i}$, so computing $\mathcal{P}$, $\mathcal{N}$ on it involves an exponential computation. But $g$ enables one to formulate a polynomial algorithm: For ${\bf u} = ( u _ { 1 } , \dots , u _ { m } ) \in \bf V$, let $\sigma ( \mathbf{u} ) = g ( u _ { 1 } ) \oplus \ldots \oplus g ( u _ { m } )$, where $\oplus$ denotes Nim addition, also known as Xor (i.e. exclusive or), or addition over $\operatorname {GF} ( 2 )$. Then $g ( \mathbf{u} ) = \sigma ( \mathbf{u} )$. For normal play one then has, in view of the above result,

\begin{equation*} \mathcal{P} = \{ \mathbf{u} \in \mathbf{V} : \sigma ( \mathbf{u} ) = 0 \}, \end{equation*}

\begin{equation*} \mathcal{N} = \{\mathbf u \in \mathbf V : \sigma ( \mathbf u ) > 0 \}. \end{equation*}

The polynomiality of the computation is valid for a standard game graph with input size $O ( | V |+ | E | )$. But many of the more interesting games are succinct, i.e., have input size $O ( \operatorname { log } ( | V | + | E | ) )$, and for them some additional property is needed to establish polynomiality. For Nim it is the fact that the $g$-values form an arithmetic sequence (cf. [[Arithmetic progression|Arithmetic progression]]); for many octal games [[#References|[a8]]] $g$ is ultimately polynomial, and for some other games special numeration systems can be exploited to recover polynomiality [[#References|[a5]]].

If the game-graph is cyclic, the game's outcome may be a draw, i.e., no player can force a win, but each has a non-losing next move. Two properties of $g$ collapse when $G$ has cycles:

i) it may not exist or not exist uniquely; in fact, the question of the existence of $g$ is $\cal N P$-complete [[#References|[a4]]]; and

ii) it may not determine the strategy.

Fortunately, however, there is a generalized Sprague–Grundy function $\gamma : V \rightarrow \mathbf{Z} ^ { 0 } \cup \{ \infty \}$, which exists uniquely on all finite and some infinite digraphs [[#References|[a9]]], [[#References|[a3]]], [[#References|[a2]]], where the symbol $\infty$ indicates a value larger than any natural number. One can define $\gamma$ also on certain subsets of vertices. Specifically:

\begin{equation*} \gamma ( F ( u ) ) = \{ \gamma ( v ) < \infty : v \in F ( u ) \}; \end{equation*}

if $\gamma ( u ) = \infty$ and $\gamma ( F ( u ) ) = K$, one also writes $\gamma ( u ) = \infty ( K )$.

Equality of $\gamma ( u )$ and $\gamma ( v )$: If $\gamma ( u ) =  k $ and $\gamma ( v ) = 1$, then $\gamma ( u ) = \gamma ( v )$ if one of the following holds:

a) $k = \text{l} < \infty$;

b) $k = \infty ( K )$, $\operatorname{l} = \infty ( L )$ and $K = L$. One also uses the notations

\begin{equation*} V ^ { f } = \{ u \in V : \gamma ( u ) <; \infty \}, \end{equation*}

\begin{equation*} V ^ { \infty } = V \backslash V ^ { f } , \gamma ^ { \prime } ( u ) = \operatorname { mex } \gamma ( F ( u ) ). \end{equation*}

Further, one associates a counter function with $\gamma$, in order to enable the winner to realize a win rather than merely maintaining a non-losing status in cycles.

Given a cyclic digraph $G = ( V , E )$, a function $\gamma : V \rightarrow \mathbf{Z} ^ { 0 } \cup \{ \infty \}$ is a $\gamma$-function with counter function $c : V ^ { f } \rightarrow J$, where $J$ is any infinite well-ordered set, if the following three conditions hold:

A) If $\gamma ( u ) < \infty$, then $\gamma ( u ) = \gamma ^ { \prime } ( u )$.

B) If $v \in F ( u )$ with $\gamma ( v ) > \gamma ( u )$, then there exists a $w \in F ( v )$ satisfying $\gamma ( w ) = \gamma ( u )$ and $c ( w ) < c ( u )$.

C) If $\gamma ( u ) = \infty$, then there is a $v \in F ( u )$ with $\gamma ( v ) = \infty ( K )$ such that $\gamma ^ { \prime } ( u ) \notin K$.

The generalized Nim-sum is defined as the Nim-sum above, augmented by:

\begin{equation*} k \bigoplus \infty ( L ) = \infty ( L ) \bigoplus k = \infty ( L \bigoplus k ), \end{equation*}

where $k \in \mathbf{Z} ^ { 0 }$, $L \subset \mathbf{Z} ^ { 0 }$, $L \neq \mathbf{Z} ^ { 0 }$, $L \oplus  k = \{ \text{l} \oplus  k  : \text{l} \in L \}$. The generalized Nim-sum of $\infty ( L _ { 1 } )$ and $\infty ( L _ { 2 } )$, for any subsets $L _ { 1 } , L _ { 2 } \subset \mathbf{Z} ^ { 0 }$, $L _ { 1 } , L _ { 2 } \neq \mathbf{Z} ^ { 0 }$, is defined by

\begin{equation*} \infty ( L _ { 1 } ) \bigoplus \infty ( L _ { 2 } ) = \infty ( L _ { 2 } ) \bigoplus \infty ( L _ { 1 } ) = \infty ( \emptyset ). \end{equation*}

To handle sums of games, one sets, analogously to the above Nim addition, $\sigma ( \mathbf{u} ) = \gamma ( u _ { 1 } ) \oplus \ldots \oplus \gamma ( u _ { m } )$, where now $\oplus$ denotes generalized Nim addition. For normal play one then has

\begin{equation*} \mathcal{P} = \{ \mathbf{u} \in V : \sigma ( \mathbf{u} ) = 0 \}, \end{equation*}

\begin{equation*} \mathcal{D} = \{ \mathbf{u} \in V : \sigma ( \mathbf{u} ) = \infty ( K ) , 0 \notin K \} , \mathcal{N} = \{ \mathbf{u} \in V : 0 < \sigma ( \mathbf{u} ) < \infty \} \bigcup \end{equation*}

\begin{equation*} \bigcup \{ \mathbf u \in V : \sigma ( \mathbf u ) = \infty ( K ) , 0 \in K \}, \end{equation*}

where $\mathcal{D}$ is the set of all  "d" {}raw positions. For a finite connected digraph $G = ( V , E )$, $\gamma$ can be computed in $O ( | V | | E | )$ steps, which is polynomial in the size of a standard digraph.

Many applications of the $g$-function to games appear in [[#References|[a1]]], and some of the results mentioned above are taken from [[#References|[a6]]].

====References====
<table>
<tr><td valign="top">[a1]</td> <td valign="top">  E.R. Berlekamp, J.H. Conway, R.K. Guy, "Winning ways for your mathematical plays" , '''I–II''' , Acad. Press  (1982)</td></tr>
<tr><td valign="top">[a2]</td> <td valign="top">  A.S. Fraenkel, O. Rahat, "Infinite cyclic impartial games"  ''Theoret. Computer Sci.'' , '''252'''  (2001)  pp. 13–22  (Special issue on Computer Games '98)</td></tr>
<tr><td valign="top">[a3]</td> <td valign="top">  A.S. Fraenkel, Y. Yesha, "Theory of annihilation games I"  ''J. Combin. Th. B'' , '''33'''  (1982)  pp. 60–86</td></tr>
<tr><td valign="top">[a4]</td> <td valign="top">  A.S. Fraenkel, "Planar kernel and Grundy with $d \leq 3$, $d _ { \operatorname{out} \leq} 2$, $d _ { \text{in} } \leq 2$ are NP-complete"  ''Discr. Appl. Math.'' , '''3'''  (1981)  pp. 257–262</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  A.S. Fraenkel, "Heap games, numeration systems and sequences"  ''Ann. Combinatorics'' , '''2'''  (1998)  pp. 197–210</td></tr>
<tr><td valign="top">[a6]</td> <td valign="top">  A.S. Fraenkel, "Adventures in games and computational complexity" , ''Graduate Studies in Mathematics'' , Amer. Math. Soc.  (to appear)</td></tr>
<tr><td valign="top">[a7]</td> <td valign="top">  P.M. Grundy, "Mathematics and games"  ''Eureka'' , '''27'''  (1964)  pp. 9–11  (Reprint; originally: ibid. 2 (1939), 6-8)</td></tr>
<tr><td valign="top">[a8]</td> <td valign="top">  R.K. Guy, C.A.B. Smith, "The $G$-values of various games"  ''Proc. Cambridge Philos. Soc.'' , '''52'''  (1956)  pp. 514–526</td></tr>
<tr><td valign="top">[a9]</td> <td valign="top">  C.A.B. Smith, "Graphs and composite games"  ''J. Combin. Th.'' , '''1'''  (1966)  pp. 51–81</td></tr>
<tr><td valign="top">[a10]</td> <td valign="top">  R. Sprague, "Über mathematische Kampfspiele"  ''Tôhoku Math. J.'' , '''41'''  (1935/36)  pp. 438–444</td></tr>
</table>