📄 sprague-grundy theory.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://yucs.org/~gnivasch/cgames/spraguegrundy/index.html -->
<HTML><HEAD><TITLE>Sprague-Grundy theory</TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<STYLE type=text/css>H2 {
MARGIN-BOTTOM: 10px; MARGIN-LEFT: 24px
}
LI.separated {
MARGIN-BOTTOM: 10px
}
P.date {
MARGIN-TOP: 0px; FONT-SIZE: small; MARGIN-LEFT: 24px; FONT-STYLE: italic
}
.myemph {
FONT-STYLE: italic; TEXT-DECORATION: underline
}
H3 {
MARGIN-LEFT: 15px
}
P.picture {
MARGIN-LEFT: 36px
}
TD.gr {
WIDTH: 22px; TEXT-ALIGN: right
}
</STYLE>
<META content="MSHTML 6.00.2800.1543" name=GENERATOR></HEAD>
<BODY>
<H2>The Sprague-Grundy theory of impartial games</H2>
<P class=date>November 9, 2005
<P>An <I>impartial game</I> is a two-player game in which both players have
complete information, no chance is involved, and the legal moves from each
position are the same for both players. We will deal with the <I>normal play</I>
rule, in which the last player to move is the winner.
<P>An impartial game can be abstractly represented by a <I>directed acyclic
graph</I>, in which each vertex corresponds to a position, and each directed
edge represents a legal move from one position to another.
<P class=picture><IMG alt="" src="Sprague-Grundy theory.files/dag.gif">
<P>We can imagine that a token is initially placed on some vertex, and the two
players take turns moving the token from its current vertex to one of its direct
followers. The game ends when the token reaches a <I>sink</I>, which is a vertex
with no outgoing edges, and then the last player to have moved is the winner.
<H3><I>P</I>- and <I>N</I>-positions</H3>
<P>We can classify each position in the game according to whether it is a first-
or a second-player win, if both players play optimally starting from that
position. A first-player-win position is known as an <I>N-position</I> (because
the <I><B>n</B></I>ext player is to win), while a second-player-win position is
known as a <I>P-position</I> (because the <I><B>p</B></I>revious player is to
win).
<P>The <I>P</I>- and <I>N</I>-positions can be characterized inductively as
follows:
<UL>
<LI class=separated>A vertex <I>v</I> is a <I>P</I>-position if and only if
<SPAN class=myemph>all</SPAN> its direct followers are <I>N</I>-positions.
<LI class=separated>A vertex <I>v</I> is an <I>N</I>-position if and only if
it has <SPAN class=myemph>some</SPAN> <I>P</I>-position follower. </LI></UL>
<P>The induction starts at the sinks, which are <I>P</I>-positions because they
vacuously satisfy the <I>P</I>-position requirement.
<P class=picture><IMG alt="" src="Sprague-Grundy theory.files/PN.gif">
<P>Knowledge of the <I>P</I>- and <I>N</I>-positions of a game provides the
winning strategy for it: If it is our turn and the game is in an
<I>N</I>-position, we should move into a <I>P</I>-position. Then our opponent
will be forced to move into an <I>N</I>-position, and so on. Eventually we will
move into a sink and win.
<H3>Sums of games</H3>
<P>If <I>G</I><SUB>1</SUB> and <I>G</I><SUB>2</SUB> are impartial games, then
their <I>sum</I> <I>G</I><SUB>1</SUB> + <I>G</I><SUB>2</SUB> is another
impartial game, which is played as follows: On each turn, a player chooses one
of <I>G</I><SUB>1</SUB>, <I>G</I><SUB>2</SUB> (whichever he wants) and plays on
it, leaving the other game untouched. The game ends when no moves are possible
on <I>G</I><SUB>1</SUB> nor on <I>G</I><SUB>2</SUB>.
<P>Formally, if <I>G</I><SUB>1</SUB> = (<I>V</I><SUB>1</SUB>,
<I>E</I><SUB>1</SUB>) and <I>G</I><SUB>2</SUB> = (<I>V</I><SUB>2</SUB>,
<I>E</I><SUB>2</SUB>) are game-graphs, then their sum <I>G</I><SUB>sum</SUB> =
(<I>V</I><SUB>sum</SUB>, <I>E</I><SUB>sum</SUB>) is given by:
<P class=picture><I>V</I><SUB>sum</SUB> = <I>V</I><SUB>1</SUB> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -