Difference between revisions of "Sprague-Grundy function"
From Encyclopedia of Mathematics
Ulf Rehmann (talk | contribs) m (moved Sprague–Grundy function to Sprague-Grundy function: ascii title) |
m (AUTOMATIC EDIT (latexlist): Replaced 155 formulas out of 155 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.) |
||
| Line 1: | Line 1: | ||
| + | <!--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'' | ''Grundy–Sprague function, Grundy function'' | ||
| − | The 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 | + | 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 | + | 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 | + | 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 | + | and $\mathcal{P} = \cup _ { n \in \mathcal{O} } P _ { n }$ and $\mathcal{N} = \cup _ { n \in \mathcal{O} } N _ { n }$. |
| − | If | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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 | + | 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. | ii) it may not determine the strategy. | ||
| − | Fortunately, however, there is a generalized Sprague–Grundy function | + | 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 | + | if $\gamma ( u ) = \infty$ and $\gamma ( F ( u ) ) = K$, one also writes $\gamma ( u ) = \infty ( K )$. |
| − | Equality of | + | 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) | + | a) $k = \text{l} < \infty$; |
| − | b) | + | 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 | + | 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 | + | 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 | + | A) If $\gamma ( u ) < \infty$, then $\gamma ( u ) = \gamma ^ { \prime } ( u )$. |
| − | B) If | + | 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 | + | 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: | 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 | + | 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, | + | 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 | + | 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 | + | 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==== | ====References==== | ||
| − | <table>< | + | <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> |
Revision as of 16:45, 1 July 2020
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 |
How to Cite This Entry:
Sprague-Grundy function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sprague-Grundy_function&oldid=23035
Sprague-Grundy function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sprague-Grundy_function&oldid=23035
This article was adapted from an original article by Aviezri S. Fraenkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article