Sprague-Grundy function

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, [a7]. Only later the more obscure but earlier reference [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), 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.)

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); for many octal games [a8] $g$ is ultimately polynomial, and for some other games special numeration systems can be exploited to recover polynomiality [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 [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 [a9], [a3], [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 [a1], and some of the results mentioned above are taken from [a6].

References

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