2498:
66:
2176:
2493:{\displaystyle \color {blue}S\color {black}+\color {red}S'\color {black}={\Big \{}\color {blue}S\color {black}+\color {red}\{*1\}\color {black}{\Big \}}\cup {\Big \{}\color {red}S'\color {black}+\color {blue}\{*1,\{*1\},*2\}\color {black},\color {red}S'\color {black}+\color {blue}\{*2,\{*1,\{*1\},*2\}\}\color {black},\color {red}S'\color {black}+\color {blue}\{\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}\}\color {black}{\Big \}}}
25:
128:
2073:
6194:
is called its Grundy value, or Grundy number, and the function that assigns this value to each such position is called the
Sprague–Grundy function. R. L. Sprague and P. M. Grundy independently gave an explicit definition of this function, not based on any concept of equivalence to nim positions, and
1811:
Sizes of heaps Moves A B C A' B' C' 1 2 2 1 1 1 Alice takes 1 from A 0 2 2 1 1 1 Bob takes 1 from A' 0 2 2 0 1 1 Alice takes 1 from B' 0 2 2 0 0 1 Bob takes 1 from C' 0 2 2 0 0 0 Alice takes 2 from B 0 0 2 0 0 0 Bob takes 2 from C 0
607:
At step 4, Bob had two options: remove one from B or remove one from C. Note, however, that it didn't really matter which heap Bob removed the object from: Either way, Alice would be left with exactly one object in exactly one pile. So, using our recursive definition, Bob really only has one move:
1202:
425:
is not impartial because, supposing Alice were playing red and Bob were playing black, for any given arrangement of pieces on the board, if it were Alice's turn, she would only be allowed to move the red pieces, and if it were Bob's turn, he would only be allowed to move the black pieces.
414:
is an example of an impartial game. In nim, there are one or more heaps of objects, and two players (we'll call them Alice and Bob), take turns choosing a heap and removing 1 or more objects from it. The winner is the player who removes the final object from the final heap. The game is
238:
of any impartial game is the unique nimber that the game is equivalent to. In the case of a game whose positions are indexed by the natural numbers (like nim itself, which is indexed by its heap sizes), the sequence of nimbers for successive positions of the game is called the
467:
Sizes of heaps Moves A B C 1 2 2 Alice takes 1 from A 0 2 2 Bob takes 1 from B 0 1 2 Alice takes 1 from C 0 1 1 Bob takes 1 from B 0 0 1 Alice takes 1 from C 0 0 0 Bob has no moves, so Alice
1844:
978:
2611:
6415:. Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it follows directly from their results and is credited to them. These results have subsequently been developed into the field of
2173:, remember that a player can either make a move in the first game, leaving the second game untouched, or make a move in the second game, leaving the first game untouched. So the combined game's starting position is:
3196:
3135:
1660:
Sizes of heaps Moves A' B' C' 1 1 1 Alice takes 1 from A' 0 1 1 Bob takes one from B' 0 0 1 Alice takes one from C' 0 0 0 Bob has no moves, so Alice
1559:, nimbers can be used to describe the positions of any finite, impartial game, and in fact, the Sprague–Grundy theorem states that every instance of a finite, impartial game can be associated with a
2165:
4857:
971:
421:
because for any given configuration of pile sizes, the moves Alice can make on her turn are exactly the same moves Bob would be allowed to make if it were his turn. In contrast, a game such as
429:
Note that any configuration of an impartial game can therefore be written as a single position, because the moves will be the same no matter whose turn it is. For example, the position of the
4725:
889:
456:, because if it's Alice's turn, she has no moves to make, and if it's Bob's turn, he has no moves to make either. A move can be associated with the position it leaves the next player in.
4556:
2678:
2649:
4969:
4502:
4404:
1546:
4772:
3046:
2106:
6086:
5413:
397:
6052:
5318:
5030:
4639:
4071:
3982:
2882:
6287:
5708:
5522:
5379:
5287:
5232:
4460:
4323:
4239:
4037:
3914:
3858:
3788:
3764:
3708:
3655:
3547:
3431:
3248:
3159:
3098:
3070:
3019:
2997:
2777:
2730:
1839:
146:
5607:
4355:
3300:
1461:
6192:
6115:
4886:
4299:
2068:{\displaystyle \color {blue}S={\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}}
5885:
5799:
5498:
5355:
5263:
5081:
4159:
4128:
4013:
2962:
2905:
1414:
805:
5684:
5576:
4608:
4580:
5971:
5736:
5656:
5441:
5208:
5183:
2825:
1801:
1776:
1751:
1650:
1625:
1600:
1487:
5915:
5852:
5766:
5158:
713:
658:
579:
6018:
5108:
4996:
4436:
3890:
3740:
3631:
3463:
3358:
6393:
1376:
493:
454:
6364:
4215:
4189:
4097:
3940:
3814:
3684:
3599:
3573:
3407:
3326:
2931:
6240:
5938:
5822:
5548:
5464:
2753:
2706:
1353:
1310:
1279:
1256:
1233:
828:
763:
740:
684:
629:
602:
546:
516:
6413:
6338:
6318:
6260:
6217:
6163:
6143:
5991:
5627:
5128:
5050:
4906:
4259:
3834:
3523:
3503:
3483:
3378:
3268:
3224:
2851:
2800:
1726:
1706:
1686:
1330:
341:
321:
1197:{\displaystyle {\Big \{}{\big \{}*1,\{*1\},*2{\big \}},{\big \{}*2,\{*1,\{*1\},*2\}{\big \}},{\big \{}\{*1\},\{\{*1\}\},\{*1,\{*1\},*2\}{\big \}}{\Big \}}.}
38:
4653:. The more specific result, that the given game's initial position must be equivalent to a nimber, shows that the game is itself equivalent to a nimber.
6431:
and others, where they are now encapsulated in the
Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books
7760:
6530:
6433:
227:, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.
2111:
6693:
897:
7592:
87:
3164:
2505:
663:
At step 3, Alice had 3 options: remove two from C, remove one from C, or remove one from B. Removing two from C leaves Bob in position
7755:
7409:
6944:
6742:
7228:
7047:
182:
164:
109:
52:
6849:
3103:
44:
7318:
459:
Doing so allows positions to be defined recursively. For example, consider the following game of Nim played by Alice and Bob.
6859:
7188:
6525:
7369:
6787:
6762:
6457:
4777:
7719:
7145:
6899:
6889:
6824:
6939:
6919:
6486:
4659:
80:
74:
833:
7653:
7374:
7032:
6874:
6869:
2659:
2630:
410:
is one in which at any given point in the game, each player is allowed exactly the same set of moves. Normal-play
7689:
7612:
7348:
6904:
6829:
6686:
6416:
521:
At step 5, Alice had exactly one option: to remove one object from heap C, leaving Bob with no moves. Since her
196:
91:
7704:
7437:
7323:
7120:
6914:
6732:
4915:
7507:
246:
The
Sprague–Grundy theorem and its proof encapsulate the main results of a theory discovered independently by
7709:
7308:
7278:
6934:
6722:
7643:
7734:
7714:
7694:
7313:
7218:
7077:
7027:
7022:
6954:
6924:
6844:
6772:
6659:
6521:
4728:
4261:, the previous player can respond with the same move in the other copy, and so always make the last move.
1492:
251:
208:
4734:
6752:
4507:
715:, as described in step 4. However, removing 1 from B would leave Bob with two objects in a single pile.
7193:
7178:
4360:
346:
7527:
7512:
7399:
7394:
7298:
7283:
7248:
7213:
6812:
6757:
6679:
6481:
6439:
4650:
4583:
303:
to be the two-player game where neither player has any legal moves. Referring to the two players as
6268:
5689:
5503:
5360:
5268:
5213:
4465:
4441:
4304:
4220:
4018:
3895:
3839:
3769:
3745:
3689:
3636:
3528:
3412:
3229:
3140:
3079:
3051:
3024:
3002:
2978:
2758:
2711:
2084:
1822:
7684:
7303:
7253:
7090:
7017:
6997:
6854:
6737:
4587:
273:
6664:
6057:
5384:
4328:
3273:
1419:
7663:
7522:
7353:
7333:
7183:
7062:
6967:
6894:
6839:
6604:
6586:
6428:
6168:
6091:
6026:
5292:
5004:
4862:
4613:
4045:
3956:
2856:
5857:
5771:
2887:
1381:
772:
7648:
7617:
7572:
7467:
7338:
7293:
7268:
7198:
7072:
7002:
6992:
6884:
6834:
6782:
4909:
4593:
4565:
5943:
5581:
1466:
7729:
7724:
7658:
7622:
7602:
7562:
7532:
7487:
7442:
7427:
7384:
7238:
6879:
6816:
6802:
6767:
6625:
6596:
6503:
6495:
5890:
5827:
5741:
5133:
4267:
689:
634:
555:
6577:
Schleicher, Dierk; Stoll, Michael (2006). "An introduction to Conway's games and numbers".
5996:
5469:
5326:
5086:
4974:
4409:
3863:
3713:
3604:
3436:
3331:
7627:
7587:
7542:
7457:
7452:
7173:
7125:
7012:
6777:
6747:
6717:
6507:
6499:
6424:
6369:
5237:
5055:
4133:
4102:
3987:
2936:
1358:
475:
436:
269:
7492:
6343:
5661:
5553:
4194:
4168:
4076:
3919:
3793:
3663:
3578:
3552:
3386:
3305:
2910:
6639:
6600:
6222:
5920:
5804:
5716:
5636:
5530:
5446:
5421:
5188:
5163:
2805:
2735:
2688:
1781:
1756:
1731:
1630:
1605:
1580:
1335:
1292:
1261:
1238:
1215:
810:
745:
722:
666:
611:
584:
528:
498:
7567:
7557:
7547:
7482:
7472:
7462:
7447:
7243:
7223:
7208:
7203:
7163:
7130:
7115:
7110:
7100:
6909:
6477:
6420:
6398:
6323:
6303:
6245:
6202:
6148:
6128:
5976:
5612:
5113:
5035:
4891:
4244:
3819:
3508:
3488:
3468:
3363:
3253:
3209:
2836:
2785:
1711:
1691:
1671:
1315:
405:
326:
306:
247:
220:
216:
204:
6634:
1332:
objects in exactly one heap. Formally, nimbers are defined inductively as follows:
7749:
7607:
7597:
7552:
7537:
7517:
7343:
7288:
7263:
7135:
7105:
7095:
7082:
6987:
6929:
6864:
6797:
4559:
4162:
3206:
As an intermediate step to proving the main theorem, we show that for every position
2975:
games above, we can show that on every turn, Alice has a move that forces Bob into a
7582:
7577:
7432:
7007:
6650:
6629:
6608:
6452:
686:. Removing one from C leaves Bob with two piles, each of size one, i.e., position
4562:
and commutativity, the right-hand sides of these results are equal. Furthermore,
6539:
7699:
7502:
7497:
7477:
7273:
7258:
7067:
7037:
6972:
6962:
6792:
6727:
6703:
5940:; in either case the result is a position plus itself. (It is not possible that
215:, or to an infinite generalization of nim. It can therefore be represented as a
1577:
their positions together. For example, consider another game of nim with heaps
7328:
6982:
3302:
holds. By the above definition of equivalence, this amounts to showing that
7233:
7153:
6977:
16:
Every impartial game position is equivalent to a position in the game of nim
7668:
7168:
4586:
because equality is an equivalence relation on outcome classes. Via the
2853:
is added to them, they are always in the same outcome class. Formally,
422:
6671:
6591:
472:
At step 6 of the game (when all of the heaps are empty) the position is
280:(all games come to an end: there are no infinite lines of play) and the
7389:
7379:
7057:
6293:
6292:
The Grundy value of the sum of a finite set of positions is just the
5713:
Finally, suppose instead that the next player moves in the component
1312:
corresponds to the position in a game of nim where there are exactly
1284:
224:
6395:, and therefore belongs to the same outcome class, for any position
3766:-position, because the next player has a winning strategy: choose a
6635:
Easily readable, introductory account from the UCLA Math
Department
6300:
It follows straightforwardly from these results that if a position
5415:. We do so by giving an explicit strategy for the previous player.
7158:
3191:{\displaystyle \color {blue}S\color {black}\approx \color {red}S'}
2606:{\displaystyle S+S'=\{S+s'\mid s'\in S'\}\cup \{s+S'\mid s\in S\}}
5527:
Or consider the case that the next player moves in the component
3816:
options, and we conclude from the previous paragraph that adding
2665:
2636:
2613:, which means that addition is both commutative and associative.
894:
Following the same recursive logic, at step 2, Bob's position is
495:, because Bob has no valid moves to make. We name this position
6558:
Smith, Cedric A.B. (1960), "Patrick
Michael Grundy, 1917–1959",
5381:-position, which, using the second lemma once again, means that
3433:-position. Then the previous player has a winning strategy for
6675:
4971:, that is, the smallest non-negative integer not equal to some
411:
212:
121:
59:
18:
2627:: either the next player (the one whose turn it is) wins (an
6274:
5695:
5509:
5366:
5274:
5219:
4447:
4310:
4226:
4024:
3901:
3845:
3775:
3751:
3695:
3642:
3534:
3418:
3235:
3146:
3085:
3057:
2984:
2764:
2717:
299:
they are allowed to make. As an example, we can define the
219:, the size of the heap in its equivalent game of nim, as an
5052:
is zero, the claim is trivially true. Otherwise, consider
3130:{\displaystyle \color {blue}S\color {black}+\color {red}S'}
4649:
We prove that all positions are equivalent to a nimber by
4325:-position by hypothesis, it follows from the first lemma,
6265:
A position is a loss for the next player to move (i.e. a
5234:-position by the lemma's forward implication. Therefore,
5289:-position, and, citing the lemma's reverse implication,
4462:-position, it follows from the first lemma in the form
2160:{\displaystyle \color {red}S'={\Big \{}\{*1\}{\Big \}}.}
399:, since the set of moves each player can make is empty.
262:
For the purposes of the
Sprague–Grundy theorem, a
6289:-position) if and only if its Grundy value is zero; and
6145:
is a position of an impartial game, the unique integer
5686:. And, as shown before, any position plus itself is a
142:
6643:
966:{\displaystyle {\big \{}\{*1,\{*1\},*2\},*2{\big \}}.}
830:. Alice's position is then the set of all her moves:
223:
in the infinite generalization, or alternatively as a
6401:
6372:
6346:
6326:
6306:
6271:
6248:
6225:
6205:
6171:
6151:
6131:
6094:
6060:
6029:
5999:
5979:
5946:
5923:
5893:
5860:
5830:
5807:
5774:
5744:
5719:
5692:
5664:
5639:
5615:
5584:
5556:
5533:
5506:
5472:
5449:
5424:
5387:
5363:
5329:
5295:
5271:
5240:
5216:
5191:
5166:
5136:
5116:
5089:
5058:
5038:
5007:
4977:
4918:
4894:
4865:
4780:
4737:
4662:
4616:
4596:
4568:
4510:
4468:
4444:
4412:
4363:
4331:
4307:
4270:
4247:
4223:
4197:
4171:
4136:
4105:
4079:
4048:
4021:
3990:
3959:
3922:
3898:
3866:
3842:
3822:
3796:
3772:
3748:
3716:
3692:
3666:
3639:
3607:
3581:
3555:
3531:
3511:
3491:
3471:
3439:
3415:
3389:
3366:
3334:
3308:
3276:
3256:
3232:
3212:
3167:
3143:
3106:
3082:
3054:
3027:
3005:
2981:
2967:
To use our running examples, notice that in both the
2939:
2913:
2890:
2859:
2839:
2808:
2788:
2761:
2738:
2714:
2691:
2662:
2633:
2508:
2179:
2114:
2087:
1847:
1825:
1784:
1759:
1734:
1714:
1694:
1674:
1633:
1608:
1583:
1495:
1469:
1422:
1384:
1361:
1338:
1318:
1295:
1264:
1241:
1218:
981:
900:
836:
813:
775:
748:
725:
692:
669:
637:
614:
587:
558:
531:
501:
478:
439:
349:
329:
309:
5185:, and conversely if the next player makes a move in
4731:, all of the options are equivalent to nimbers, say
7677:
7636:
7418:
7362:
7144:
7046:
6953:
6811:
6710:
4852:{\displaystyle G'=\{*n_{1},*n_{2},\ldots ,*n_{k}\}}
137:
may be too technical for most readers to understand
6560:Journal of the Royal Statistical Society, Series A
6407:
6387:
6358:
6332:
6312:
6281:
6254:
6234:
6211:
6186:
6157:
6137:
6109:
6080:
6046:
6012:
5985:
5965:
5932:
5909:
5879:
5846:
5816:
5793:
5760:
5730:
5702:
5678:
5650:
5621:
5601:
5570:
5542:
5516:
5492:
5458:
5435:
5407:
5373:
5349:
5312:
5281:
5257:
5226:
5202:
5177:
5152:
5122:
5102:
5075:
5044:
5024:
4990:
4963:
4900:
4880:
4851:
4766:
4719:
4633:
4602:
4574:
4550:
4496:
4454:
4430:
4398:
4349:
4317:
4293:
4253:
4233:
4209:
4183:
4153:
4122:
4091:
4065:
4031:
4007:
3976:
3945:As these are the only two cases, the lemma holds.
3934:
3908:
3884:
3852:
3828:
3808:
3782:
3758:
3734:
3702:
3678:
3649:
3625:
3593:
3567:
3541:
3517:
3497:
3477:
3457:
3425:
3401:
3372:
3352:
3320:
3294:
3262:
3242:
3218:
3190:
3161:-position, which as we will see in Lemma 2, means
3153:
3129:
3092:
3064:
3040:
3013:
2991:
2956:
2925:
2899:
2876:
2845:
2819:
2794:
2771:
2747:
2724:
2700:
2672:
2643:
2605:
2492:
2159:
2100:
2067:
1833:
1795:
1770:
1745:
1720:
1700:
1680:
1644:
1619:
1594:
1540:
1481:
1455:
1408:
1370:
1347:
1324:
1304:
1273:
1250:
1227:
1196:
965:
883:
822:
799:
757:
734:
707:
678:
652:
623:
596:
573:
540:
510:
487:
448:
391:
335:
315:
5633:excluded number, the previous player can move in
2465:
2242:
2232:
2203:
2148:
2129:
2059:
1857:
1186:
984:
3072:-positions. (Notice that in the combined game,
1815:To differentiate between the two games, for the
1812:0 0 0 0 0 Alice has no moves, so Bob wins.
4720:{\displaystyle G=\{G_{1},G_{2},\ldots ,G_{k}\}}
4073:. Applying the definition of equivalence with
6199:The Grundy value of a single nim pile of size
4241:-position: for every move made in one copy of
2502:The explicit formula for adding positions is:
884:{\displaystyle {\big \{}*1,\{*1\},*2{\big \}}}
343:(for Bob), we would denote their positions as
6687:
6195:showed that it had the following properties:
4165:of addition) is in the same outcome class as
3601:(which exists for the analogous reason). So
2052:
1973:
1963:
1911:
1901:
1864:
1179:
1100:
1090:
1038:
1028:
991:
955:
903:
876:
839:
8:
6652:Combinatorial Games, Theory and Applications
4846:
4792:
4714:
4669:
2673:{\displaystyle {\boldsymbol {\mathcal {P}}}}
2644:{\displaystyle {\boldsymbol {\mathcal {N}}}}
2600:
2571:
2565:
2526:
2459:
2456:
2444:
2435:
2423:
2417:
2414:
2405:
2402:
2396:
2387:
2384:
2363:
2360:
2348:
2339:
2327:
2315:
2294:
2282:
2273:
2261:
2226:
2217:
2143:
2134:
2047:
2035:
2026:
2014:
2008:
2005:
1996:
1993:
1987:
1978:
1958:
1946:
1937:
1925:
1887:
1878:
1535:
1526:
1450:
1432:
1403:
1394:
1365:
1362:
1174:
1162:
1153:
1141:
1135:
1132:
1123:
1120:
1114:
1105:
1085:
1073:
1064:
1052:
1014:
1005:
941:
929:
920:
908:
862:
853:
794:
776:
702:
693:
647:
638:
568:
559:
482:
479:
443:
440:
383:
380:
374:
371:
2621:Positions in impartial games fall into two
287:At any given point in the game, a player's
53:Learn how and when to remove these messages
6694:
6680:
6672:
1281:referenced in our example game are called
6663:
6590:
6400:
6371:
6345:
6325:
6305:
6273:
6272:
6270:
6247:
6224:
6204:
6170:
6150:
6130:
6093:
6059:
6028:
6004:
5998:
5993:was defined to be different from all the
5978:
5951:
5945:
5922:
5901:
5892:
5865:
5859:
5838:
5829:
5806:
5779:
5773:
5752:
5743:
5718:
5694:
5693:
5691:
5663:
5638:
5614:
5583:
5555:
5532:
5508:
5507:
5505:
5471:
5448:
5423:
5386:
5365:
5364:
5362:
5328:
5294:
5273:
5272:
5270:
5239:
5218:
5217:
5215:
5190:
5165:
5144:
5135:
5115:
5094:
5088:
5057:
5037:
5006:
4982:
4976:
4964:{\displaystyle n_{1},n_{2},\ldots ,n_{k}}
4955:
4936:
4923:
4917:
4893:
4864:
4840:
4818:
4802:
4779:
4758:
4742:
4736:
4708:
4689:
4676:
4661:
4615:
4595:
4567:
4509:
4467:
4446:
4445:
4443:
4411:
4362:
4330:
4309:
4308:
4306:
4269:
4246:
4225:
4224:
4222:
4196:
4170:
4135:
4104:
4078:
4047:
4023:
4022:
4020:
3989:
3958:
3921:
3900:
3899:
3897:
3865:
3844:
3843:
3841:
3821:
3795:
3774:
3773:
3771:
3750:
3749:
3747:
3715:
3694:
3693:
3691:
3665:
3641:
3640:
3638:
3606:
3580:
3554:
3533:
3532:
3530:
3510:
3490:
3470:
3438:
3417:
3416:
3414:
3388:
3365:
3333:
3307:
3275:
3255:
3234:
3233:
3231:
3211:
3166:
3145:
3144:
3142:
3105:
3084:
3083:
3081:
3056:
3055:
3053:
3026:
3004:
2983:
2982:
2980:
2938:
2912:
2889:
2858:
2838:
2807:
2787:
2763:
2762:
2760:
2737:
2716:
2715:
2713:
2690:
2664:
2663:
2661:
2635:
2634:
2632:
2507:
2464:
2463:
2241:
2240:
2231:
2230:
2202:
2201:
2178:
2147:
2146:
2128:
2127:
2113:
2086:
2058:
2057:
2051:
2050:
1972:
1971:
1962:
1961:
1910:
1909:
1900:
1899:
1863:
1862:
1856:
1855:
1846:
1824:
1783:
1758:
1733:
1713:
1693:
1673:
1632:
1607:
1582:
1494:
1468:
1421:
1383:
1360:
1337:
1317:
1294:
1263:
1240:
1217:
1185:
1184:
1178:
1177:
1099:
1098:
1089:
1088:
1037:
1036:
1027:
1026:
990:
989:
983:
982:
980:
954:
953:
902:
901:
899:
875:
874:
838:
837:
835:
812:
774:
747:
724:
691:
668:
636:
613:
586:
557:
530:
500:
477:
438:
348:
328:
308:
183:Learn how and when to remove this message
165:Learn how and when to remove this message
149:, without removing the technical details.
110:Learn how and when to remove this message
6434:Winning Ways for your Mathematical Plays
5001:The first thing we need to note is that
3575:according to their winning strategy for
3485:according to their winning strategy for
2169:To compute the starting position of the
975:Finally, at step 1, Alice's position is
73:This article includes a list of general
6469:
5130:, then the previous player can move to
4042:In the forward direction, suppose that
1668:to get a combined game with six heaps:
6296:of the Grundy values of its summands.
6088:. By transitivity, we conclude that
5083:. If the next player makes a move to
3168:
3006:
2383:
2314:
2260:
2208:
2180:
1826:
147:make it understandable to non-experts
7:
3549:-position), and respond to moves in
2081:, we'll label the starting position
1819:, we'll label its starting position
1541:{\displaystyle *(n+1)=*n\cup \{*n\}}
211:is equivalent to a one-heap game of
6649:Milvang-Jensen, Brit C. A. (2000),
6601:10.17323/1609-4514-2006-6-2-359-388
4767:{\displaystyle G_{i}\approx *n_{i}}
3172:
3111:
2462:
2379:
2366:
2310:
2297:
2256:
2229:
2212:
2197:
2184:
6743:First-player and second-player win
5801:then the previous player moves in
4551:{\displaystyle G'\approx G'+(G+G)}
3107:
2972:
2891:
2656:), or the previous player wins (a
2078:
1848:
769:move would result in the position
284:(a player who cannot move loses).
79:it lacks sufficient corresponding
14:
5032:, by way of the second lemma. If
4399:{\displaystyle G\approx G+(G+G')}
3176:
3115:
3028:
2968:
2370:
2301:
2247:
2216:
2188:
2170:
2115:
2088:
1816:
1665:
392:{\displaystyle (A,B)=(\{\},\{\})}
34:This article has multiple issues.
7761:Theorems in discrete mathematics
6850:Coalition-proof Nash equilibrium
6482:"Über mathematische Kampfspiele"
5210:. After this, the position is a
4264:In the reverse direction, since
3953:As a further step, we show that
3860:-position. Thus, in this case,
2933:is in the same outcome class as
126:
64:
23:
5887:, the previous player moves in
3360:share an outcome class for all
42:or discuss these issues on the
6860:Evolutionarily stable strategy
6366:has the same Grundy value as
6282:{\displaystyle {\mathcal {P}}}
5703:{\displaystyle {\mathcal {P}}}
5517:{\displaystyle {\mathcal {P}}}
5374:{\displaystyle {\mathcal {P}}}
5282:{\displaystyle {\mathcal {P}}}
5227:{\displaystyle {\mathcal {P}}}
4545:
4533:
4497:{\displaystyle G'\approx G'+B}
4455:{\displaystyle {\mathcal {P}}}
4393:
4376:
4318:{\displaystyle {\mathcal {P}}}
4234:{\displaystyle {\mathcal {P}}}
4032:{\displaystyle {\mathcal {P}}}
3909:{\displaystyle {\mathcal {N}}}
3853:{\displaystyle {\mathcal {P}}}
3783:{\displaystyle {\mathcal {P}}}
3759:{\displaystyle {\mathcal {N}}}
3703:{\displaystyle {\mathcal {N}}}
3650:{\displaystyle {\mathcal {P}}}
3542:{\displaystyle {\mathcal {P}}}
3426:{\displaystyle {\mathcal {P}}}
3243:{\displaystyle {\mathcal {P}}}
3154:{\displaystyle {\mathcal {P}}}
3093:{\displaystyle {\mathcal {N}}}
3065:{\displaystyle {\mathcal {N}}}
3041:{\displaystyle \color {red}S'}
3014:{\displaystyle \color {blue}S}
2992:{\displaystyle {\mathcal {P}}}
2772:{\displaystyle {\mathcal {N}}}
2725:{\displaystyle {\mathcal {P}}}
2101:{\displaystyle \color {red}S'}
1834:{\displaystyle \color {blue}S}
1810:
1659:
1511:
1499:
466:
386:
368:
362:
350:
1:
6788:Simultaneous action selection
6458:Indistinguishability quotient
1571:Two games can be combined by
7720:List of games in game theory
6900:Quantal response equilibrium
6890:Perfect Bayesian equilibrium
6825:Bayes correlated equilibrium
6081:{\displaystyle G'\approx *m}
5408:{\displaystyle G'\approx *m}
4350:{\displaystyle G\approx G+A}
3836:to that position is still a
3295:{\displaystyle G\approx A+G}
2833:if, no matter what position
1456:{\displaystyle *2=\{*0,*1\}}
631:. Thus, Bob's position is
201:Sprague–Grundy theorem
7189:Optional prisoner's dilemma
6920:Self-confirming equilibrium
6579:Moscow Mathematical Journal
6487:Tohoku Mathematical Journal
6187:{\displaystyle G\approx *m}
6110:{\displaystyle G\approx *m}
6047:{\displaystyle G\approx G'}
5500:is the null set, clearly a
5313:{\displaystyle G\approx G'}
5025:{\displaystyle G\approx G'}
4881:{\displaystyle G\approx *m}
4634:{\displaystyle G\approx G'}
4066:{\displaystyle G\approx G'}
3977:{\displaystyle G\approx G'}
3505:(which exists by virtue of
2877:{\displaystyle G\approx G'}
1664:We can combine it with our
7779:
7654:Principal variation search
7370:Aumann's agreement theorem
7033:Strategy-stealing argument
6945:Trembling hand equilibrium
6875:Markov perfect equilibrium
6870:Mertens-stable equilibrium
5880:{\displaystyle n_{i}>m}
5794:{\displaystyle n_{i}<m}
1289:. In general, the nimber
7756:Combinatorial game theory
7690:Combinatorial game theory
7349:Princess and monster game
6905:Quasi-perfect equilibrium
6830:Bayesian Nash equilibrium
6417:combinatorial game theory
3790:-position from among the
2900:{\displaystyle \forall H}
1409:{\displaystyle *1=\{*0\}}
807:. We call this position
800:{\displaystyle \{*0,*1\}}
581:. We name this position
197:combinatorial game theory
7705:Evolutionary game theory
7438:Antoine Augustin Cournot
7324:Guess 2/3 of the average
7121:Strictly determined game
6915:Satisfaction equilibrium
6733:Escalation of commitment
4603:{\displaystyle \approx }
4575:{\displaystyle \approx }
1555:ber comes from the game
7710:Glossary of game theory
7309:Stackelberg competition
6935:Strong Nash equilibrium
6526:"Mathematics and games"
5966:{\displaystyle n_{i}=m}
5602:{\displaystyle m'<m}
4910:mex (minimum exclusion)
4610:, we can conclude that
3076:is the player with the
1482:{\displaystyle n\geq 0}
525:leaves Bob in position
94:more precise citations.
7735:Tragedy of the commons
7715:List of game theorists
7695:Confrontation analysis
7405:Sprague–Grundy theorem
6925:Sequential equilibrium
6845:Correlated equilibrium
6409:
6389:
6360:
6334:
6320:has a Grundy value of
6314:
6283:
6256:
6236:
6219:(i.e. of the position
6213:
6188:
6159:
6139:
6111:
6082:
6048:
6014:
5987:
5967:
5934:
5911:
5910:{\displaystyle *n_{i}}
5881:
5848:
5847:{\displaystyle *n_{i}}
5818:
5795:
5762:
5761:{\displaystyle *n_{i}}
5732:
5704:
5680:
5652:
5623:
5603:
5572:
5544:
5518:
5494:
5460:
5437:
5409:
5375:
5351:
5314:
5283:
5259:
5228:
5204:
5179:
5154:
5153:{\displaystyle *n_{i}}
5124:
5104:
5077:
5046:
5026:
4992:
4965:
4902:
4882:
4853:
4768:
4721:
4635:
4604:
4576:
4552:
4498:
4456:
4432:
4400:
4351:
4319:
4295:
4294:{\displaystyle A=G+G'}
4255:
4235:
4211:
4185:
4155:
4124:
4093:
4067:
4033:
4009:
3978:
3936:
3910:
3886:
3854:
3830:
3810:
3784:
3760:
3736:
3704:
3680:
3660:On the other hand, if
3651:
3627:
3595:
3569:
3543:
3519:
3499:
3479:
3465:: respond to moves in
3459:
3427:
3403:
3374:
3354:
3322:
3296:
3264:
3244:
3220:
3192:
3155:
3131:
3094:
3066:
3042:
3015:
2999:-position. Thus, both
2993:
2958:
2927:
2901:
2878:
2847:
2821:
2796:
2773:
2749:
2726:
2702:
2674:
2645:
2607:
2494:
2161:
2102:
2069:
1835:
1797:
1772:
1747:
1722:
1702:
1682:
1646:
1621:
1596:
1542:
1483:
1457:
1410:
1372:
1349:
1326:
1306:
1275:
1252:
1229:
1198:
967:
885:
824:
801:
759:
736:
709:
708:{\displaystyle \{*1\}}
680:
654:
653:{\displaystyle \{*1\}}
625:
598:
575:
574:{\displaystyle \{*0\}}
542:
512:
489:
450:
433:can simply be written
393:
337:
317:
209:normal play convention
7508:Jean-François Mertens
6538:: 6–8. Archived from
6410:
6390:
6361:
6335:
6315:
6284:
6257:
6237:
6214:
6189:
6160:
6140:
6112:
6083:
6049:
6015:
6013:{\displaystyle n_{i}}
5988:
5968:
5935:
5912:
5882:
5849:
5819:
5796:
5763:
5733:
5705:
5681:
5653:
5624:
5604:
5573:
5545:
5519:
5495:
5493:{\displaystyle G'+*m}
5461:
5438:
5410:
5376:
5352:
5350:{\displaystyle G'+*m}
5323:Now let us show that
5315:
5284:
5260:
5229:
5205:
5180:
5155:
5125:
5105:
5103:{\displaystyle G_{i}}
5078:
5047:
5027:
4993:
4991:{\displaystyle n_{i}}
4966:
4903:
4883:
4859:. We will show that
4854:
4769:
4722:
4636:
4605:
4577:
4553:
4499:
4457:
4433:
4431:{\displaystyle B=G+G}
4406:. Similarly, since
4401:
4352:
4320:
4296:
4256:
4236:
4212:
4186:
4156:
4125:
4094:
4068:
4034:
4010:
3979:
3937:
3916:-position, just like
3911:
3887:
3885:{\displaystyle A+G+H}
3855:
3831:
3811:
3785:
3761:
3737:
3735:{\displaystyle A+G+H}
3705:
3681:
3652:
3628:
3626:{\displaystyle A+G+H}
3596:
3570:
3544:
3520:
3500:
3480:
3460:
3458:{\displaystyle A+G+H}
3428:
3404:
3375:
3355:
3353:{\displaystyle A+G+H}
3323:
3297:
3265:
3245:
3221:
3193:
3156:
3132:
3100:-positions. In fact,
3095:
3067:
3043:
3016:
2994:
2959:
2928:
2902:
2879:
2848:
2822:
2797:
2774:
2750:
2727:
2703:
2685:). So, for example,
2675:
2646:
2608:
2495:
2162:
2103:
2070:
1841:, and color it blue:
1836:
1798:
1773:
1748:
1723:
1703:
1683:
1647:
1622:
1597:
1543:
1484:
1458:
1411:
1373:
1350:
1327:
1307:
1276:
1253:
1230:
1199:
968:
886:
825:
802:
760:
737:
710:
681:
655:
626:
599:
576:
543:
513:
490:
451:
394:
338:
318:
282:normal play condition
7637:Search optimizations
7513:Jennifer Tour Chayes
7400:Revelation principle
7395:Purification theorem
7334:Nash bargaining game
7299:Bertrand competition
7284:El Farol Bar problem
7249:Electronic mail game
7214:Lewis signaling game
6758:Hierarchy of beliefs
6440:On Numbers and Games
6399:
6388:{\displaystyle *m+H}
6370:
6344:
6324:
6304:
6269:
6246:
6223:
6203:
6169:
6149:
6129:
6092:
6058:
6027:
6023:In summary, we have
5997:
5977:
5944:
5921:
5891:
5858:
5828:
5805:
5772:
5742:
5717:
5690:
5662:
5637:
5613:
5582:
5554:
5531:
5504:
5470:
5447:
5422:
5385:
5361:
5327:
5293:
5269:
5258:{\displaystyle G+G'}
5238:
5214:
5189:
5164:
5134:
5114:
5087:
5076:{\displaystyle G+G'}
5056:
5036:
5005:
4975:
4916:
4892:
4863:
4778:
4735:
4729:induction hypothesis
4660:
4656:Consider a position
4651:structural induction
4614:
4594:
4584:equivalence relation
4566:
4508:
4466:
4442:
4410:
4361:
4329:
4305:
4268:
4245:
4221:
4195:
4169:
4154:{\displaystyle G+G'}
4134:
4123:{\displaystyle G'+G}
4103:
4077:
4046:
4019:
4008:{\displaystyle G+G'}
3988:
3957:
3920:
3896:
3864:
3840:
3820:
3794:
3770:
3746:
3714:
3690:
3664:
3637:
3605:
3579:
3553:
3529:
3509:
3489:
3469:
3437:
3413:
3387:
3364:
3332:
3306:
3274:
3254:
3230:
3210:
3165:
3141:
3104:
3080:
3052:
3025:
3003:
2979:
2957:{\displaystyle G'+H}
2937:
2911:
2888:
2857:
2837:
2806:
2786:
2759:
2736:
2712:
2689:
2660:
2631:
2506:
2177:
2112:
2085:
1845:
1823:
1782:
1757:
1732:
1712:
1692:
1672:
1631:
1606:
1581:
1493:
1467:
1420:
1382:
1371:{\displaystyle \{\}}
1359:
1336:
1316:
1293:
1262:
1239:
1216:
979:
898:
834:
811:
773:
746:
723:
719:moves would then be
690:
667:
635:
612:
585:
556:
529:
499:
488:{\displaystyle \{\}}
476:
449:{\displaystyle \{\}}
437:
347:
327:
307:
7685:Bounded rationality
7304:Cournot competition
7254:Rock paper scissors
7229:Battle of the sexes
7219:Volunteer's dilemma
7091:Perfect information
7018:Dominant strategies
6855:Epsilon-equilibrium
6738:Extensive-form game
6359:{\displaystyle G+H}
5679:{\displaystyle *m'}
5571:{\displaystyle *m'}
4210:{\displaystyle G+G}
4184:{\displaystyle G+G}
4130:(which is equal to
4092:{\displaystyle H=G}
3935:{\displaystyle G+H}
3809:{\displaystyle G+H}
3679:{\displaystyle G+H}
3594:{\displaystyle G+H}
3568:{\displaystyle G+H}
3402:{\displaystyle G+H}
3321:{\displaystyle G+H}
2926:{\displaystyle G+H}
2079:second example game
274:perfect information
7664:Paranoid algorithm
7644:Alpha–beta pruning
7523:John Maynard Smith
7354:Rendezvous problem
7194:Traveler's dilemma
7184:Gift-exchange game
7179:Prisoner's dilemma
7096:Large Poisson game
7063:Bargaining problem
6968:Backward induction
6940:Subgame perfection
6895:Proper equilibrium
6429:John Horton Conway
6405:
6385:
6356:
6330:
6310:
6279:
6252:
6235:{\displaystyle *m}
6232:
6209:
6184:
6155:
6135:
6107:
6078:
6044:
6010:
5983:
5963:
5933:{\displaystyle *m}
5930:
5907:
5877:
5844:
5817:{\displaystyle *m}
5814:
5791:
5758:
5731:{\displaystyle G'}
5728:
5700:
5676:
5651:{\displaystyle G'}
5648:
5619:
5599:
5568:
5543:{\displaystyle *m}
5540:
5514:
5490:
5459:{\displaystyle *m}
5456:
5436:{\displaystyle G'}
5433:
5405:
5371:
5347:
5310:
5279:
5255:
5224:
5203:{\displaystyle G'}
5200:
5178:{\displaystyle G'}
5175:
5150:
5120:
5100:
5073:
5042:
5022:
4988:
4961:
4898:
4878:
4849:
4764:
4717:
4631:
4600:
4572:
4548:
4494:
4452:
4428:
4396:
4347:
4315:
4291:
4251:
4231:
4207:
4181:
4151:
4120:
4089:
4063:
4029:
4005:
3974:
3932:
3906:
3882:
3850:
3826:
3806:
3780:
3756:
3732:
3700:
3676:
3647:
3623:
3591:
3565:
3539:
3515:
3495:
3475:
3455:
3423:
3399:
3370:
3350:
3318:
3292:
3270:, the equivalence
3260:
3240:
3216:
3188:
3187:
3186:
3185:
3151:
3127:
3126:
3125:
3124:
3090:
3062:
3038:
3037:
3011:
3010:
2989:
2954:
2923:
2897:
2874:
2843:
2820:{\displaystyle G'}
2817:
2792:
2769:
2748:{\displaystyle *1}
2745:
2722:
2701:{\displaystyle *0}
2698:
2670:
2641:
2603:
2490:
2489:
2488:
2487:
2486:
2485:
2484:
2483:
2482:
2481:
2480:
2479:
2478:
2477:
2476:
2475:
2474:
2473:
2472:
2471:
2470:
2157:
2156:
2108:and color it red:
2098:
2097:
2065:
2064:
1831:
1830:
1817:first example game
1796:{\displaystyle C'}
1793:
1771:{\displaystyle B'}
1768:
1746:{\displaystyle A'}
1743:
1718:
1698:
1678:
1645:{\displaystyle C'}
1642:
1620:{\displaystyle B'}
1617:
1595:{\displaystyle A'}
1592:
1538:
1479:
1453:
1406:
1368:
1348:{\displaystyle *0}
1345:
1322:
1305:{\displaystyle *n}
1302:
1274:{\displaystyle *2}
1271:
1251:{\displaystyle *1}
1248:
1228:{\displaystyle *0}
1225:
1212:The special names
1194:
963:
881:
823:{\displaystyle *2}
820:
797:
758:{\displaystyle *1}
755:
735:{\displaystyle *0}
732:
705:
679:{\displaystyle *1}
676:
650:
624:{\displaystyle *1}
621:
597:{\displaystyle *1}
594:
571:
541:{\displaystyle *0}
538:
511:{\displaystyle *0}
508:
485:
446:
389:
333:
313:
203:states that every
7743:
7742:
7649:Aspiration window
7618:Suzanne Scotchmer
7573:Oskar Morgenstern
7468:Donald B. Gillies
7410:Zermelo's theorem
7339:Induction puzzles
7294:Fair cake-cutting
7269:Public goods game
7199:Coordination game
7073:Intransitive game
7003:Forward induction
6885:Pareto efficiency
6865:Gibbs equilibrium
6835:Berge equilibrium
6783:Simultaneous game
6544:Reprinted, 1964,
6408:{\displaystyle H}
6333:{\displaystyle m}
6313:{\displaystyle G}
6255:{\displaystyle m}
6212:{\displaystyle m}
6158:{\displaystyle m}
6138:{\displaystyle G}
5986:{\displaystyle m}
5622:{\displaystyle m}
5466:are empty. Then
5123:{\displaystyle G}
5045:{\displaystyle k}
4901:{\displaystyle m}
4254:{\displaystyle G}
3829:{\displaystyle A}
3518:{\displaystyle A}
3498:{\displaystyle A}
3478:{\displaystyle A}
3373:{\displaystyle H}
3263:{\displaystyle A}
3219:{\displaystyle G}
2846:{\displaystyle H}
2795:{\displaystyle G}
2732:-position, while
1721:{\displaystyle C}
1701:{\displaystyle B}
1681:{\displaystyle A}
1325:{\displaystyle n}
336:{\displaystyle B}
316:{\displaystyle A}
193:
192:
185:
175:
174:
167:
120:
119:
112:
57:
7768:
7730:Topological game
7725:No-win situation
7623:Thomas Schelling
7603:Robert B. Wilson
7563:Merrill M. Flood
7533:John von Neumann
7443:Ariel Rubinstein
7428:Albert W. Tucker
7279:War of attrition
7239:Matching pennies
6880:Nash equilibrium
6803:Mechanism design
6768:Normal-form game
6723:Cooperative game
6696:
6689:
6682:
6673:
6668:
6667:
6657:
6613:
6612:
6594:
6574:
6568:
6567:
6555:
6549:
6543:
6518:
6512:
6511:
6474:
6414:
6412:
6411:
6406:
6394:
6392:
6391:
6386:
6365:
6363:
6362:
6357:
6339:
6337:
6336:
6331:
6319:
6317:
6316:
6311:
6288:
6286:
6285:
6280:
6278:
6277:
6261:
6259:
6258:
6253:
6241:
6239:
6238:
6233:
6218:
6216:
6215:
6210:
6193:
6191:
6190:
6185:
6164:
6162:
6161:
6156:
6144:
6142:
6141:
6136:
6116:
6114:
6113:
6108:
6087:
6085:
6084:
6079:
6068:
6053:
6051:
6050:
6045:
6043:
6019:
6017:
6016:
6011:
6009:
6008:
5992:
5990:
5989:
5984:
5972:
5970:
5969:
5964:
5956:
5955:
5939:
5937:
5936:
5931:
5916:
5914:
5913:
5908:
5906:
5905:
5886:
5884:
5883:
5878:
5870:
5869:
5854:; otherwise, if
5853:
5851:
5850:
5845:
5843:
5842:
5823:
5821:
5820:
5815:
5800:
5798:
5797:
5792:
5784:
5783:
5767:
5765:
5764:
5759:
5757:
5756:
5737:
5735:
5734:
5729:
5727:
5709:
5707:
5706:
5701:
5699:
5698:
5685:
5683:
5682:
5677:
5675:
5657:
5655:
5654:
5649:
5647:
5628:
5626:
5625:
5620:
5608:
5606:
5605:
5600:
5592:
5577:
5575:
5574:
5569:
5567:
5549:
5547:
5546:
5541:
5523:
5521:
5520:
5515:
5513:
5512:
5499:
5497:
5496:
5491:
5480:
5465:
5463:
5462:
5457:
5442:
5440:
5439:
5434:
5432:
5414:
5412:
5411:
5406:
5395:
5380:
5378:
5377:
5372:
5370:
5369:
5356:
5354:
5353:
5348:
5337:
5319:
5317:
5316:
5311:
5309:
5288:
5286:
5285:
5280:
5278:
5277:
5264:
5262:
5261:
5256:
5254:
5233:
5231:
5230:
5225:
5223:
5222:
5209:
5207:
5206:
5201:
5199:
5184:
5182:
5181:
5176:
5174:
5159:
5157:
5156:
5151:
5149:
5148:
5129:
5127:
5126:
5121:
5109:
5107:
5106:
5101:
5099:
5098:
5082:
5080:
5079:
5074:
5072:
5051:
5049:
5048:
5043:
5031:
5029:
5028:
5023:
5021:
4997:
4995:
4994:
4989:
4987:
4986:
4970:
4968:
4967:
4962:
4960:
4959:
4941:
4940:
4928:
4927:
4907:
4905:
4904:
4899:
4887:
4885:
4884:
4879:
4858:
4856:
4855:
4850:
4845:
4844:
4823:
4822:
4807:
4806:
4788:
4773:
4771:
4770:
4765:
4763:
4762:
4747:
4746:
4726:
4724:
4723:
4718:
4713:
4712:
4694:
4693:
4681:
4680:
4640:
4638:
4637:
4632:
4630:
4609:
4607:
4606:
4601:
4581:
4579:
4578:
4573:
4557:
4555:
4554:
4549:
4529:
4518:
4503:
4501:
4500:
4495:
4487:
4476:
4461:
4459:
4458:
4453:
4451:
4450:
4437:
4435:
4434:
4429:
4405:
4403:
4402:
4397:
4392:
4356:
4354:
4353:
4348:
4324:
4322:
4321:
4316:
4314:
4313:
4300:
4298:
4297:
4292:
4290:
4260:
4258:
4257:
4252:
4240:
4238:
4237:
4232:
4230:
4229:
4216:
4214:
4213:
4208:
4190:
4188:
4187:
4182:
4160:
4158:
4157:
4152:
4150:
4129:
4127:
4126:
4121:
4113:
4098:
4096:
4095:
4090:
4072:
4070:
4069:
4064:
4062:
4038:
4036:
4035:
4030:
4028:
4027:
4014:
4012:
4011:
4006:
4004:
3983:
3981:
3980:
3975:
3973:
3941:
3939:
3938:
3933:
3915:
3913:
3912:
3907:
3905:
3904:
3891:
3889:
3888:
3883:
3859:
3857:
3856:
3851:
3849:
3848:
3835:
3833:
3832:
3827:
3815:
3813:
3812:
3807:
3789:
3787:
3786:
3781:
3779:
3778:
3765:
3763:
3762:
3757:
3755:
3754:
3741:
3739:
3738:
3733:
3710:-position, then
3709:
3707:
3706:
3701:
3699:
3698:
3685:
3683:
3682:
3677:
3656:
3654:
3653:
3648:
3646:
3645:
3632:
3630:
3629:
3624:
3600:
3598:
3597:
3592:
3574:
3572:
3571:
3566:
3548:
3546:
3545:
3540:
3538:
3537:
3524:
3522:
3521:
3516:
3504:
3502:
3501:
3496:
3484:
3482:
3481:
3476:
3464:
3462:
3461:
3456:
3432:
3430:
3429:
3424:
3422:
3421:
3408:
3406:
3405:
3400:
3379:
3377:
3376:
3371:
3359:
3357:
3356:
3351:
3327:
3325:
3324:
3319:
3301:
3299:
3298:
3293:
3269:
3267:
3266:
3261:
3249:
3247:
3246:
3241:
3239:
3238:
3225:
3223:
3222:
3217:
3197:
3195:
3194:
3189:
3184:
3160:
3158:
3157:
3152:
3150:
3149:
3136:
3134:
3133:
3128:
3123:
3099:
3097:
3096:
3091:
3089:
3088:
3071:
3069:
3068:
3063:
3061:
3060:
3047:
3045:
3044:
3039:
3036:
3020:
3018:
3017:
3012:
2998:
2996:
2995:
2990:
2988:
2987:
2963:
2961:
2960:
2955:
2947:
2932:
2930:
2929:
2924:
2906:
2904:
2903:
2898:
2883:
2881:
2880:
2875:
2873:
2852:
2850:
2849:
2844:
2826:
2824:
2823:
2818:
2816:
2801:
2799:
2798:
2793:
2778:
2776:
2775:
2770:
2768:
2767:
2754:
2752:
2751:
2746:
2731:
2729:
2728:
2723:
2721:
2720:
2707:
2705:
2704:
2699:
2679:
2677:
2676:
2671:
2669:
2668:
2650:
2648:
2647:
2642:
2640:
2639:
2612:
2610:
2609:
2604:
2587:
2564:
2553:
2542:
2522:
2499:
2497:
2496:
2491:
2469:
2468:
2378:
2309:
2255:
2246:
2245:
2236:
2235:
2207:
2206:
2196:
2166:
2164:
2163:
2158:
2152:
2151:
2133:
2132:
2123:
2107:
2105:
2104:
2099:
2096:
2074:
2072:
2071:
2066:
2063:
2062:
2056:
2055:
1977:
1976:
1967:
1966:
1915:
1914:
1905:
1904:
1868:
1867:
1861:
1860:
1840:
1838:
1837:
1832:
1802:
1800:
1799:
1794:
1792:
1777:
1775:
1774:
1769:
1767:
1752:
1750:
1749:
1744:
1742:
1727:
1725:
1724:
1719:
1707:
1705:
1704:
1699:
1687:
1685:
1684:
1679:
1651:
1649:
1648:
1643:
1641:
1626:
1624:
1623:
1618:
1616:
1601:
1599:
1598:
1593:
1591:
1547:
1545:
1544:
1539:
1488:
1486:
1485:
1480:
1462:
1460:
1459:
1454:
1415:
1413:
1412:
1407:
1377:
1375:
1374:
1369:
1354:
1352:
1351:
1346:
1331:
1329:
1328:
1323:
1311:
1309:
1308:
1303:
1280:
1278:
1277:
1272:
1257:
1255:
1254:
1249:
1234:
1232:
1231:
1226:
1203:
1201:
1200:
1195:
1190:
1189:
1183:
1182:
1104:
1103:
1094:
1093:
1042:
1041:
1032:
1031:
995:
994:
988:
987:
972:
970:
969:
964:
959:
958:
907:
906:
890:
888:
887:
882:
880:
879:
843:
842:
829:
827:
826:
821:
806:
804:
803:
798:
764:
762:
761:
756:
741:
739:
738:
733:
714:
712:
711:
706:
685:
683:
682:
677:
659:
657:
656:
651:
630:
628:
627:
622:
603:
601:
600:
595:
580:
578:
577:
572:
547:
545:
544:
539:
517:
515:
514:
509:
494:
492:
491:
486:
463:Example Nim Game
455:
453:
452:
447:
398:
396:
395:
390:
342:
340:
339:
334:
323:(for Alice) and
322:
320:
319:
314:
278:ending condition
268:is a two-player
188:
181:
170:
163:
159:
156:
150:
130:
129:
122:
115:
108:
104:
101:
95:
90:this article by
81:inline citations
68:
67:
60:
49:
27:
26:
19:
7778:
7777:
7771:
7770:
7769:
7767:
7766:
7765:
7746:
7745:
7744:
7739:
7673:
7659:max^n algorithm
7632:
7628:William Vickrey
7588:Reinhard Selten
7543:Kenneth Binmore
7458:David K. Levine
7453:Daniel Kahneman
7420:
7414:
7390:Negamax theorem
7380:Minimax theorem
7358:
7319:Diner's dilemma
7174:All-pay auction
7140:
7126:Stochastic game
7078:Mean-field game
7049:
7042:
7013:Markov strategy
6949:
6815:
6807:
6778:Sequential game
6763:Information set
6748:Game complexity
6718:Congestion game
6706:
6700:
6655:
6648:
6640:The Game of Nim
6622:
6617:
6616:
6592:math.CO/0410026
6576:
6575:
6571:
6557:
6556:
6552:
6520:
6519:
6515:
6476:
6475:
6471:
6466:
6449:
6425:Elwyn Berlekamp
6397:
6396:
6368:
6367:
6342:
6341:
6322:
6321:
6302:
6301:
6267:
6266:
6244:
6243:
6221:
6220:
6201:
6200:
6167:
6166:
6147:
6146:
6127:
6126:
6123:
6090:
6089:
6061:
6056:
6055:
6036:
6025:
6024:
6000:
5995:
5994:
5975:
5974:
5947:
5942:
5941:
5919:
5918:
5897:
5889:
5888:
5861:
5856:
5855:
5834:
5826:
5825:
5803:
5802:
5775:
5770:
5769:
5748:
5740:
5739:
5720:
5715:
5714:
5688:
5687:
5668:
5660:
5659:
5640:
5635:
5634:
5611:
5610:
5585:
5580:
5579:
5560:
5552:
5551:
5529:
5528:
5502:
5501:
5473:
5468:
5467:
5445:
5444:
5425:
5420:
5419:
5388:
5383:
5382:
5359:
5358:
5330:
5325:
5324:
5302:
5291:
5290:
5267:
5266:
5247:
5236:
5235:
5212:
5211:
5192:
5187:
5186:
5167:
5162:
5161:
5140:
5132:
5131:
5112:
5111:
5090:
5085:
5084:
5065:
5054:
5053:
5034:
5033:
5014:
5003:
5002:
4978:
4973:
4972:
4951:
4932:
4919:
4914:
4913:
4912:of the numbers
4890:
4889:
4861:
4860:
4836:
4814:
4798:
4781:
4776:
4775:
4754:
4738:
4733:
4732:
4704:
4685:
4672:
4658:
4657:
4647:
4623:
4612:
4611:
4592:
4591:
4564:
4563:
4522:
4511:
4506:
4505:
4480:
4469:
4464:
4463:
4440:
4439:
4408:
4407:
4385:
4359:
4358:
4327:
4326:
4303:
4302:
4283:
4266:
4265:
4243:
4242:
4219:
4218:
4193:
4192:
4167:
4166:
4143:
4132:
4131:
4106:
4101:
4100:
4099:, we find that
4075:
4074:
4055:
4044:
4043:
4017:
4016:
3997:
3986:
3985:
3984:if and only if
3966:
3955:
3954:
3951:
3918:
3917:
3894:
3893:
3862:
3861:
3838:
3837:
3818:
3817:
3792:
3791:
3768:
3767:
3744:
3743:
3712:
3711:
3688:
3687:
3662:
3661:
3635:
3634:
3633:must also be a
3603:
3602:
3577:
3576:
3551:
3550:
3527:
3526:
3507:
3506:
3487:
3486:
3467:
3466:
3435:
3434:
3411:
3410:
3385:
3384:
3362:
3361:
3330:
3329:
3304:
3303:
3272:
3271:
3252:
3251:
3228:
3227:
3208:
3207:
3204:
3177:
3163:
3162:
3139:
3138:
3116:
3102:
3101:
3078:
3077:
3050:
3049:
3029:
3023:
3022:
3001:
3000:
2977:
2976:
2940:
2935:
2934:
2909:
2908:
2886:
2885:
2884:if and only if
2866:
2855:
2854:
2835:
2834:
2809:
2804:
2803:
2784:
2783:
2757:
2756:
2734:
2733:
2710:
2709:
2687:
2686:
2658:
2657:
2629:
2628:
2624:outcome classes
2619:
2580:
2557:
2546:
2535:
2515:
2504:
2503:
2371:
2302:
2248:
2189:
2175:
2174:
2116:
2110:
2109:
2089:
2083:
2082:
1843:
1842:
1821:
1820:
1813:
1809:
1785:
1780:
1779:
1760:
1755:
1754:
1735:
1730:
1729:
1710:
1709:
1690:
1689:
1670:
1669:
1662:
1658:
1634:
1629:
1628:
1609:
1604:
1603:
1584:
1579:
1578:
1569:
1567:Combining Games
1551:While the word
1491:
1490:
1465:
1464:
1418:
1417:
1380:
1379:
1357:
1356:
1334:
1333:
1314:
1313:
1291:
1290:
1260:
1259:
1237:
1236:
1214:
1213:
1210:
977:
976:
896:
895:
832:
831:
809:
808:
771:
770:
744:
743:
721:
720:
688:
687:
665:
664:
633:
632:
610:
609:
583:
582:
554:
553:
527:
526:
497:
496:
474:
473:
469:
465:
435:
434:
345:
344:
325:
324:
305:
304:
276:satisfying the
270:sequential game
260:
189:
178:
177:
176:
171:
160:
154:
151:
143:help improve it
140:
131:
127:
116:
105:
99:
96:
86:Please help to
85:
69:
65:
28:
24:
17:
12:
11:
5:
7776:
7775:
7772:
7764:
7763:
7758:
7748:
7747:
7741:
7740:
7738:
7737:
7732:
7727:
7722:
7717:
7712:
7707:
7702:
7697:
7692:
7687:
7681:
7679:
7675:
7674:
7672:
7671:
7666:
7661:
7656:
7651:
7646:
7640:
7638:
7634:
7633:
7631:
7630:
7625:
7620:
7615:
7610:
7605:
7600:
7595:
7593:Robert Axelrod
7590:
7585:
7580:
7575:
7570:
7568:Olga Bondareva
7565:
7560:
7558:Melvin Dresher
7555:
7550:
7548:Leonid Hurwicz
7545:
7540:
7535:
7530:
7525:
7520:
7515:
7510:
7505:
7500:
7495:
7490:
7485:
7483:Harold W. Kuhn
7480:
7475:
7473:Drew Fudenberg
7470:
7465:
7463:David M. Kreps
7460:
7455:
7450:
7448:Claude Shannon
7445:
7440:
7435:
7430:
7424:
7422:
7416:
7415:
7413:
7412:
7407:
7402:
7397:
7392:
7387:
7385:Nash's theorem
7382:
7377:
7372:
7366:
7364:
7360:
7359:
7357:
7356:
7351:
7346:
7341:
7336:
7331:
7326:
7321:
7316:
7311:
7306:
7301:
7296:
7291:
7286:
7281:
7276:
7271:
7266:
7261:
7256:
7251:
7246:
7244:Ultimatum game
7241:
7236:
7231:
7226:
7224:Dollar auction
7221:
7216:
7211:
7209:Centipede game
7206:
7201:
7196:
7191:
7186:
7181:
7176:
7171:
7166:
7164:Infinite chess
7161:
7156:
7150:
7148:
7142:
7141:
7139:
7138:
7133:
7131:Symmetric game
7128:
7123:
7118:
7116:Signaling game
7113:
7111:Screening game
7108:
7103:
7101:Potential game
7098:
7093:
7088:
7080:
7075:
7070:
7065:
7060:
7054:
7052:
7044:
7043:
7041:
7040:
7035:
7030:
7028:Mixed strategy
7025:
7020:
7015:
7010:
7005:
7000:
6995:
6990:
6985:
6980:
6975:
6970:
6965:
6959:
6957:
6951:
6950:
6948:
6947:
6942:
6937:
6932:
6927:
6922:
6917:
6912:
6910:Risk dominance
6907:
6902:
6897:
6892:
6887:
6882:
6877:
6872:
6867:
6862:
6857:
6852:
6847:
6842:
6837:
6832:
6827:
6821:
6819:
6809:
6808:
6806:
6805:
6800:
6795:
6790:
6785:
6780:
6775:
6770:
6765:
6760:
6755:
6753:Graphical game
6750:
6745:
6740:
6735:
6730:
6725:
6720:
6714:
6712:
6708:
6707:
6701:
6699:
6698:
6691:
6684:
6676:
6670:
6669:
6646:
6637:
6632:
6621:
6620:External links
6618:
6615:
6614:
6585:(2): 359–388.
6569:
6550:
6542:on 2007-09-27.
6513:
6478:Sprague, R. P.
6468:
6467:
6465:
6462:
6461:
6460:
6455:
6448:
6445:
6404:
6384:
6381:
6378:
6375:
6355:
6352:
6349:
6329:
6309:
6298:
6297:
6290:
6276:
6263:
6251:
6231:
6228:
6208:
6183:
6180:
6177:
6174:
6154:
6134:
6122:
6119:
6117:, as desired.
6106:
6103:
6100:
6097:
6077:
6074:
6071:
6067:
6064:
6042:
6039:
6035:
6032:
6007:
6003:
5982:
5962:
5959:
5954:
5950:
5929:
5926:
5904:
5900:
5896:
5876:
5873:
5868:
5864:
5841:
5837:
5833:
5813:
5810:
5790:
5787:
5782:
5778:
5755:
5751:
5747:
5738:to the option
5726:
5723:
5697:
5674:
5671:
5667:
5646:
5643:
5618:
5598:
5595:
5591:
5588:
5566:
5563:
5559:
5550:to the option
5539:
5536:
5511:
5489:
5486:
5483:
5479:
5476:
5455:
5452:
5431:
5428:
5404:
5401:
5398:
5394:
5391:
5368:
5346:
5343:
5340:
5336:
5333:
5308:
5305:
5301:
5298:
5276:
5253:
5250:
5246:
5243:
5221:
5198:
5195:
5173:
5170:
5147:
5143:
5139:
5119:
5097:
5093:
5071:
5068:
5064:
5061:
5041:
5020:
5017:
5013:
5010:
4985:
4981:
4958:
4954:
4950:
4947:
4944:
4939:
4935:
4931:
4926:
4922:
4897:
4877:
4874:
4871:
4868:
4848:
4843:
4839:
4835:
4832:
4829:
4826:
4821:
4817:
4813:
4810:
4805:
4801:
4797:
4794:
4791:
4787:
4784:
4761:
4757:
4753:
4750:
4745:
4741:
4716:
4711:
4707:
4703:
4700:
4697:
4692:
4688:
4684:
4679:
4675:
4671:
4668:
4665:
4646:
4643:
4629:
4626:
4622:
4619:
4599:
4571:
4547:
4544:
4541:
4538:
4535:
4532:
4528:
4525:
4521:
4517:
4514:
4493:
4490:
4486:
4483:
4479:
4475:
4472:
4449:
4427:
4424:
4421:
4418:
4415:
4395:
4391:
4388:
4384:
4381:
4378:
4375:
4372:
4369:
4366:
4346:
4343:
4340:
4337:
4334:
4312:
4289:
4286:
4282:
4279:
4276:
4273:
4250:
4228:
4206:
4203:
4200:
4180:
4177:
4174:
4149:
4146:
4142:
4139:
4119:
4116:
4112:
4109:
4088:
4085:
4082:
4061:
4058:
4054:
4051:
4026:
4003:
4000:
3996:
3993:
3972:
3969:
3965:
3962:
3950:
3947:
3931:
3928:
3925:
3903:
3881:
3878:
3875:
3872:
3869:
3847:
3825:
3805:
3802:
3799:
3777:
3753:
3731:
3728:
3725:
3722:
3719:
3697:
3675:
3672:
3669:
3644:
3622:
3619:
3616:
3613:
3610:
3590:
3587:
3584:
3564:
3561:
3558:
3536:
3514:
3494:
3474:
3454:
3451:
3448:
3445:
3442:
3420:
3398:
3395:
3392:
3369:
3349:
3346:
3343:
3340:
3337:
3317:
3314:
3311:
3291:
3288:
3285:
3282:
3279:
3259:
3237:
3215:
3203:
3200:
3183:
3180:
3175:
3171:
3148:
3122:
3119:
3114:
3110:
3087:
3059:
3035:
3032:
3009:
2986:
2953:
2950:
2946:
2943:
2922:
2919:
2916:
2896:
2893:
2872:
2869:
2865:
2862:
2842:
2815:
2812:
2791:
2782:Two positions
2766:
2744:
2741:
2719:
2697:
2694:
2667:
2638:
2618:
2615:
2602:
2599:
2596:
2593:
2590:
2586:
2583:
2579:
2576:
2573:
2570:
2567:
2563:
2560:
2556:
2552:
2549:
2545:
2541:
2538:
2534:
2531:
2528:
2525:
2521:
2518:
2514:
2511:
2467:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2382:
2377:
2374:
2369:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2320:
2317:
2313:
2308:
2305:
2300:
2296:
2293:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2266:
2263:
2259:
2254:
2251:
2244:
2239:
2234:
2228:
2225:
2222:
2219:
2215:
2211:
2205:
2200:
2195:
2192:
2187:
2183:
2155:
2150:
2145:
2142:
2139:
2136:
2131:
2126:
2122:
2119:
2095:
2092:
2061:
2054:
2049:
2046:
2043:
2040:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1975:
1970:
1965:
1960:
1957:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1921:
1918:
1913:
1908:
1903:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1866:
1859:
1854:
1851:
1829:
1808:
1805:
1791:
1788:
1766:
1763:
1741:
1738:
1717:
1697:
1677:
1657:
1656:Example Game 2
1654:
1640:
1637:
1615:
1612:
1590:
1587:
1568:
1565:
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1478:
1475:
1472:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1405:
1402:
1399:
1396:
1393:
1390:
1387:
1367:
1364:
1344:
1341:
1321:
1301:
1298:
1270:
1267:
1247:
1244:
1224:
1221:
1209:
1206:
1205:
1204:
1193:
1188:
1181:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1102:
1097:
1092:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1040:
1035:
1030:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
993:
986:
973:
962:
957:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
905:
892:
878:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
841:
819:
816:
796:
793:
790:
787:
784:
781:
778:
754:
751:
731:
728:
704:
701:
698:
695:
675:
672:
661:
649:
646:
643:
640:
620:
617:
605:
593:
590:
570:
567:
564:
561:
537:
534:
519:
507:
504:
484:
481:
464:
461:
445:
442:
406:impartial game
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
332:
312:
293:is the set of
259:
256:
221:ordinal number
217:natural number
205:impartial game
191:
190:
173:
172:
134:
132:
125:
118:
117:
72:
70:
63:
58:
32:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
7774:
7773:
7762:
7759:
7757:
7754:
7753:
7751:
7736:
7733:
7731:
7728:
7726:
7723:
7721:
7718:
7716:
7713:
7711:
7708:
7706:
7703:
7701:
7698:
7696:
7693:
7691:
7688:
7686:
7683:
7682:
7680:
7678:Miscellaneous
7676:
7670:
7667:
7665:
7662:
7660:
7657:
7655:
7652:
7650:
7647:
7645:
7642:
7641:
7639:
7635:
7629:
7626:
7624:
7621:
7619:
7616:
7614:
7613:Samuel Bowles
7611:
7609:
7608:Roger Myerson
7606:
7604:
7601:
7599:
7598:Robert Aumann
7596:
7594:
7591:
7589:
7586:
7584:
7581:
7579:
7576:
7574:
7571:
7569:
7566:
7564:
7561:
7559:
7556:
7554:
7553:Lloyd Shapley
7551:
7549:
7546:
7544:
7541:
7539:
7538:Kenneth Arrow
7536:
7534:
7531:
7529:
7526:
7524:
7521:
7519:
7518:John Harsanyi
7516:
7514:
7511:
7509:
7506:
7504:
7501:
7499:
7496:
7494:
7491:
7489:
7488:Herbert Simon
7486:
7484:
7481:
7479:
7476:
7474:
7471:
7469:
7466:
7464:
7461:
7459:
7456:
7454:
7451:
7449:
7446:
7444:
7441:
7439:
7436:
7434:
7431:
7429:
7426:
7425:
7423:
7417:
7411:
7408:
7406:
7403:
7401:
7398:
7396:
7393:
7391:
7388:
7386:
7383:
7381:
7378:
7376:
7373:
7371:
7368:
7367:
7365:
7361:
7355:
7352:
7350:
7347:
7345:
7342:
7340:
7337:
7335:
7332:
7330:
7327:
7325:
7322:
7320:
7317:
7315:
7312:
7310:
7307:
7305:
7302:
7300:
7297:
7295:
7292:
7290:
7289:Fair division
7287:
7285:
7282:
7280:
7277:
7275:
7272:
7270:
7267:
7265:
7264:Dictator game
7262:
7260:
7257:
7255:
7252:
7250:
7247:
7245:
7242:
7240:
7237:
7235:
7232:
7230:
7227:
7225:
7222:
7220:
7217:
7215:
7212:
7210:
7207:
7205:
7202:
7200:
7197:
7195:
7192:
7190:
7187:
7185:
7182:
7180:
7177:
7175:
7172:
7170:
7167:
7165:
7162:
7160:
7157:
7155:
7152:
7151:
7149:
7147:
7143:
7137:
7136:Zero-sum game
7134:
7132:
7129:
7127:
7124:
7122:
7119:
7117:
7114:
7112:
7109:
7107:
7106:Repeated game
7104:
7102:
7099:
7097:
7094:
7092:
7089:
7087:
7085:
7081:
7079:
7076:
7074:
7071:
7069:
7066:
7064:
7061:
7059:
7056:
7055:
7053:
7051:
7045:
7039:
7036:
7034:
7031:
7029:
7026:
7024:
7023:Pure strategy
7021:
7019:
7016:
7014:
7011:
7009:
7006:
7004:
7001:
6999:
6996:
6994:
6991:
6989:
6988:De-escalation
6986:
6984:
6981:
6979:
6976:
6974:
6971:
6969:
6966:
6964:
6961:
6960:
6958:
6956:
6952:
6946:
6943:
6941:
6938:
6936:
6933:
6931:
6930:Shapley value
6928:
6926:
6923:
6921:
6918:
6916:
6913:
6911:
6908:
6906:
6903:
6901:
6898:
6896:
6893:
6891:
6888:
6886:
6883:
6881:
6878:
6876:
6873:
6871:
6868:
6866:
6863:
6861:
6858:
6856:
6853:
6851:
6848:
6846:
6843:
6841:
6838:
6836:
6833:
6831:
6828:
6826:
6823:
6822:
6820:
6818:
6814:
6810:
6804:
6801:
6799:
6798:Succinct game
6796:
6794:
6791:
6789:
6786:
6784:
6781:
6779:
6776:
6774:
6771:
6769:
6766:
6764:
6761:
6759:
6756:
6754:
6751:
6749:
6746:
6744:
6741:
6739:
6736:
6734:
6731:
6729:
6726:
6724:
6721:
6719:
6716:
6715:
6713:
6709:
6705:
6697:
6692:
6690:
6685:
6683:
6678:
6677:
6674:
6666:
6665:10.1.1.89.805
6661:
6654:
6653:
6647:
6645:
6641:
6638:
6636:
6633:
6631:
6627:
6626:Grundy's game
6624:
6623:
6619:
6610:
6606:
6602:
6598:
6593:
6588:
6584:
6580:
6573:
6570:
6565:
6561:
6554:
6551:
6547:
6541:
6537:
6533:
6532:
6527:
6523:
6522:Grundy, P. M.
6517:
6514:
6509:
6505:
6501:
6497:
6493:
6490:(in German).
6489:
6488:
6483:
6479:
6473:
6470:
6463:
6459:
6456:
6454:
6451:
6450:
6446:
6444:
6442:
6441:
6436:
6435:
6430:
6426:
6422:
6419:, notably by
6418:
6402:
6382:
6379:
6376:
6373:
6353:
6350:
6347:
6327:
6307:
6295:
6291:
6264:
6249:
6229:
6226:
6206:
6198:
6197:
6196:
6181:
6178:
6175:
6172:
6152:
6132:
6120:
6118:
6104:
6101:
6098:
6095:
6075:
6072:
6069:
6065:
6062:
6040:
6037:
6033:
6030:
6021:
6005:
6001:
5980:
5960:
5957:
5952:
5948:
5927:
5924:
5902:
5898:
5894:
5874:
5871:
5866:
5862:
5839:
5835:
5831:
5811:
5808:
5788:
5785:
5780:
5776:
5753:
5749:
5745:
5724:
5721:
5711:
5672:
5669:
5665:
5644:
5641:
5632:
5616:
5596:
5593:
5589:
5586:
5564:
5561:
5557:
5537:
5534:
5525:
5487:
5484:
5481:
5477:
5474:
5453:
5450:
5429:
5426:
5418:Suppose that
5416:
5402:
5399:
5396:
5392:
5389:
5344:
5341:
5338:
5334:
5331:
5321:
5306:
5303:
5299:
5296:
5251:
5248:
5244:
5241:
5196:
5193:
5171:
5168:
5145:
5141:
5137:
5117:
5095:
5091:
5069:
5066:
5062:
5059:
5039:
5018:
5015:
5011:
5008:
4999:
4983:
4979:
4956:
4952:
4948:
4945:
4942:
4937:
4933:
4929:
4924:
4920:
4911:
4895:
4875:
4872:
4869:
4866:
4841:
4837:
4833:
4830:
4827:
4824:
4819:
4815:
4811:
4808:
4803:
4799:
4795:
4789:
4785:
4782:
4759:
4755:
4751:
4748:
4743:
4739:
4730:
4709:
4705:
4701:
4698:
4695:
4690:
4686:
4682:
4677:
4673:
4666:
4663:
4654:
4652:
4644:
4642:
4627:
4624:
4620:
4617:
4597:
4589:
4585:
4569:
4561:
4560:associativity
4542:
4539:
4536:
4530:
4526:
4523:
4519:
4515:
4512:
4491:
4488:
4484:
4481:
4477:
4473:
4470:
4425:
4422:
4419:
4416:
4413:
4389:
4386:
4382:
4379:
4373:
4370:
4367:
4364:
4344:
4341:
4338:
4335:
4332:
4287:
4284:
4280:
4277:
4274:
4271:
4262:
4248:
4204:
4201:
4198:
4178:
4175:
4172:
4164:
4163:commutativity
4147:
4144:
4140:
4137:
4117:
4114:
4110:
4107:
4086:
4083:
4080:
4059:
4056:
4052:
4049:
4040:
4001:
3998:
3994:
3991:
3970:
3967:
3963:
3960:
3948:
3946:
3943:
3929:
3926:
3923:
3879:
3876:
3873:
3870:
3867:
3823:
3803:
3800:
3797:
3729:
3726:
3723:
3720:
3717:
3673:
3670:
3667:
3658:
3620:
3617:
3614:
3611:
3608:
3588:
3585:
3582:
3562:
3559:
3556:
3512:
3492:
3472:
3452:
3449:
3446:
3443:
3440:
3396:
3393:
3390:
3383:Suppose that
3381:
3367:
3347:
3344:
3341:
3338:
3335:
3315:
3312:
3309:
3289:
3286:
3283:
3280:
3277:
3257:
3213:
3201:
3199:
3181:
3178:
3173:
3169:
3120:
3117:
3112:
3108:
3075:
3033:
3030:
3007:
2974:
2970:
2965:
2951:
2948:
2944:
2941:
2920:
2917:
2914:
2894:
2870:
2867:
2863:
2860:
2840:
2832:
2831:
2813:
2810:
2789:
2780:
2742:
2739:
2695:
2692:
2684:
2683:
2655:
2654:
2626:
2625:
2616:
2614:
2597:
2594:
2591:
2588:
2584:
2581:
2577:
2574:
2568:
2561:
2558:
2554:
2550:
2547:
2543:
2539:
2536:
2532:
2529:
2523:
2519:
2516:
2512:
2509:
2500:
2453:
2450:
2447:
2441:
2438:
2432:
2429:
2426:
2420:
2411:
2408:
2399:
2393:
2390:
2380:
2375:
2372:
2367:
2357:
2354:
2351:
2345:
2342:
2336:
2333:
2330:
2324:
2321:
2318:
2311:
2306:
2303:
2298:
2291:
2288:
2285:
2279:
2276:
2270:
2267:
2264:
2257:
2252:
2249:
2237:
2223:
2220:
2213:
2209:
2198:
2193:
2190:
2185:
2181:
2172:
2171:combined game
2167:
2153:
2140:
2137:
2124:
2120:
2117:
2093:
2090:
2080:
2075:
2044:
2041:
2038:
2032:
2029:
2023:
2020:
2017:
2011:
2002:
1999:
1990:
1984:
1981:
1968:
1955:
1952:
1949:
1943:
1940:
1934:
1931:
1928:
1922:
1919:
1916:
1906:
1896:
1893:
1890:
1884:
1881:
1875:
1872:
1869:
1852:
1849:
1827:
1818:
1807:Combined Game
1806:
1804:
1789:
1786:
1764:
1761:
1739:
1736:
1715:
1695:
1675:
1667:
1666:first example
1655:
1653:
1638:
1635:
1613:
1610:
1588:
1585:
1576:
1575:
1566:
1564:
1562:
1558:
1554:
1549:
1532:
1529:
1523:
1520:
1517:
1514:
1508:
1505:
1502:
1496:
1476:
1473:
1470:
1463:and for all
1447:
1444:
1441:
1438:
1435:
1429:
1426:
1423:
1400:
1397:
1391:
1388:
1385:
1342:
1339:
1319:
1299:
1296:
1288:
1287:
1286:
1268:
1265:
1245:
1242:
1222:
1219:
1207:
1191:
1171:
1168:
1165:
1159:
1156:
1150:
1147:
1144:
1138:
1129:
1126:
1117:
1111:
1108:
1095:
1082:
1079:
1076:
1070:
1067:
1061:
1058:
1055:
1049:
1046:
1043:
1033:
1023:
1020:
1017:
1011:
1008:
1002:
999:
996:
974:
960:
950:
947:
944:
938:
935:
932:
926:
923:
917:
914:
911:
893:
871:
868:
865:
859:
856:
850:
847:
844:
817:
814:
791:
788:
785:
782:
779:
768:
752:
749:
729:
726:
718:
699:
696:
673:
670:
662:
644:
641:
618:
615:
606:
591:
588:
565:
562:
551:
535:
532:
524:
520:
505:
502:
471:
470:
462:
460:
457:
432:
427:
424:
420:
419:
413:
409:
408:
407:
400:
377:
365:
359:
356:
353:
330:
310:
302:
298:
297:
292:
291:
285:
283:
279:
275:
271:
267:
266:
257:
255:
253:
249:
248:R. P. Sprague
244:
243:of the game.
242:
237:
233:
228:
226:
222:
218:
214:
210:
206:
202:
198:
187:
184:
169:
166:
158:
148:
144:
138:
135:This article
133:
124:
123:
114:
111:
103:
93:
89:
83:
82:
76:
71:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
7583:Peyton Young
7578:Paul Milgrom
7493:Hervé Moulin
7433:Amos Tversky
7404:
7375:Folk theorem
7086:-player game
7083:
7008:Grim trigger
6651:
6644:sputsoft.com
6630:cut-the-knot
6582:
6578:
6572:
6563:
6559:
6553:
6545:
6540:the original
6535:
6529:
6516:
6491:
6485:
6472:
6453:Genus theory
6438:
6432:
6299:
6124:
6022:
5712:
5630:
5526:
5417:
5322:
5000:
4655:
4648:
4588:transitivity
4263:
4041:
3952:
3949:Second Lemma
3944:
3659:
3382:
3205:
3073:
2966:
2829:
2828:
2781:
2681:
2680:
2652:
2651:
2623:
2622:
2620:
2501:
2168:
2076:
1814:
1663:
1573:
1572:
1570:
1560:
1556:
1552:
1550:
1283:
1282:
1211:
766:
716:
549:
522:
458:
430:
428:
417:
416:
404:
403:
401:
300:
295:
294:
289:
288:
286:
281:
277:
264:
263:
261:
252:P. M. Grundy
245:
241:nim-sequence
240:
235:
232:Grundy value
231:
229:
200:
194:
179:
161:
152:
136:
106:
97:
78:
50:
43:
37:
36:Please help
33:
7700:Coopetition
7503:Jean Tirole
7498:John Conway
7478:Eric Maskin
7274:Blotto game
7259:Pirate game
7068:Global game
7038:Tit for tat
6973:Bid shading
6963:Appeasement
6813:Equilibrium
6793:Solved game
6728:Determinacy
6711:Definitions
6704:game theory
6566:(2): 221–22
6494:: 438–444.
6421:Richard Guy
6121:Development
5710:-position.
5524:-position.
4039:-position.
3742:is also an
3657:-position.
3202:First Lemma
2779:-position.
2617:Equivalence
552:is written
258:Definitions
250:(1936) and
92:introducing
7750:Categories
7344:Trust game
7329:Kuhn poker
6998:Escalation
6993:Deterrence
6983:Cheap talk
6955:Strategies
6773:Preference
6702:Topics of
6508:0013.29004
6500:62.1070.03
6464:References
6165:such that
5609:. Because
4438:is also a
4217:must be a
3892:must be a
3250:-position
3226:and every
2830:equivalent
2682:- position
2653:- position
207:under the
75:references
39:improve it
7528:John Nash
7234:Stag hunt
6978:Collusion
6660:CiteSeerX
6374:∗
6227:∗
6179:∗
6176:≈
6102:∗
6099:≈
6073:∗
6070:≈
6034:≈
5925:∗
5895:∗
5832:∗
5809:∗
5746:∗
5666:∗
5558:∗
5535:∗
5485:∗
5451:∗
5400:∗
5397:≈
5342:∗
5300:≈
5138:∗
5012:≈
4946:…
4873:∗
4870:≈
4834:∗
4828:…
4812:∗
4796:∗
4774:. So let
4752:∗
4749:≈
4727:. By the
4699:…
4621:≈
4598:≈
4570:≈
4520:≈
4478:≈
4368:≈
4336:≈
4053:≈
3964:≈
3281:≈
3174:≈
2892:∀
2864:≈
2740:∗
2693:∗
2595:∈
2589:∣
2569:∪
2555:∈
2544:∣
2451:∗
2439:∗
2427:∗
2409:∗
2391:∗
2355:∗
2343:∗
2331:∗
2319:∗
2289:∗
2277:∗
2265:∗
2238:∪
2221:∗
2138:∗
2042:∗
2030:∗
2018:∗
2000:∗
1982:∗
1953:∗
1941:∗
1929:∗
1917:∗
1894:∗
1882:∗
1870:∗
1530:∗
1524:∪
1518:∗
1497:∗
1474:≥
1445:∗
1436:∗
1424:∗
1398:∗
1386:∗
1340:∗
1297:∗
1266:∗
1243:∗
1220:∗
1169:∗
1157:∗
1145:∗
1127:∗
1109:∗
1080:∗
1068:∗
1056:∗
1044:∗
1021:∗
1009:∗
997:∗
948:∗
936:∗
924:∗
912:∗
869:∗
857:∗
845:∗
815:∗
789:∗
780:∗
750:∗
727:∗
697:∗
671:∗
642:∗
616:∗
589:∗
563:∗
533:∗
503:∗
431:zero game
418:impartial
301:zero game
236:nim-value
155:June 2014
100:June 2014
45:talk page
7669:Lazy SMP
7363:Theorems
7314:Deadlock
7169:Checkers
7050:of games
6817:concepts
6524:(1939).
6480:(1936).
6447:See also
6066:′
6041:′
5973:because
5725:′
5673:′
5645:′
5629:was the
5590:′
5565:′
5478:′
5430:′
5393:′
5335:′
5307:′
5252:′
5197:′
5172:′
5070:′
5019:′
4888:, where
4786:′
4628:′
4527:′
4516:′
4485:′
4474:′
4390:′
4288:′
4148:′
4111:′
4060:′
4002:′
3971:′
3525:being a
3182:′
3121:′
3034:′
2945:′
2871:′
2814:′
2585:′
2562:′
2551:′
2540:′
2520:′
2376:′
2307:′
2253:′
2194:′
2121:′
2094:′
2077:For the
1790:′
1765:′
1740:′
1639:′
1614:′
1589:′
1563:nimber.
550:position
423:checkers
290:position
254:(1939).
7421:figures
7204:Chicken
7058:Auction
7048:Classes
6609:7175146
6548:: 9–11.
6340:, then
6294:nim-sum
5631:minimum
4908:is the
4357:, that
4191:. But
1285:nimbers
1208:Nimbers
141:Please
88:improve
6662:
6607:
6531:Eureka
6506:
6498:
5578:where
4582:is an
4558:. By
3686:is an
2973:second
2755:is an
1778:, and
1627:, and
1574:adding
1561:single
1258:, and
548:, her
225:nimber
199:, the
77:, but
7159:Chess
7146:Games
6656:(PDF)
6605:S2CID
6587:arXiv
6242:) is
5768:. If
5357:is a
5265:is a
4645:Proof
4504:that
4301:is a
4015:is a
3409:is a
3137:is a
3021:and
2969:first
2708:is a
1661:wins.
765:, so
742:and
296:moves
6840:Core
6437:and
6054:and
5872:>
5786:<
5594:<
5443:and
3328:and
3048:are
2971:and
2827:are
2802:and
523:move
468:wins
265:game
230:The
7419:Key
6642:at
6628:at
6597:doi
6564:123
6504:Zbl
6496:JFM
6125:If
6020:.)
5917:to
5824:to
5658:to
5160:in
5110:in
4590:of
4161:by
3198:.)
3074:Bob
1557:nim
1553:nim
1355:is
767:her
717:His
412:nim
402:An
272:of
234:or
213:nim
195:In
145:to
7752::
7154:Go
6658:,
6603:.
6595:.
6581:.
6562:,
6546:27
6534:.
6528:.
6502:.
6492:41
6484:.
6443:.
6427:,
6423:,
5320:.
4998:.
4641:.
3942:.
3380:.
2964:.
2907:,
1803::
1753:,
1728:,
1708:,
1688:,
1652:.
1602:,
1548:.
1489:,
1416:,
1378:,
1235:,
48:.
7084:n
6695:e
6688:t
6681:v
6611:.
6599::
6589::
6583:6
6536:2
6510:.
6403:H
6383:H
6380:+
6377:m
6354:H
6351:+
6348:G
6328:m
6308:G
6275:P
6262:;
6250:m
6230:m
6207:m
6182:m
6173:G
6153:m
6133:G
6105:m
6096:G
6076:m
6063:G
6038:G
6031:G
6006:i
6002:n
5981:m
5961:m
5958:=
5953:i
5949:n
5928:m
5903:i
5899:n
5875:m
5867:i
5863:n
5840:i
5836:n
5812:m
5789:m
5781:i
5777:n
5754:i
5750:n
5722:G
5696:P
5670:m
5642:G
5617:m
5597:m
5587:m
5562:m
5538:m
5510:P
5488:m
5482:+
5475:G
5454:m
5427:G
5403:m
5390:G
5367:P
5345:m
5339:+
5332:G
5304:G
5297:G
5275:P
5249:G
5245:+
5242:G
5220:P
5194:G
5169:G
5146:i
5142:n
5118:G
5096:i
5092:G
5067:G
5063:+
5060:G
5040:k
5016:G
5009:G
4984:i
4980:n
4957:k
4953:n
4949:,
4943:,
4938:2
4934:n
4930:,
4925:1
4921:n
4896:m
4876:m
4867:G
4847:}
4842:k
4838:n
4831:,
4825:,
4820:2
4816:n
4809:,
4804:1
4800:n
4793:{
4790:=
4783:G
4760:i
4756:n
4744:i
4740:G
4715:}
4710:k
4706:G
4702:,
4696:,
4691:2
4687:G
4683:,
4678:1
4674:G
4670:{
4667:=
4664:G
4625:G
4618:G
4546:)
4543:G
4540:+
4537:G
4534:(
4531:+
4524:G
4513:G
4492:B
4489:+
4482:G
4471:G
4448:P
4426:G
4423:+
4420:G
4417:=
4414:B
4394:)
4387:G
4383:+
4380:G
4377:(
4374:+
4371:G
4365:G
4345:A
4342:+
4339:G
4333:G
4311:P
4285:G
4281:+
4278:G
4275:=
4272:A
4249:G
4227:P
4205:G
4202:+
4199:G
4179:G
4176:+
4173:G
4145:G
4141:+
4138:G
4118:G
4115:+
4108:G
4087:G
4084:=
4081:H
4057:G
4050:G
4025:P
3999:G
3995:+
3992:G
3968:G
3961:G
3930:H
3927:+
3924:G
3902:N
3880:H
3877:+
3874:G
3871:+
3868:A
3846:P
3824:A
3804:H
3801:+
3798:G
3776:P
3752:N
3730:H
3727:+
3724:G
3721:+
3718:A
3696:N
3674:H
3671:+
3668:G
3643:P
3621:H
3618:+
3615:G
3612:+
3609:A
3589:H
3586:+
3583:G
3563:H
3560:+
3557:G
3535:P
3513:A
3493:A
3473:A
3453:H
3450:+
3447:G
3444:+
3441:A
3419:P
3397:H
3394:+
3391:G
3368:H
3348:H
3345:+
3342:G
3339:+
3336:A
3316:H
3313:+
3310:G
3290:G
3287:+
3284:A
3278:G
3258:A
3236:P
3214:G
3179:S
3170:S
3147:P
3118:S
3113:+
3109:S
3086:N
3058:N
3031:S
3008:S
2985:P
2952:H
2949:+
2942:G
2921:H
2918:+
2915:G
2895:H
2868:G
2861:G
2841:H
2811:G
2790:G
2765:N
2743:1
2718:P
2696:0
2666:P
2637:N
2601:}
2598:S
2592:s
2582:S
2578:+
2575:s
2572:{
2566:}
2559:S
2548:s
2537:s
2533:+
2530:S
2527:{
2524:=
2517:S
2513:+
2510:S
2466:}
2460:}
2457:}
2454:2
2448:,
2445:}
2442:1
2436:{
2433:,
2430:1
2424:{
2421:,
2418:}
2415:}
2412:1
2406:{
2403:{
2400:,
2397:}
2394:1
2388:{
2385:{
2381:+
2373:S
2368:,
2364:}
2361:}
2358:2
2352:,
2349:}
2346:1
2340:{
2337:,
2334:1
2328:{
2325:,
2322:2
2316:{
2312:+
2304:S
2299:,
2295:}
2292:2
2286:,
2283:}
2280:1
2274:{
2271:,
2268:1
2262:{
2258:+
2250:S
2243:{
2233:}
2227:}
2224:1
2218:{
2214:+
2210:S
2204:{
2199:=
2191:S
2186:+
2182:S
2154:.
2149:}
2144:}
2141:1
2135:{
2130:{
2125:=
2118:S
2091:S
2060:}
2053:}
2048:}
2045:2
2039:,
2036:}
2033:1
2027:{
2024:,
2021:1
2015:{
2012:,
2009:}
2006:}
2003:1
1997:{
1994:{
1991:,
1988:}
1985:1
1979:{
1974:{
1969:,
1964:}
1959:}
1956:2
1950:,
1947:}
1944:1
1938:{
1935:,
1932:1
1926:{
1923:,
1920:2
1912:{
1907:,
1902:}
1897:2
1891:,
1888:}
1885:1
1879:{
1876:,
1873:1
1865:{
1858:{
1853:=
1850:S
1828:S
1787:C
1762:B
1737:A
1716:C
1696:B
1676:A
1636:C
1611:B
1586:A
1536:}
1533:n
1527:{
1521:n
1515:=
1512:)
1509:1
1506:+
1503:n
1500:(
1477:0
1471:n
1451:}
1448:1
1442:,
1439:0
1433:{
1430:=
1427:2
1404:}
1401:0
1395:{
1392:=
1389:1
1366:}
1363:{
1343:0
1320:n
1300:n
1269:2
1246:1
1223:0
1192:.
1187:}
1180:}
1175:}
1172:2
1166:,
1163:}
1160:1
1154:{
1151:,
1148:1
1142:{
1139:,
1136:}
1133:}
1130:1
1124:{
1121:{
1118:,
1115:}
1112:1
1106:{
1101:{
1096:,
1091:}
1086:}
1083:2
1077:,
1074:}
1071:1
1065:{
1062:,
1059:1
1053:{
1050:,
1047:2
1039:{
1034:,
1029:}
1024:2
1018:,
1015:}
1012:1
1006:{
1003:,
1000:1
992:{
985:{
961:.
956:}
951:2
945:,
942:}
939:2
933:,
930:}
927:1
921:{
918:,
915:1
909:{
904:{
891:.
877:}
872:2
866:,
863:}
860:1
854:{
851:,
848:1
840:{
818:2
795:}
792:1
786:,
783:0
777:{
753:1
730:0
703:}
700:1
694:{
674:1
660:.
648:}
645:1
639:{
619:1
604:.
592:1
569:}
566:0
560:{
536:0
518:.
506:0
483:}
480:{
444:}
441:{
387:)
384:}
381:{
378:,
375:}
372:{
369:(
366:=
363:)
360:B
357:,
354:A
351:(
331:B
311:A
186:)
180:(
168:)
162:(
157:)
153:(
139:.
113:)
107:(
102:)
98:(
84:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.