nim-value -- from wolfram mathworld.htm

Sprague-Grundy Value(博弈论)

                  title="Created, developed, and nurtured by Eric Weisstein with contributions from the world's mathematical community" 
                  height=49 
                  alt="Created, developed, and nurtured by Eric Weisstein with contributions from the world's mathematical community" 
                  src="Nim-Value -- from Wolfram MathWorld.files/created-by.gif" 
                  width=120 border=0 name=Image1></A> 
          </DIV></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><MAP id=SideMap 
      name=SideMap><AREA shape=RECT alt="Wolfram Research" coords=11,31,97,46 
        href="http://www.wolfram.com/"><AREA shape=RECT alt="Eric W. Weisstein" 
        coords=3,3,118,30 href="http://mathworld.wolfram.com/author.html"></MAP><!-- End Sidebar --></TD>
    <TD><IMG alt="" src="Nim-Value -- from Wolfram MathWorld.files/spacer.gif" 
      width=30></TD>
    <TD>
      <TABLE width="100%">
        <TBODY>
        <TR>
          <TD vAlign=top align=left width="100%">
            <DIV class=navbar><A 
            href="http://mathworld.wolfram.com/topics/RecreationalMathematics.html">Recreational 
            Mathematics</A>&nbsp;&gt;&nbsp;<A 
            href="http://mathworld.wolfram.com/topics/Games.html">Games</A>&nbsp;&gt;&nbsp;<A 
            href="http://mathworld.wolfram.com/topics/GeneralGames.html">General 
            Games</A>&nbsp;<BR><A 
            href="http://mathworld.wolfram.com/topics/AppliedMathematics.html">Applied 
            Mathematics</A>&nbsp;&gt;&nbsp;<A 
            href="http://mathworld.wolfram.com/topics/GameTheory.html">Game 
            Theory</A>&nbsp;<BR></DIV><BR>
            <TABLE cellSpacing=0 cellPadding=0 border=0>
              <TBODY>
              <TR>
                <TD class=title vAlign=baseline><SPAN 
                  class=nowrap>Nim-Value</SPAN></TD></TR>
              <TR>
                <TD vAlign=top><SPAN class=nowrap><IMG height=3 alt="" 
                  src="Nim-Value -- from Wolfram MathWorld.files/underline.gif" 
                  width="100%"><IMG height=3 alt="" 
                  src="Nim-Value -- from Wolfram MathWorld.files/underline.gif" 
                  width=20></SPAN></TD>
                <TD><IMG height=15 alt="" 
                  src="Nim-Value -- from Wolfram MathWorld.files/spacer.gif"></TD></TR></TBODY></TABLE></TD></TR>
        <TR vAlign=top>
          <TD width="100%"><A href="http://mathworld.wolfram.com/contact/" 
            target=_blank><IMG height=25 alt="COMMENT On this Page" 
            src="Nim-Value -- from Wolfram MathWorld.files/comment.gif" width=98 
            border=0></A><A 
            href="http://mathworld.wolfram.com/notebooks/Games/Nim-Value.nb"><IMG 
            height=26 alt="DOWNLOAD Mathematica Notebook" 
            src="Nim-Value -- from Wolfram MathWorld.files/dnld-nb.gif" 
            width=119 border=0></A> 
            <P class=Text>Every position of every <A class=Hyperlink 
            href="http://mathworld.wolfram.com/ImpartialGame.html">impartial 
            game</A> has a nim-value, making it equivalent to a <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/Nim-Heap.html">nim-heap</A>. To 
            find the nim-value (also called the Sprague-Grundy number), take the 
            <A class=Hyperlink 
            href="http://mathworld.wolfram.com/Mex.html">mex</A> of the 
            nim-values of the possible moves. The nim-value can also be found by 
            writing the number of counters in each heap in <A class=Hyperlink 
            href="http://mathworld.wolfram.com/Binary.html">binary</A>, adding 
            corresponding binary digits (mod 2), and interpreting the resulting 
            <A class=Hyperlink 
            href="http://mathworld.wolfram.com/Binary.html">binary</A> string as 
            a <A class=Hyperlink 
            href="http://mathworld.wolfram.com/Decimal.html">decimal</A> number. 
            </P>
            <P class=Text>If at any point in the game, the nim-value is 0 for a 
            given player, the position is <A class=Hyperlink 
            href="http://mathworld.wolfram.com/Safe.html">safe</A> (i.e., he 
            will always win if he plays correctly); otherwise, it is <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/Unsafe.html">unsafe</A> (i.e., he 
            will always lose if the other player plays correctly). With two 
            heaps in the game of <A class=Hyperlink 
            href="http://mathworld.wolfram.com/Nim.html">nim</A>, the only safe 
            positions are <IMG class=inlineformula height=15 alt=(x,x) 
            src="Nim-Value -- from Wolfram MathWorld.files/inline1.gif" width=32 
            border=0>. With three heaps (assuming nim-heaps of maximum size 7), 
            the safe positions are (1, 2, 3), (1, 4, 5), (1, 6, 7), (2, 4, 6), 
            (2, 5, 7), (3, 4, 7), and (3, 5, 6). For four nim-heaps of maximum 
            size 7, the safe positions are <IMG class=inlineformula height=15 
            alt=(x,x,x,x) 
            src="Nim-Value -- from Wolfram MathWorld.files/inline2.gif" width=62 
            border=0>, <IMG class=inlineformula height=15 alt=(x,x,y,y) 
            src="Nim-Value -- from Wolfram MathWorld.files/inline3.gif" width=62 
            border=0>, and (1, 2, 4, 7), (1, 2, 5, 6), (1, 3, 4, 6), (1, 3, 5, 
            7), (2, 3, 4, 5), (2, 3, 6, 7), and (4, 5, 6, 7). The position (1, 
            3, 5, 7) corresponds to the beginning state for the game <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/Marienbad.html">Marienbad</A>, 
            which is therefore an <A class=Hyperlink 
            href="http://mathworld.wolfram.com/UnfairGame.html">unfair game</A>. 
            </P>
            <FORM name=SearchLinks action=http://mathworld.wolfram.com/search/ 
            method=post>
            <P class=CrossRefs><SPAN class=crosslinkheader>SEE ALSO:</SPAN> <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/GrundysGame.html">Grundy's 
            Game</A>, <A class=Hyperlink 
            href="http://mathworld.wolfram.com/ImpartialGame.html">Impartial 
            Game</A>, <A class=Hyperlink 
            href="http://mathworld.wolfram.com/Marienbad.html">Marienbad</A>, <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/Mex.html">Mex</A>, <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/Nim.html">Nim</A>, <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/Safe.html">Safe</A>, <A 
            class=Hyperlink 
            href="http://mathworld.wolfram.com/Unsafe.html">Unsafe</A>. <INPUT 
            type=hidden value=http://mathworld.wolfram.com/Nim-Value.html 
            name=as_lq><A 
            href="javascript:document.forms.SearchLinks.submit();">[Pages&nbsp;Linking&nbsp;Here]</A> 
            </P></FORM>
            <P><IMG height=3 alt="" 
            src="Nim-Value -- from Wolfram MathWorld.files/underline.gif" 
            width=300> </P><SPAN class=crosslinkheader>REFERENCES:</SPAN> 
            <P class=Reference>Ball, W. W. R. and Coxeter, H. S. M. <I><A 
            class=Hyperlink 
            href="http://www.amazon.com/exec/obidos/ASIN/0486253570/ref=nosim/weisstein-20">Mathematical 
            Recreations and Essays, 13th ed.</A></I> New York: Dover, pp. 36-38, 
            1987. </P>
            <P class=Reference>Grundy, P. M. "Mathematics and Games." 
            <I>Eureka</I> <B>2</B>, 6-8, 1939. </P>
            <P class=Reference>Sprague, R. "躡er mathematische Kampfspiele." 
            <I>T鬶oku J. Math.</I> <B>41</B>, 438-444, 1936. </P>
            <DIV><IMG height=3 alt="" 
            src="Nim-Value -- from Wolfram MathWorld.files/underline.gif" 
            width=300><BR><BR>
            <DIV><SPAN class=crosslinkheader>LAST MODIFIED:</SPAN><SPAN 
            class=citation>&nbsp;<A 
            href="http://mathworld.wolfram.com/whatsnew/2002/04.html#26">April 
            26, 2002</A></SPAN> </DIV><BR><SPAN class=crosslinkheader>CITE THIS 
            AS:</SPAN><BR>
            <P class=citation><A 
            href="http://mathworld.wolfram.com/about/author.html">Weisstein, 
            Eric W.</A> "Nim-Value." From <A 
            href="http://mathworld.wolfram.com/"><I>MathWorld</I></A>--A Wolfram 
            Web Resource. <A 
            href="http://mathworld.wolfram.com/Nim-Value.html">http://mathworld.wolfram.com/Nim-Value.html</A> 
            </P><IMG height=3 alt="" 
            src="Nim-Value -- from Wolfram MathWorld.files/underline.gif" 
            width=300><BR>
            <P class=copyright>