📄 grundy's game.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0050)http://wwwhomes.uni-bielefeld.de/achim/grundy.html -->
<HTML><HEAD><TITLE>Grundy's Game</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312"><LINK rev=made
href="mailto:achim@mathematik.uni-bielefeld.de">
<META content="MSHTML 6.00.2800.1543" name=GENERATOR></HEAD>
<BODY>
<H1>Sprague-Grundy Values of Grundy's Game</H1>
<H2>Introduction</H2>Grundy's Game is a special case of a <B>Nim Game</B>. Given
a heap of size <TT>n</TT> and two players who alternately have to select a heap
and divide it into two unequal heaps. The player who can't make a legal move,
then all remaining heaps have size 1 or 2, loses.<BR>Therefore heapsizes <= 2
are lost and get the value 0. Generally a heap of size n has the value G(n) =
min{ <B>N</B><SUB>0</SUB> \ U <SUB>j</SUB> G(successor_position<SUB>j</SUB>) }.
This formula holds for all such ``Take-and-Break'' Games. <BR>The set of these
<STRONG>Spargue-Grundy-Values G(n)</STRONG> can be divided into a <STRONG>sparse
set</STRONG>, number of ones in the binary representation of G(n) without the
lowest digit is even, and its complement, called the <STRONG>common
set</STRONG>. Values of the sparse set occur extremly rare --- a value G(n)
belongs to the sparse set if and only if <EM>parity( G(n) AND m) = 0</EM> for a
fixed game specific bitstring <EM>m</EM>. 1287 are known for Grundy's Game which
has <EM>m=01111...</EM>, and if these die out the infinte sequence of the G(n)
must become periodic.<BR>Reference: E.R. Berlekamp, J.H. Conway, and R.K. Guy,
Winning Ways -- for Your mathematical Plays, Vol.1, Chap. 4, Academic Press
1982.
<H2>Known Sparse SGV of Grundy's Game</H2><PRE>G( 0)= 0 G( 1)= 0 G( 2)= 0 G( 3)= 1 G( 4)= 0
G( 6)= 1 G( 7)= 0 G( 9)= 1 G( 10)= 0 G( 12)= 1
G( 15)= 1 G( 20)= 0 G( 23)= 0 G( 26)= 0 G( 28)= 1
G( 31)= 1 G( 34)= 1 G( 37)= 1 G( 40)= 1 G( 43)= 1
G( 46)= 1 G( 49)= 1 G( 50)= 0 G( 52)= 1 G( 53)= 0
G( 55)= 1 G( 58)= 1 G( 61)= 1 G( 87)= 7 G( 90)= 7
G( 93)= 7 G( 146)= 6 G( 149)= 6 G( 152)= 6 G( 158)= 11
G( 161)= 11 G( 164)= 11 G( 167)= 11 G( 176)= 7 G( 179)= 7
G( 181)= 12 G( 182)= 7 G( 185)= 7 G( 188)= 7 G( 190)= 12
G( 193)= 12 G( 196)= 10 G( 231)= 10 G( 232)= 1 G( 235)= 1
G( 238)= 1 G( 270)= 0 G( 273)= 0 G( 276)= 0 G( 281)= 1
G( 282)= 0 G( 284)= 1 G( 285)= 0 G( 287)= 1 G( 288)= 0
G( 290)= 1 G( 291)= 13 G( 293)= 1 G( 294)= 13 G( 296)= 1
G( 297)= 13 G( 299)= 1 G( 300)= 13 G( 302)= 1 G( 303)= 13
G( 305)= 1 G( 306)= 13 G( 308)= 1 G( 309)= 13 G( 312)= 13
G( 315)= 13 G( 316)= 0 G( 324)= 1 G( 327)= 1 G( 330)= 1
G( 333)= 1 G( 334)= 0 G( 336)= 1 G( 337)= 0 G( 338)= 12
G( 339)= 1 G( 340)= 0 G( 341)= 12 G( 342)= 1 G( 345)= 1
G( 346)= 0 G( 348)= 1 G( 351)= 1 G( 359)= 0 G( 362)= 0
G( 365)= 0 G( 379)= 12 G( 380)= 7 G( 383)= 7 G( 386)= 0
G( 389)= 0 G( 392)= 0 G( 451)= 11 G( 454)= 11 G( 456)= 7
G( 457)= 11 G( 460)= 11 G( 469)= 7 G( 474)= 7 G( 500)= 11
G( 503)= 11 G( 507)= 6 G( 510)= 6 G( 512)= 13 G( 513)= 6
G( 515)= 13 G( 516)= 6 G( 519)= 6 G( 522)= 6 G( 524)= 10
G( 525)= 1 G( 527)= 10 G( 528)= 1 G( 541)= 21 G( 544)= 21
G( 566)= 0 G( 584)= 13 G( 587)= 13 G( 590)= 13 G( 593)= 13
G( 596)= 13 G( 599)= 13 G( 601)= 1 G( 602)= 13 G( 604)= 1
G( 605)= 13 G( 611)= 21 G( 620)= 18 G( 623)= 18 G( 624)= 13
G( 626)= 18 G( 627)= 13 G( 629)= 18 G( 630)= 0 G( 633)= 0
G( 634)= 12 G( 636)= 0 G( 639)= 0 G( 645)= 24 G( 648)= 21
G( 651)= 13 G( 660)= 21 G( 663)= 24 G( 666)= 24 G( 673)= 0
G( 676)= 0 G( 680)= 12 G( 682)= 0 G( 685)= 0 G( 735)= 11
G( 738)= 11 G( 741)= 11 G( 757)= 12 G( 760)= 12 G( 763)= 12
G( 782)= 10 G( 785)= 10 G( 788)= 24 G( 811)= 13 G( 828)= 10
G( 831)= 10 G( 852)= 24 G( 855)= 11 G( 858)= 11 G( 860)= 20
G( 863)= 20 G( 866)= 20 G( 877)= 24 G( 883)= 13 G( 886)= 13
G( 915)= 12 G( 918)= 12 G( 920)= 13 G( 921)= 12 G( 923)= 0
G( 926)= 0 G( 927)= 12 G( 929)= 0 G( 930)= 12 G( 932)= 0
G( 941)= 13 G( 944)= 13 G( 955)= 1 G( 956)= 24 G( 958)= 1
G( 959)= 21 G( 961)= 1 G( 962)= 21 G( 964)= 1 G( 967)= 12
G( 969)= 10 G( 970)= 12 G( 973)= 12 G( 976)= 12 G( 979)= 12
G( 1005)= 24 G( 1007)= 1 G( 1010)= 1 G( 1013)= 1 G( 1050)= 12
G( 1053)= 12 G( 1063)= 10 G( 1066)= 10 G( 1068)= 6 G( 1069)= 10
G( 1072)= 10 G( 1074)= 6 G( 1075)= 10 G( 1077)= 6 G( 1083)= 11
G( 1086)= 11 G( 1106)= 7 G( 1109)= 7 G( 1112)= 7 G( 1117)= 12
G( 1127)= 10 G( 1188)= 21 G( 1191)= 21 G( 1199)= 12 G( 1202)= 12
G( 1204)= 7 G( 1205)= 12 G( 1207)= 7 G( 1210)= 7 G( 1213)= 13
G( 1216)= 13 G( 1222)= 0 G( 1252)= 21 G( 1255)= 21 G( 1258)= 21
G( 1260)= 1 G( 1261)= 21 G( 1266)= 12 G( 1284)= 20 G( 1290)= 25
G( 1291)= 35 G( 1294)= 35 G( 1297)= 1 G( 1299)= 30 G( 1301)= 13
G( 1304)= 13 G( 1306)= 12 G( 1311)= 10 G( 1317)= 10 G( 1334)= 12
G( 1343)= 1 G( 1347)= 24 G( 1349)= 36 G( 1350)= 24 G( 1379)= 11
G( 1382)= 11 G( 1393)= 37 G( 1396)= 37 G( 1398)= 12 G( 1400)= 19
G( 1403)= 19 G( 1404)= 36 G( 1407)= 12 G( 1410)= 12 G( 1413)= 12
G( 1425)= 11 G( 1442)= 13 G( 1445)= 7 G( 1447)= 24 G( 1458)= 11
G( 1462)= 12 G( 1494)= 13 G( 1506)= 37 G( 1509)= 37 G( 1512)= 37
G( 1529)= 36 G( 1531)= 10 G( 1532)= 36 G( 1534)= 10 G( 1535)= 40
G( 1538)= 40 G( 1539)= 13 G( 1541)= 12 G( 1542)= 13 G( 1544)= 12
G( 1547)= 12 G( 1548)= 21 G( 1551)= 21 G( 1553)= 12 G( 1556)= 12
G( 1557)= 21 G( 1559)= 12 G( 1562)= 12 G( 1565)= 12 G( 1570)= 13
G( 1576)= 13 G( 1579)= 13 G( 1580)= 12 G( 1582)= 13 G( 1583)= 12
G( 1586)= 20 G( 1589)= 20 G( 1595)= 34 G( 1600)= 21 G( 1603)= 13
G( 1605)= 12 G( 1606)= 13 G( 1607)= 10 G( 1610)= 10 G( 1632)= 12
G( 1649)= 13 G( 1683)= 10 G( 1692)= 40 G( 1707)= 10 G( 1718)= 36
G( 1732)= 37 G( 1733)= 6 G( 1739)= 11 G( 1741)= 37 G( 1749)= 12
G( 1752)= 12 G( 1761)= 36 G( 1764)= 12 G( 1801)= 24 G( 1802)= 37
G( 1840)= 40 G( 1848)= 25 G( 1865)= 11 G( 1866)= 41 G( 1869)= 41
G( 1876)= 20 G( 1879)= 20 G( 1888)= 10 G( 1894)= 30 G( 1899)= 13
G( 1960)= 13 G( 1965)= 25 G( 1983)= 19 G( 1986)= 19 G( 1996)= 12
G( 1999)= 31 G( 2002)= 31 G( 2011)= 36 G( 2020)= 36 G( 2021)= 18
G( 2023)= 36 G( 2024)= 18 G( 2027)= 18 G( 2030)= 18 G( 2031)= 30
G( 2032)= 41 G( 2034)= 37 G( 2037)= 37 G( 2045)= 12 G( 2046)= 37
G( 2048)= 12 G( 2056)= 13 G( 2059)= 13 G( 2063)= 36 G( 2072)= 36
G( 2075)= 36 G( 2111)= 20 G( 2138)= 25 G( 2162)= 41 G( 2191)= 36
G( 2215)= 25 G( 2218)= 20 G( 2221)= 20 G( 2248)= 30 G( 2253)= 13
G( 2277)= 31 G( 2314)= 13 G( 2320)= 18 G( 2324)= 30 G( 2326)= 18
G( 2327)= 30 G( 2332)= 12 G( 2335)= 12 G( 2338)= 12 G( 2353)= 31
G( 2356)= 31 G( 2362)= 36 G( 2363)= 18 G( 2368)= 36 G( 2404)= 19
G( 2407)= 20 G( 2465)= 40 G( 2471)= 20 G( 2497)= 21 G( 2533)= 35
G( 2555)= 18 G( 2558)= 18 G( 2576)= 31 G( 2579)= 31 G( 2581)= 20
G( 2582)= 31 G( 2600)= 35 G( 2613)= 18 G( 2614)= 30 G( 2616)= 18
G( 2619)= 18 G( 2629)= 30 G( 2642)= 20 G( 2645)= 19 G( 2648)= 20
G( 2654)= 19 G( 2655)= 35 G( 2657)= 19 G( 2660)= 19 G( 2661)= 35
G( 2664)= 35 G( 2666)= 30 G( 2669)= 30 G( 2672)= 30 G( 2678)= 37
G( 2702)= 37 G( 2704)= 35 G( 2707)= 36 G( 2710)= 35 G( 2716)= 35
G( 2718)= 19 G( 2719)= 36 G( 2731)= 35 G( 2762)= 36 G( 2798)= 30
G( 2805)= 21 G( 2819)= 20 G( 2822)= 20 G( 2842)= 21 G( 2845)= 21
G( 2848)= 18 G( 2851)= 21 G( 2965)= 30 G( 2969)= 36 G( 2971)= 30
G( 2983)= 34 G( 2992)= 37 G( 3000)= 35 G( 3003)= 35 G( 3006)= 35
G( 3009)= 35 G( 3012)= 36 G( 3015)= 36 G( 3021)= 35 G( 3024)= 35
G( 3032)= 59 G( 3038)= 37 G( 3041)= 37 G( 3047)= 37 G( 3050)= 34
G( 3053)= 34 G( 3054)= 19 G( 3056)= 34 G( 3059)= 34 G( 3090)= 37
G( 3093)= 37 G( 3096)= 34 G( 3108)= 34 G( 3124)= 20 G( 3135)= 31
G( 3138)= 31 G( 3155)= 46 G( 3158)= 46 G( 3176)= 20 G( 3179)= 20
G( 3182)= 20 G( 3197)= 60 G( 3224)= 37 G( 3227)= 34 G( 3230)= 34
G( 3238)= 35 G( 3276)= 34 G( 3288)= 37 G( 3290)= 31 G( 3291)= 37
G( 3295)= 19 G( 3298)= 19 G( 3299)= 31 G( 3302)= 10 G( 3305)= 31
G( 3317)= 35 G( 3318)= 18 G( 3320)= 36 G( 3321)= 18 G( 3326)= 36
G( 3328)= 30 G( 3330)= 18 G( 3331)= 34 G( 3334)= 34 G( 3343)= 37
G( 3346)= 34 G( 3352)= 34 G( 3355)= 34 G( 3369)= 35 G( 3372)= 36
G( 3380)= 37 G( 3383)= 37 G( 3386)= 37 G( 3389)= 34 G( 3392)= 34
G( 3395)= 34 G( 3398)= 34 G( 3401)= 34 G( 3418)= 36 G( 3437)= 21
G( 3462)= 12 G( 3500)= 13 G( 3503)= 13 G( 3562)= 21 G( 3574)= 31
G( 3578)= 34 G( 3581)= 37 G( 3586)= 31 G( 3616)= 10 G( 3619)= 36
G( 3630)= 34 G( 3639)= 11 G( 3648)= 34 G( 3651)= 37 G( 3673)= 30
G( 3674)= 36 G( 3675)= 18 G( 3676)= 30 G( 3679)= 34 G( 3682)= 47
G( 3685)= 47 G( 3694)= 34 G( 3714)= 36 G( 3738)= 35 G( 3741)= 13
G( 3760)= 58 G( 3771)= 20 G( 3797)= 21 G( 3874)= 11 G( 3892)= 37
G( 3900)= 35 G( 3932)= 11 G( 3943)= 31 G( 3944)= 11 G( 3952)= 10
G( 3957)= 59 G( 3967)= 10 G( 3979)= 13 G( 4037)= 41 G( 4062)= 46
G( 4068)= 46 G( 4072)= 12 G( 4075)= 12 G( 4086)= 13 G( 4129)= 13
G( 4130)= 12 G( 4132)= 13 G( 4138)= 13 G( 4167)= 12 G( 4170)= 11
G( 4173)= 11 G( 4179)= 12 G( 4189)= 20 G( 4202)= 10 G( 4205)= 10
G( 4206)= 21 G( 4226)= 10 G( 4229)= 10 G( 4240)= 11 G( 4249)= 11
G( 4254)= 10 G( 4257)= 10 G( 4258)= 11 G( 4260)= 10 G( 4263)= 10
G( 4266)= 10 G( 4272)= 10 G( 4277)= 11 G( 4286)= 11 G( 4292)= 47
G( 4315)= 10 G( 4318)= 10 G( 4355)= 46 G( 4359)= 12 G( 4361)= 41
G( 4362)= 12 G( 4365)= 12 G( 4376)= 10 G( 4377)= 12 G( 4391)= 41
G( 4403)= 13 G( 4423)= 47 G( 4440)= 10 G( 4466)= 12 G( 4469)= 12
G( 4484)= 47 G( 4497)= 20 G( 4506)= 60 G( 4519)= 10 G( 4539)= 11
G( 4554)= 58 G( 4565)= 46 G( 4568)= 10 G( 4571)= 10 G( 4574)= 10
G( 4588)= 11 G( 4594)= 11 G( 4597)= 11 G( 4603)= 11 G( 4613)= 47
G( 4614)= 10 G( 4620)= 10 G( 4631)= 60 G( 4640)= 11 G( 4643)= 11
G( 4646)= 11 G( 4649)= 11 G( 4652)= 11 G( 4666)= 10 G( 4699)= 13
G( 4722)= 12 G( 4725)= 12 G( 4728)= 12 G( 4731)= 12 G( 4765)= 12
G( 4838)= 11 G( 4879)= 10 G( 4951)= 11 G( 4954)= 11 G( 4956)= 10
G( 4971)= 10 G( 4983)= 10 G( 4986)= 10 G( 5006)= 68 G( 5029)= 10
G( 5070)= 67 G( 5096)= 10 G( 5107)= 67 G( 5160)= 66 G( 5171)= 68
G( 5180)= 11 G( 5273)= 10 G( 5276)= 13 G( 5285)= 60 G( 5342)= 67
G( 5380)= 66 G( 5383)= 66 G( 5392)= 66 G( 5394)= 67 G( 5397)= 67
G( 5400)= 68 G( 5441)= 69 G( 5444)= 66 G( 5450)= 66 G( 5453)= 66
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -