nim-value -- from mathworld.htm

Sprague-Grundy Value(博弈论)

                  the Author</NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><A class=sidebarlink 
                  href="http://mathworld.wolfram.com/whatsnew/"><NOBR>New in 
                  <I>MathWorld</I></NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><A class=sidebarlink 
                  href="http://mathworld.wolfram.com/classroom/"><NOBR><I>MathWorld</I> 
                  Classroom</NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><A class=sidebarlink 
                  href="http://mathworld.wolfram.com/topics/InteractiveEntries.html"><NOBR>Interactive 
                  Entries</NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><A class=sidebarlink 
                  href="http://mathworld.wolfram.com/cgi-bin/random.cgi"><NOBR>Random 
                  Entry</NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><IMG height=9 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
                  width=1><BR><IMG height=3 alt="" 
                  src="Nim-Value -- From MathWorld.files/sidebar-line.gif" 
                  width=159></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><SPAN class=sidebarheader>CONTACT</SPAN></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><A class=sidebarlink 
                  href="http://mathworld.wolfram.com/contact/contribute.html"><NOBR>Contribute 
                  an Entry</NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><A class=sidebarlink style="LINE-HEIGHT: 14px" 
                  href="http://mathworld.wolfram.com/contact/"><NOBR>Send a 
                  Message to the Team</NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><IMG height=9 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
                  width=1><BR><IMG height=3 alt="" 
                  src="Nim-Value -- From MathWorld.files/sidebar-line.gif" 
                  width=159></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><SPAN class=sidebarheader><I>MATHWORLD</I> - IN 
                  PRINT</SPAN></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><A class=sidebarlink 
                  href="http://www.amazon.com/exec/obidos/ASIN/1584883472/weisstein-20" 
                  target=_blank><NOBR>Order book from Amazon</NOBR></A></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD><IMG height=6 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" width=1></TD>
                <TD width=1 bgColor=#98cdb9><IMG height=1 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif" 
              width=1></TD></TR>
              <TR>
                <TD colSpan=2>
                  <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
                    <TBODY>
                    <TR>
                      <TD rowSpan=2><IMG height=14 alt="" 
                        src="Nim-Value -- From MathWorld.files/bottom-angle.gif" 
                        width=12></TD>
                      <TD><IMG height=13 alt="" 
                        src="Nim-Value -- From MathWorld.files/spacer.gif" 
                        width=1></TD>
                      <TD width=1 bgColor=#98cdb9 rowSpan=2><IMG height=1 
                        alt="" 
                        src="Nim-Value -- From MathWorld.files/spacer.gif" 
                        width=1></TD></TR>
                    <TR>
                      <TD width="100%" bgColor=#98cdb9 height=1><IMG height=1 
                        alt="" 
                        src="Nim-Value -- From MathWorld.files/spacer.gif" 
                        width=1></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD>
    <TD><IMG alt="" src="Nim-Value -- From MathWorld.files/spacer.gif" 
      width=30></TD>
    <TD>
      <TABLE width="100%">
        <TBODY>
        <TR>
          <TD width="100%" colSpan=4>
            <DIV class=navbar><A 
            href="http://mathworld.wolfram.com/topics/RecreationalMathematics.html">Recreational 
            Mathematics</A>&nbsp;<IMG height=8 alt=">" 
            src="Nim-Value -- From MathWorld.files/gray_arrow_right.gif" width=8 
            border=0>&nbsp;<A 
            href="http://mathworld.wolfram.com/topics/Games.html">Games</A>&nbsp;<IMG 
            height=8 alt=">" 
            src="Nim-Value -- From MathWorld.files/gray_arrow_right.gif" width=8 
            border=0>&nbsp;<A 
            href="http://mathworld.wolfram.com/topics/GeneralGames.html">General 
            Games</A>&nbsp;<IMG height=8 alt=v 
            src="Nim-Value -- From MathWorld.files/gray_arrow_down.gif" width=8 
            border=0><BR><A 
            href="http://mathworld.wolfram.com/topics/AppliedMathematics.html">Applied 
            Mathematics</A>&nbsp;<IMG height=8 alt=">" 
            src="Nim-Value -- From MathWorld.files/gray_arrow_right.gif" width=8 
            border=0>&nbsp;<A 
            href="http://mathworld.wolfram.com/topics/GameTheory.html">Game 
            Theory</A>&nbsp;<IMG height=8 alt=v 
            src="Nim-Value -- From MathWorld.files/gray_arrow_down.gif" width=8 
            border=0><BR></DIV><BR><SPAN class=Title>
            <TABLE cellSpacing=0 cellPadding=0 border=0>
              <TBODY>
              <TR>
                <TD class=title vAlign=baseline><NOBR>Nim-Value</NOBR></TD></TR>
              <TR>
                <TD vAlign=top><NOBR><IMG height=3 alt="" 
                  src="Nim-Value -- From MathWorld.files/underline.gif" 
                  width="100%"><IMG height=3 alt="" 
                  src="Nim-Value -- From MathWorld.files/underline.gif" 
                  width=20></NOBR></TD>
                <TD><IMG height=15 alt="" 
                  src="Nim-Value -- From MathWorld.files/spacer.gif"></TD></TR></TBODY></TABLE></SPAN></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 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 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 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 MathWorld.files/inline2.gif" 
            width=62 border=0>, <IMG class=inlineformula height=15 alt=(x,x,y,y) 
            src="Nim-Value -- From 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>
            <P class=CrossRefs>
            <FORM name=SearchLinks action=http://mathworld.wolfram.com/search/ 
            method=post><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></FORM></P>
            <P><IMG height=3 alt="" 
            src="Nim-Value -- From 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. "&Uuml;ber mathematische Kampfspiele." 
            <I>T&ocirc;hoku J. Math.</I> <B>41</B>, 438-444, 1936. </P>
            <DIV><IMG height=3 alt="" 
            src="Nim-Value -- From MathWorld.files/underline.gif" 
            width=300><BR><BR><SPAN class=crosslinkheader>CITE THIS 
            AS:</SPAN><BR>
            <P class=citation>Eric W. Weisstein. "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 MathWorld.files/underline.gif" width=300><BR>
            <P class=copyright>&copy; 1999 CRC Press LLC, &copy; 1999-2006 <A 
            href="http://www.wolfram.com/">Wolfram Research, Inc.</A> | <A 
            href="http://mathworld.wolfram.com/about/terms.html">Terms of 
            Use</A> </P></DIV></TD>
          <TD><IMG alt="" src="Nim-Value -- From MathWorld.files/spacer.gif" 
            width=30></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></BODY></HTML>