Namespaces
Variants
Actions

Difference between revisions of "Sprague-Grundy function"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(latex details)
 
(4 intermediate revisions by 3 users not shown)
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305101.png" /> from the vertex set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305102.png" /> of a digraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305103.png" /> into the non-negative integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305104.png" /> defined inductively by: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305105.png" />, where for any subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305106.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305108.png" /> least non-negative integer not in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s1305109.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051010.png" /> is the set of (directed) followers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051012.png" />. Informally, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051013.png" /> least non-negative integer not among the values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051014.png" />. Note that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051015.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051016.png" /> is a leaf of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051017.png" />, i.e., if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051018.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051020.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051021.png" /> there is a bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051022.png" /> such that the length of every (directed) walk emanating from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051023.png" /> does not exceed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051024.png" />. Every locally walk-bounded digraph has a unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051025.png" />-function. Moreover, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051026.png" />. In particular, every finite acyclic digraph has a unique <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051027.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051028.png" /> whose vertices are all the game positions, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051029.png" /> if and only if there is a legal move from position <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051030.png" /> to position <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051031.png" />. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051032.png" />-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:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051033.png" /></td> </tr></table>
+
\begin{equation*} \mathcal{P} = \{ u \in V : g ( u ) = 0 \}, \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051034.png" /></td> </tr></table>
+
\begin{equation*} \mathcal{N} = \{ u \in V : g ( u ) > 0 \}, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051035.png" /> is the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051036.png" />-positions of the game and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051037.png" /> is the set of all its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051038.png" />-positions. Informally, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051040.png" />-position is any game position <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051041.png" /> from which the  "p" {}revious player can force a win, that is, the opponent of the player moving from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051042.png" />. An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051044.png" />-position is any position <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051045.png" /> from which the  "n" {}ext player can force a win, that is, the player who moves from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051046.png" />. More precisely, suppose one is given a finite or infinite game with game-graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051047.png" />, which may be cyclic. Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051048.png" /> the set of all non-negative ordinals not exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051049.png" />. By recursion on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051050.png" />, define
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051051.png" /></td> </tr></table>
+
\begin{equation*} P _ { n } = \left\{ u \in V : n = \operatorname { min } m , F ( u ) \subseteq \bigcup _ { i < m } N _ { i } \right\}, \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051052.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051054.png" />.
+
and $\mathcal{P} = \cup _ { n \in \mathcal{O} } P _ { n }$ and $\mathcal{N} = \cup _ { n \in \mathcal{O} } N _ { n }$.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051055.png" /> is finite, acyclic and connected, there is a depth-first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051056.png" /> algorithm for computing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051057.png" />. However, there is an algorithm of the same complexity for computing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051059.png" /> directly, so who needs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051060.png" />? (Cf. also [[Complexity theory|Complexity theory]].)
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051061.png" /> be a finite disjoint collection of games with game-graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051062.png" />, which may have cycles or loops, or may be infinite. Then the sum-game <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051063.png" /> is the two-player game in which a position has the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051064.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051065.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051066.png" />, and a move consists of selecting some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051067.png" /> and making a legal move <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051068.png" /> in it (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051069.png" />).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051070.png" /> is the digraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051071.png" /> defined as follows:
+
The sum-graph $\mathbf{G} = G _ { 1 } + \ldots + G _ { m }$ is the digraph $ \mathbf{G} = ( \mathbf{V} , \mathbf{E} )$ defined as follows:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051072.png" /></td> </tr></table>
+
\begin{equation*} {\bf V} = \{ ( u _ { 1 } , \dots , u _ { m } ) : u _ { i } \in V _ { i } , i \in \{ 1 , \dots , m \} \}; \end{equation*}
  
if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051073.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051074.png" /> if there is some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051075.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051076.png" />, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051077.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051078.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051079.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051080.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051081.png" />, so computing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051082.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051083.png" /> on it involves an exponential computation. But <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051084.png" /> enables one to formulate a polynomial algorithm: For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051085.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051086.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051087.png" /> denotes Nim addition, also known as Xor (i.e. exclusive or), or addition over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051088.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051089.png" />. For normal play one then has, in view of the above result,
+
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,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051090.png" /></td> </tr></table>
+
\begin{equation*} \mathcal{P} = \{ \mathbf{u} \in \mathbf{V} : \sigma ( \mathbf{u} ) = 0 \}, \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051091.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051092.png" />. But many of the more interesting games are succinct, i.e., have input size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051093.png" />, and for them some additional property is needed to establish polynomiality. For Nim it is the fact that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051094.png" />-values form an arithmetic sequence (cf. [[Arithmetic progression|Arithmetic progression]]); for many octal games [[#References|[a8]]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051095.png" /> is ultimately polynomial, and for some other games special numeration systems can be exploited to recover polynomiality [[#References|[a5]]].
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051096.png" /> collapse when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051097.png" /> has cycles:
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s13051098.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510100.png" />-complete [[#References|[a4]]]; and
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510101.png" />, which exists uniquely on all finite and some infinite digraphs [[#References|[a9]]], [[#References|[a3]]], [[#References|[a2]]], where the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510102.png" /> indicates a value larger than any natural number. One can define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510103.png" /> also on certain subsets of vertices. Specifically:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510104.png" /></td> </tr></table>
+
\begin{equation*} \gamma ( F ( u ) ) = \{ \gamma ( v ) < \infty : v \in F ( u ) \}; \end{equation*}
  
if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510105.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510106.png" />, one also writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510107.png" />.
+
if $\gamma ( u ) = \infty$ and $\gamma ( F ( u ) ) = K$, one also writes $\gamma ( u ) = \infty ( K )$.
  
Equality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510108.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510109.png" />: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510110.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510111.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510112.png" /> if one of the following holds:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510113.png" />;
+
a) $k = \text{l} < \infty$;
  
b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510114.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510115.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510116.png" />. One also uses the notations
+
b) $k = \infty ( K )$, $\operatorname{l} = \infty ( L )$ and $K = L$. One also uses the notations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510117.png" /></td> </tr></table>
+
\begin{equation*} V ^ { f } = \{ u \in V : \gamma ( u ) <; \infty \}, \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510118.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510119.png" />, in order to enable the winner to realize a win rather than merely maintaining a non-losing status in cycles.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510120.png" />, a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510121.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510123.png" />-function with counter function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510124.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510125.png" /> is any infinite well-ordered set, if the following three conditions hold:
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510126.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510127.png" />.
+
A) If $\gamma ( u ) < \infty$, then $\gamma ( u ) = \gamma ^ { \prime } ( u )$.
  
B) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510128.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510129.png" />, then there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510130.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510131.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510132.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510133.png" />, then there is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510134.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510135.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510136.png" />.
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510137.png" /></td> </tr></table>
+
\begin{equation*} k \bigoplus \infty ( L ) = \infty ( L ) \bigoplus k = \infty ( L \bigoplus k ), \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510138.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510139.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510140.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510141.png" />. The generalized Nim-sum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510142.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510143.png" />, for any subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510144.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510145.png" />, is defined by
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510146.png" /></td> </tr></table>
+
\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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510147.png" />, where now <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510148.png" /> denotes generalized Nim addition. For normal play one then has
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510149.png" /></td> </tr></table>
+
\begin{equation*} \mathcal{P} = \{ \mathbf{u} \in V : \sigma ( \mathbf{u} ) = 0 \}, \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510150.png" /></td> </tr></table>
+
\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*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510151.png" /></td> </tr></table>
+
\begin{equation*} \bigcup \{ \mathbf u \in V : \sigma ( \mathbf u ) = \infty ( K ) , 0 \in K \}, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510152.png" /> is the set of all  "d" {}raw positions. For a finite connected digraph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510153.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510154.png" /> can be computed in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510155.png" /> steps, which is polynomial in the size of a standard digraph.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510156.png" />-function to games appear in [[#References|[a1]]], and some of the results mentioned above are taken from [[#References|[a6]]].
+
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><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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510157.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510158.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510159.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s130/s130510/s130510160.png" />-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>
+
<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>

Latest revision as of 16:52, 18 February 2024

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=19261
This article was adapted from an original article by Aviezri S. Fraenkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article