Difference between revisions of "Sprague-Grundy function"
(Importing text file) |
Ulf Rehmann (talk | contribs) m (moved Sprague–Grundy function to Sprague-Grundy function: ascii title) |
(No difference)
|
Revision as of 18:54, 24 March 2012
Grundy–Sprague function, Grundy function
The function from the vertex set
of a digraph
into the non-negative integers
defined inductively by:
, where for any subset
,
,
least non-negative integer not in
,
is the set of (directed) followers of
and
. Informally,
least non-negative integer not among the values
. Note that
if
is a leaf of
, i.e., if
. 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
-function.
A digraph is locally walk-bounded if for every vertex there is a bound
such that the length of every (directed) walk emanating from
does not exceed
. Every locally walk-bounded digraph has a unique
-function. Moreover,
. In particular, every finite acyclic digraph has a unique
-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 whose vertices are all the game positions, and
if and only if there is a legal move from position
to position
. The
-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:
![]() |
![]() |
where is the set of all
-positions of the game and
is the set of all its
-positions. Informally, a
-position is any game position
from which the "p" {}revious player can force a win, that is, the opponent of the player moving from
. An
-position is any position
from which the "n" {}ext player can force a win, that is, the player who moves from
. More precisely, suppose one is given a finite or infinite game with game-graph
, which may be cyclic. Denote by
the set of all non-negative ordinals not exceeding
. By recursion on
, define
![]() |
![]() |
and and
.
If is finite, acyclic and connected, there is a depth-first
algorithm for computing
. However, there is an algorithm of the same complexity for computing
and
directly, so who needs
? (Cf. also Complexity theory.)
The answer lies in the important concept of a sum of games. Let be a finite disjoint collection of games with game-graphs
, which may have cycles or loops, or may be infinite. Then the sum-game
is the two-player game in which a position has the form
with
for all
, and a move consists of selecting some
and making a legal move
in it (
).
The sum-graph is the digraph
defined as follows:
![]() |
if , then
if there is some
such that
, that is,
, and
for all
.
Informally, the sum of games is a game in which a move consists of selecting one of the 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
, so computing
,
on it involves an exponential computation. But
enables one to formulate a polynomial algorithm: For
, let
, where
denotes Nim addition, also known as Xor (i.e. exclusive or), or addition over
. Then
. For normal play one then has, in view of the above result,
![]() |
![]() |
The polynomiality of the computation is valid for a standard game graph with input size . But many of the more interesting games are succinct, i.e., have input size
, and for them some additional property is needed to establish polynomiality. For Nim it is the fact that the
-values form an arithmetic sequence (cf. Arithmetic progression); for many octal games [a8]
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 collapse when
has cycles:
i) it may not exist or not exist uniquely; in fact, the question of the existence of is
-complete [a4]; and
ii) it may not determine the strategy.
Fortunately, however, there is a generalized Sprague–Grundy function , which exists uniquely on all finite and some infinite digraphs [a9], [a3], [a2], where the symbol
indicates a value larger than any natural number. One can define
also on certain subsets of vertices. Specifically:
![]() |
if and
, one also writes
.
Equality of and
: If
and
, then
if one of the following holds:
a) ;
b) ,
and
. One also uses the notations
![]() |
![]() |
Further, one associates a counter function with , in order to enable the winner to realize a win rather than merely maintaining a non-losing status in cycles.
Given a cyclic digraph , a function
is a
-function with counter function
, where
is any infinite well-ordered set, if the following three conditions hold:
A) If , then
.
B) If with
, then there exists a
satisfying
and
.
C) If , then there is a
with
such that
.
The generalized Nim-sum is defined as the Nim-sum above, augmented by:
![]() |
where ,
,
,
. The generalized Nim-sum of
and
, for any subsets
,
, is defined by
![]() |
To handle sums of games, one sets, analogously to the above Nim addition, , where now
denotes generalized Nim addition. For normal play one then has
![]() |
![]() |
![]() |
where is the set of all "d" {}raw positions. For a finite connected digraph
,
can be computed in
steps, which is polynomial in the size of a standard digraph.
Many applications of the -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 ![]() ![]() ![]() |
[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 ![]() |
[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 |
Sprague-Grundy function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sprague-Grundy_function&oldid=23035