179:, one can recursively evaluate a non-final position as identical to the position that is one move away and best valued for the player whose move it is. Thus a transition between positions can never result in a better evaluation for the moving player, and a perfect move in a position would be a transition between positions that are equally evaluated. As an example, a perfect player in a drawn position would always get a draw or win, never a loss. If there are multiple options with the same outcome, perfect play is sometimes considered the fastest method leading to a good result, or the slowest method leading to a bad result.
263:
641:) shows that all square board sizes cannot be lost by the first player. Combined with a proof of the impossibility of a draw, this shows that the game is a first player win (so it is ultra-weak solved). On particular board sizes, more is known: it is strongly solved by several computers for board sizes up to 6×6. Weak solutions are known for board sizes 7×7 (using a
127:. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate a move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time. Many algorithms rely on a huge pre-generated database and are effectively nothing more.
1519:(which says the 7x7 solution is only weakly solved and it's still under research, 1. the correct komi is 9 (4.5 stone); 2. there are multiple optimal trees - the first 3 moves are unique - but within the first 7 moves there are 5 optimal trees; 3. There are many ways to play that don't affect the result)
115:
By contrast, "strong" proofs often proceed by brute force—using a computer to exhaustively search a game tree to figure out what would happen if perfect play were realized. The resulting proof gives an optimal strategy for every possible position on the board. However, these proofs are not as helpful
174:
is the behavior or strategy of a player that leads to the best possible outcome for that player regardless of the response by the opponent. Perfect play for a game is known when the game is solved. Based on the rules of a game, every possible final position can be evaluated (as a win, loss or draw).
145:
Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if its solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple
675:
All endgame positions with two through seven pieces were solved, as well as positions with 4×4 and 5×3 pieces where each side had one king or fewer, positions with five men versus four men, positions with five men versus three men and one king, and positions with four men and one king versus four
194:
would be to randomly choose each of the options with equal (1/3) probability. The disadvantage in this example is that this strategy will never exploit non-optimal strategies of the opponent, so the expected outcome of this strategy versus any strategy will always be equal to the minimal expected
111:
Despite their name, many game theorists believe that "ultra-weak" proofs are the deepest, most interesting and valuable. "Ultra-weak" proofs require a scholar to reason about the abstract properties of the game, and show how these properties lead to certain outcomes if perfect play is realized.
273:
on
October 16, 1988. The first player can force a win. Strongly solved by John Tromp's 8-ply database (Feb 4, 1995). Weakly solved for all boardsizes where width+height is at most 15 (as well as 8×8 in late 2015) (Feb 18, 2006). Solved for all boardsizes where width+height equals 16 on May 22,
476:. From the standard starting position, both players can guarantee a draw with perfect play. Checkers has a search space of 5×10 possible game positions. The number of calculations involved was 10, which were done over a period of 18 years. The process involved from 200
1189:
374:
Strongly solved by Jason
Doucette (2001). The game is a draw. There are only two unique first moves if you discard mirrored positions. One forces the draw, and the other gives the opponent a forced win in 15
317:
Most variants solved by
Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk (2000) except Kalah (6/6). The (6/6) variant was solved by Anders Carstensen (2011). Strong first-player advantage was proven in most
515:. From the standard starting position on an 8×8 board, a perfect play by both players will result in a draw. Othello is the largest game solved to date, with a search space of 10 possible game positions.
676:
men. The endgame positions were solved in 2007 by Ed
Gilbert of the United States. Computer analysis showed that it was highly likely to end in a draw if both players played perfectly.
621:
The 5×5 board was weakly solved for all opening moves in 2002. The 7×7 board was weakly solved in 2015. Humans usually play on a 19×19 board, which is over 145
432:
Strongly solved by
Johannes Laire in 2009, and weakly solved by Ali Elabridi in 2017. It is a win for the blue pieces (Cardinal Richelieu's men, or, the enemy).
665:+ 1) board then the player who has the shorter distance to connect can always win by a simple pairing strategy, even with the disadvantage of playing second.
799:
93:
Provide an algorithm that secures a win for one player, or a draw for either, against any possible play by the opponent, from the beginning of the game.
440:
Trivially strongly solvable because of the small game tree. The game is a draw if no mistakes are made, with no mistake possible on the opening move.
366:
Weakly solved by humans, but proven by computers. (Dakon is, however, not identical to
Ohvalhu, the game which actually had been observed by de Voogt)
198:
Although the optimal strategy of a game may not (yet) be known, a game-playing computer might still benefit from solutions of the game from certain
1107:
1137:
116:
in understanding deeper reasons why some games are solvable as a draw, and other, seemingly very similar games are solvable as a win.
586:
Fully solving chess remains elusive, and it is speculated that the complexity of the game may preclude it ever being solved. Through
984:
1477:
1364:
1334:
42:) can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to
1619:
1356:
2518:
297:
1531:
2691:
2335:
1870:
1668:
746:
17:
2154:
1973:
1162:
997:
2686:
1775:
1485:
779:
2244:
2114:
1785:
119:
Given the rules of any two-person game with a finite number of positions, one can always trivially construct a
1953:
645:), 8×8, and 9×9; in the 8×8 case, a weak solution is known for all opening moves. Strongly solving Hex on an
2295:
1713:
1688:
134:
is easily solvable as a draw for both players with perfect play (a result manually determinable). Games like
2645:
2071:
1825:
1815:
1750:
1234:
2681:
1865:
1845:
2579:
2330:
2300:
1958:
1800:
1795:
696:
634:
80:
46:, and especially to games with full information and no element of chance; solving such a game may use
2615:
2538:
2274:
1830:
1755:
1612:
609:
have been solved. Some other popular variants have also been solved; for example, a weak solution to
139:
107:
for both players from any position, even if imperfect play has already occurred on one or both sides.
47:
1406:
2630:
2363:
2249:
2046:
1840:
1658:
915:
610:
329:
147:
2433:
1111:
2635:
2234:
2204:
1860:
1648:
1547:
P. Henderson, B. Arneson, and R. Hayward, , Proc. IJCAI-09 505-510 (2009) Retrieved 29 June 2010.
530:
427:
1461:
2660:
2640:
2620:
2569:
2239:
2144:
2003:
1948:
1880:
1850:
1770:
1698:
1354:
1230:
670:
449:
248:
43:
1456:
1355:
M.P.D. Schadd; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; M.H.J. Bergsma (2008).
2696:
2119:
2104:
1678:
1039:
949:
794:
638:
419:
2453:
2438:
2325:
2320:
2224:
2209:
2174:
2139:
1738:
1683:
1605:
1269:
1126:
345:
875:
8:
2610:
2229:
2179:
2016:
1943:
1923:
1780:
1663:
587:
390:
191:
183:
2269:
1273:
1190:"Weakly Solving the Three Musketeers Game Using Artificial Intelligence and Game Theory"
1003:
2589:
2448:
2279:
2259:
2109:
1988:
1893:
1820:
1765:
1510:
1431:
1295:
966:
898:
741:
622:
512:
473:
413:
238:
76:
71:
Prove whether the first player will win, lose or draw from the initial position, given
1474:
613:
is an easily memorable series of moves that guarantees victory to the "sepoys" player.
253:
Strongly solved. If two players both play perfectly, the game will go on indefinitely.
2574:
2543:
2498:
2393:
2264:
2219:
2194:
2124:
1998:
1928:
1918:
1810:
1760:
1708:
1497:
1287:
1156:
993:
940:
775:
591:
548:
443:
203:
176:
1299:
838:
190:
regardless of the strategy of the opponent. As an example, the perfect strategy for
2655:
2650:
2584:
2548:
2528:
2488:
2458:
2413:
2368:
2353:
2310:
2164:
1805:
1742:
1728:
1693:
1373:
1277:
1026:
958:
731:
628:
558:
477:
462:
155:
369:
2553:
2513:
2468:
2383:
2378:
2099:
2051:
1938:
1703:
1673:
1643:
1585:
1535:
1481:
1381:
983:
Gasser, Ralph (1996). "Solving Nine Men's Morris". In
Nowakowski, Richard (ed.).
736:
654:
404:
Claimed to be solved by János Wagner and István Virág (2001). A first-player win.
353:
309:
3×3 variant solved as a win for black, several other larger variants also solved.
59:
2418:
2493:
2483:
2473:
2408:
2398:
2388:
2373:
2169:
2149:
2134:
2129:
2089:
2056:
2041:
2036:
2026:
1835:
1528:
1205:
721:
536:
207:
187:
1377:
1313:
1093:
1052:
2675:
2533:
2523:
2478:
2463:
2443:
2214:
2189:
2061:
2031:
2021:
2008:
1913:
1855:
1790:
1723:
1556:
1065:
856:
595:
580:
199:
1282:
1257:
350:
Solved by Ralph Gasser (1993). Either player can force the game into a draw.
2508:
2503:
2358:
1933:
1291:
599:
540:
495:
290:
284:
270:
256:
1573:
Beating the World
Champion? The state-of-the-art in computer game playing.
1175:
2625:
2428:
2423:
2403:
2199:
2184:
1993:
1963:
1898:
1888:
1653:
1629:
992:. Vol. 29. Cambridge: Cambridge University Press. pp. 101–113.
726:
435:
167:
131:
1597:
334:
This asymmetrical game is a win for the sepoys player with correct play.
269:
Solved first by James D. Allen on
October 1, 1988, and independently by
2254:
1908:
970:
679:
206:), which will allow it to play perfectly after some point in the game.
39:
395:
Solved by Luc
Goossens (1998). Two perfect players will always draw.
158:
on a sufficiently large board) generally does not affect playability.
2159:
2079:
1903:
1591:
820:
616:
606:
520:
416:(1998). Depending on the variant either a first-player win or a draw.
242:
234:
124:
1460:, MSRI Publications – Volume 29, 1996, pages 339-344. Online:
962:
2594:
2094:
1436:
642:
607:
variants of chess on a smaller board with reduced numbers of pieces
500:
Weakly solved in 2016 as a win for White beginning with 1. e3.
485:
469:
304:
245:, Netherlands (2002). Either player can force the game into a draw.
83:) that need not actually determine any details of the perfect play.
383:
Strongly solved by Geoffrey Irving with use of a supercomputer at
2315:
2305:
1983:
594:(strong solutions) have been found for all three- to seven-piece
505:
424:
Trivially solvable. Either player can force the game into a draw.
378:
361:
223:
120:
695:
It is trivial to show that the second player can never win; see
186:
games, as the strategy that would guarantee the highest minimal
1594:
solving two-person games with perfect information and no chance
525:
Weakly solved by H. K. Orman. It is a win for the first player.
321:
287:(1993). The first player can force a win without opening rules.
278:
262:
326:
Easily solvable. Either player can force the game into a draw.
2084:
573:
407:
398:
384:
312:
230:
219:
151:
772:
Searching for Solutions in Games and Artificial Intelligence
35:
511:
Weakly solved in 2023 by Hiroki Takizawa, a researcher at
233:
allowing game ending "grand slams" was strongly solved by
1314:"Project - Chinook - World Man-Machine Checkers Champion"
927:
337:
135:
1217:
563:
Weakly solved by Yew Jin Lim (2007). The game is a draw.
653:
board is unlikely as the problem has been shown to be
130:
As a simple example of a strong solution, the game of
918:
by Geoffrey Irving, Jeroen Donkers and Jos Uiterwijk.
839:"UCI Machine Learning Repository: Connect-4 Data Set"
774:(PhD thesis). Maastricht: Rijksuniversiteit Limburg.
1430:
Takizawa, Hiroki (2023-10-30). "Othello is Solved".
490:
Weakly solved by Maarten Schadd. The game is a draw.
472:
was weakly solved on April 29, 2007, by the team of
1335:"Checkers 'solved' after years of number crunching"
2673:
1125:Wágner, János & Virág, István (March 2001).
815:
813:
699:. Almost all cases have been solved weakly for
123:algorithm that would exhaustively traverse the
1613:
1586:Computational Complexity of Games and Puzzles
810:
27:Game whose outcome can be correctly predicted
797:, Jos W.H.M. Uiterwijk, Jack van Rijswijck,
1538:, Tromp and Farnebäck, accessed 2007-08-24.
1398:
1124:
939:
1620:
1606:
1575:in New Approaches to Board Games Research.
1348:
945:a game with a complete mathematical theory
1627:
1435:
1281:
1255:
567:
553:Weakly solved: win for the second player.
401:-like game without opening rules involved
1557:Some of the nine-piece endgame tablebase
1511:"首期喆理围棋沙龙举行 李喆7路盘最优解具有里程碑意义_下棋想赢怕输_新浪博客"
1429:
266:The game of Connect Four has been solved
261:
210:programs are well known for doing this.
1365:New Mathematics and Natural Computation
1332:
1229:
765:
763:
761:
182:Perfect play can be generalized to non-
14:
2674:
1475:On Forward Pruning in Game-Tree Search
1134:Széchenyi Egyetem - University of Győr
1040:"solved: Order wins - Order and Chaos"
982:
103:Provide an algorithm that can produce
65:
1601:
1357:"Best Play in Fanorona leads to Draw"
873:
769:
138:also admit a rigorous analysis using
1407:"Losing Chess: 1. e3 wins for White"
1187:
1094:"414298141056 Quarto Draws Suffice!"
758:
298:Official Scrabble Players Dictionary
1404:
1235:"A modification of the game of nim"
1053:Pangki is strongly solved as a draw
800:Games solved: Now and in the future
24:
1669:First-player and second-player win
1565:
1522:
1503:
1491:
1467:
1444:
1256:Schaeffer, Jonathan (2007-07-19).
1143:from the original on 24 April 2024
770:Allis, Louis Victor (1994-09-23).
97:
25:
2708:
1579:
896:
150:). An ultra-weak solution (e.g.,
104:
72:
62:can be solved on several levels:
1776:Coalition-proof Nash equilibrium
1486:National University of Singapore
821:"John's Connect Four Playground"
703:≤ 4. Some results are known for
87:
1550:
1541:
1452:Pentominoes: A First Player Win
1423:
1337:. NewScientist.com news service
1326:
1306:
1249:
1223:
1211:
1199:
1181:
1169:
1118:
1100:
1086:
1058:
1046:
1032:
1020:
976:
933:
747:Zermelo's theorem (game theory)
295:Solved by Alan Frank using the
213:
161:
1786:Evolutionarily stable strategy
1529:Counting legal positions in Go
1333:Mullins, Justin (2007-07-19).
921:
909:
890:
867:
849:
831:
788:
480:at its peak down to around 50.
456:
13:
1:
1714:Simultaneous action selection
1161:: CS1 maint: date and year (
752:
707:= 5. The games are drawn for
75:on both sides. This can be a
2646:List of games in game theory
1826:Quantal response equilibrium
1816:Perfect Bayesian equilibrium
1751:Bayes correlated equilibrium
588:retrograde computer analysis
79:proof (possibly involving a
50:and/or computer assistance.
38:whose outcome (win, lose or
7:
2115:Optional prisoner's dilemma
1846:Self-confirming equilibrium
1239:Nieuw Archief voor Wiskunde
1027:Nine Men's Morris is a Draw
715:
53:
10:
2713:
2580:Principal variation search
2296:Aumann's agreement theorem
1959:Strategy-stealing argument
1871:Trembling hand equilibrium
1801:Markov perfect equilibrium
1796:Mertens-stable equilibrium
874:Frank, Alan (1987-08-01).
697:strategy-stealing argument
635:strategy-stealing argument
578:
358:Order (First player) wins.
202:positions (in the form of
146:enough to remember (e.g.,
81:strategy-stealing argument
2692:Combinatorial game theory
2616:Combinatorial game theory
2603:
2562:
2344:
2288:
2275:Princess and monster game
2070:
1972:
1879:
1831:Quasi-perfect equilibrium
1756:Bayesian Nash equilibrium
1737:
1636:
1378:10.1142/S1793005708001124
857:"ChristopheSteininger/c4"
657:. If Hex is played on an
140:combinatorial game theory
48:combinatorial game theory
2631:Evolutionary game theory
2364:Antoine Augustin Cournot
2250:Guess 2/3 of the average
2047:Strictly determined game
1841:Satisfaction equilibrium
1659:Escalation of commitment
611:Maharajah and the Sepoys
543:. The first player wins.
387:. The first player wins.
330:Maharajah and the Sepoys
148:Maharajah and the Sepoys
2687:Abstract strategy games
2636:Glossary of game theory
2235:Stackelberg competition
1861:Strong Nash equilibrium
1283:10.1126/science.1144079
805:Artificial Intelligence
237:and John Romein at the
44:abstract strategy games
2661:Tragedy of the commons
2641:List of game theorists
2621:Confrontation analysis
2331:Sprague–Grundy theorem
1851:Sequential equilibrium
1771:Correlated equilibrium
671:International draughts
625:more complex than 7×7.
568:Partially solved games
267:
2434:Jean-François Mertens
950:Annals of Mathematics
930:by Anders Carstensen.
903:www.chessvariants.com
795:H. Jaap van den Herik
265:
2563:Search optimizations
2439:Jennifer Tour Chayes
2326:Revelation principle
2321:Purification theorem
2260:Nash bargaining game
2225:Bertrand competition
2210:El Farol Bar problem
2175:Electronic mail game
2140:Lewis signaling game
1684:Hierarchy of beliefs
1500:by Erik van der Werf
1258:"Checkers Is Solved"
928:Solving (6,6)-Kalaha
468:This 8×8 variant of
2611:Bounded rationality
2230:Cournot competition
2180:Rock paper scissors
2155:Battle of the sexes
2145:Volunteer's dilemma
2017:Perfect information
1944:Dominant strategies
1781:Epsilon-equilibrium
1664:Extensive-form game
1274:2007Sci...317.1518S
943:(1901–1902), "Nim,
843:archive.ics.uci.edu
807:134 (2002) 277–311.
623:orders of magnitude
598:, counting the two
448:Strongly solved by
192:rock paper scissors
184:perfect information
66:Ultra-weak solution
2682:Mathematical games
2590:Paranoid algorithm
2570:Alpha–beta pruning
2449:John Maynard Smith
2280:Rendezvous problem
2120:Traveler's dilemma
2110:Gift-exchange game
2105:Prisoner's dilemma
2022:Large Poisson game
1989:Bargaining problem
1894:Backward induction
1866:Subgame perfection
1821:Proper equilibrium
1588:by David Eppstein.
1534:2007-09-30 at the
1480:2009-03-25 at the
1457:Games of no chance
1450:Hilarie K. Orman:
986:Games of No Chance
592:endgame tablebases
513:Preferred Networks
474:Jonathan Schaeffer
420:Three men's morris
268:
239:Vrije Universiteit
204:endgame tablebases
177:backward reasoning
18:Solved board games
2669:
2668:
2575:Aspiration window
2544:Suzanne Scotchmer
2499:Oskar Morgenstern
2394:Donald B. Gillies
2336:Zermelo's theorem
2265:Induction puzzles
2220:Fair cake-cutting
2195:Public goods game
2125:Coordination game
1999:Intransitive game
1929:Forward induction
1811:Pareto efficiency
1791:Gibbs equilibrium
1761:Berge equilibrium
1709:Simultaneous game
1268:(5844): 1518–22.
1178:, by E. Weisstein
1073:wouterkoolen.info
1055:by Jason Doucette
643:swapping strategy
535:Weakly solved by
478:desktop computers
346:Nine men's morris
16:(Redirected from
2704:
2656:Topological game
2651:No-win situation
2549:Thomas Schelling
2529:Robert B. Wilson
2489:Merrill M. Flood
2459:John von Neumann
2369:Ariel Rubinstein
2354:Albert W. Tucker
2205:War of attrition
2165:Matching pennies
1806:Nash equilibrium
1729:Mechanism design
1694:Normal-form game
1649:Cooperative game
1622:
1615:
1608:
1599:
1598:
1560:
1554:
1548:
1545:
1539:
1526:
1520:
1518:
1515:blog.sina.com.cn
1507:
1501:
1498:5×5 Go is solved
1495:
1489:
1484:. Ph.D. Thesis,
1471:
1465:
1448:
1442:
1441:
1439:
1427:
1421:
1420:
1418:
1416:
1411:
1402:
1396:
1395:
1393:
1392:
1386:
1380:. Archived from
1361:
1352:
1346:
1345:
1343:
1342:
1330:
1324:
1323:
1321:
1320:
1310:
1304:
1303:
1285:
1253:
1247:
1246:
1227:
1221:
1215:
1209:
1206:Three Musketeers
1203:
1197:
1196:
1194:
1185:
1179:
1173:
1167:
1166:
1160:
1152:
1150:
1148:
1142:
1131:
1122:
1116:
1115:
1110:. Archived from
1104:
1098:
1097:
1090:
1084:
1083:
1081:
1079:
1070:
1062:
1056:
1050:
1044:
1043:
1036:
1030:
1024:
1018:
1017:
1015:
1014:
1008:
1002:. Archived from
991:
980:
974:
973:
937:
931:
925:
919:
913:
907:
906:
894:
888:
887:
871:
865:
864:
853:
847:
846:
835:
829:
828:
817:
808:
792:
786:
785:
767:
732:Computer Othello
559:Lambs and tigers
463:English draughts
428:Three musketeers
342:Strongly solved.
188:expected outcome
77:non-constructive
21:
2712:
2711:
2707:
2706:
2705:
2703:
2702:
2701:
2672:
2671:
2670:
2665:
2599:
2585:max^n algorithm
2558:
2554:William Vickrey
2514:Reinhard Selten
2469:Kenneth Binmore
2384:David K. Levine
2379:Daniel Kahneman
2346:
2340:
2316:Negamax theorem
2306:Minimax theorem
2284:
2245:Diner's dilemma
2100:All-pay auction
2066:
2052:Stochastic game
2004:Mean-field game
1975:
1968:
1939:Markov strategy
1875:
1741:
1733:
1704:Sequential game
1689:Information set
1674:Game complexity
1644:Congestion game
1632:
1626:
1582:
1568:
1566:Further reading
1563:
1555:
1551:
1546:
1542:
1536:Wayback Machine
1527:
1523:
1509:
1508:
1504:
1496:
1492:
1482:Wayback Machine
1472:
1468:
1449:
1445:
1428:
1424:
1414:
1412:
1409:
1405:Watkins, Mark.
1403:
1399:
1390:
1388:
1384:
1359:
1353:
1349:
1340:
1338:
1331:
1327:
1318:
1316:
1312:
1311:
1307:
1254:
1250:
1228:
1224:
1216:
1212:
1208:, by J. Lemaire
1204:
1200:
1192:
1188:Elabridi, Ali.
1186:
1182:
1174:
1170:
1154:
1153:
1146:
1144:
1140:
1129:
1127:"Solving Renju"
1123:
1119:
1106:
1105:
1101:
1092:
1091:
1087:
1077:
1075:
1068:
1064:
1063:
1059:
1051:
1047:
1038:
1037:
1033:
1029:by Ralph Gasser
1025:
1021:
1012:
1010:
1006:
1000:
989:
981:
977:
963:10.2307/1967631
938:
934:
926:
922:
914:
910:
897:Price, Robert.
895:
891:
872:
868:
855:
854:
850:
837:
836:
832:
825:tromp.github.io
819:
818:
811:
793:
789:
782:
768:
759:
755:
742:God's algorithm
737:Game complexity
718:
655:PSPACE-complete
583:
570:
459:
354:Order and Chaos
229:The variant of
222:(a game of the
216:
164:
100:
98:Strong solution
90:
68:
60:two-player game
56:
28:
23:
22:
15:
12:
11:
5:
2710:
2700:
2699:
2694:
2689:
2684:
2667:
2666:
2664:
2663:
2658:
2653:
2648:
2643:
2638:
2633:
2628:
2623:
2618:
2613:
2607:
2605:
2601:
2600:
2598:
2597:
2592:
2587:
2582:
2577:
2572:
2566:
2564:
2560:
2559:
2557:
2556:
2551:
2546:
2541:
2536:
2531:
2526:
2521:
2519:Robert Axelrod
2516:
2511:
2506:
2501:
2496:
2494:Olga Bondareva
2491:
2486:
2484:Melvin Dresher
2481:
2476:
2474:Leonid Hurwicz
2471:
2466:
2461:
2456:
2451:
2446:
2441:
2436:
2431:
2426:
2421:
2416:
2411:
2409:Harold W. Kuhn
2406:
2401:
2399:Drew Fudenberg
2396:
2391:
2389:David M. Kreps
2386:
2381:
2376:
2374:Claude Shannon
2371:
2366:
2361:
2356:
2350:
2348:
2342:
2341:
2339:
2338:
2333:
2328:
2323:
2318:
2313:
2311:Nash's theorem
2308:
2303:
2298:
2292:
2290:
2286:
2285:
2283:
2282:
2277:
2272:
2267:
2262:
2257:
2252:
2247:
2242:
2237:
2232:
2227:
2222:
2217:
2212:
2207:
2202:
2197:
2192:
2187:
2182:
2177:
2172:
2170:Ultimatum game
2167:
2162:
2157:
2152:
2150:Dollar auction
2147:
2142:
2137:
2135:Centipede game
2132:
2127:
2122:
2117:
2112:
2107:
2102:
2097:
2092:
2090:Infinite chess
2087:
2082:
2076:
2074:
2068:
2067:
2065:
2064:
2059:
2057:Symmetric game
2054:
2049:
2044:
2042:Signaling game
2039:
2037:Screening game
2034:
2029:
2027:Potential game
2024:
2019:
2014:
2006:
2001:
1996:
1991:
1986:
1980:
1978:
1970:
1969:
1967:
1966:
1961:
1956:
1954:Mixed strategy
1951:
1946:
1941:
1936:
1931:
1926:
1921:
1916:
1911:
1906:
1901:
1896:
1891:
1885:
1883:
1877:
1876:
1874:
1873:
1868:
1863:
1858:
1853:
1848:
1843:
1838:
1836:Risk dominance
1833:
1828:
1823:
1818:
1813:
1808:
1803:
1798:
1793:
1788:
1783:
1778:
1773:
1768:
1763:
1758:
1753:
1747:
1745:
1735:
1734:
1732:
1731:
1726:
1721:
1716:
1711:
1706:
1701:
1696:
1691:
1686:
1681:
1679:Graphical game
1676:
1671:
1666:
1661:
1656:
1651:
1646:
1640:
1638:
1634:
1633:
1625:
1624:
1617:
1610:
1602:
1596:
1595:
1589:
1581:
1580:External links
1578:
1577:
1576:
1567:
1564:
1562:
1561:
1549:
1540:
1521:
1502:
1490:
1466:
1443:
1422:
1397:
1372:(3): 369–387.
1347:
1325:
1305:
1248:
1231:Wythoff, W. A.
1222:
1220:, by R. Munroe
1210:
1198:
1180:
1168:
1136:. p. 30.
1117:
1114:on 2004-10-12.
1099:
1085:
1057:
1045:
1031:
1019:
998:
975:
932:
920:
908:
889:
876:"Ghostbusters"
866:
848:
830:
809:
787:
780:
756:
754:
751:
750:
749:
744:
739:
734:
729:
724:
722:Computer chess
717:
714:
713:
712:
693:
677:
673:
667:
666:
631:
626:
619:
614:
603:
584:
579:Main article:
576:
569:
566:
565:
564:
561:
555:
554:
551:
545:
544:
537:Oren Patashnik
533:
527:
526:
523:
517:
516:
509:
502:
501:
498:
492:
491:
488:
482:
481:
466:
458:
455:
454:
453:
446:
444:Wythoff's game
441:
438:
433:
430:
425:
422:
417:
410:
405:
402:
396:
393:
388:
381:
376:
372:
367:
364:
359:
356:
351:
348:
343:
340:
335:
332:
327:
324:
319:
315:
310:
307:
302:
293:
288:
281:
275:
259:
254:
251:
246:
227:
215:
212:
208:Computer chess
163:
160:
109:
108:
99:
96:
95:
94:
89:
86:
85:
84:
67:
64:
55:
52:
26:
9:
6:
4:
3:
2:
2709:
2698:
2695:
2693:
2690:
2688:
2685:
2683:
2680:
2679:
2677:
2662:
2659:
2657:
2654:
2652:
2649:
2647:
2644:
2642:
2639:
2637:
2634:
2632:
2629:
2627:
2624:
2622:
2619:
2617:
2614:
2612:
2609:
2608:
2606:
2604:Miscellaneous
2602:
2596:
2593:
2591:
2588:
2586:
2583:
2581:
2578:
2576:
2573:
2571:
2568:
2567:
2565:
2561:
2555:
2552:
2550:
2547:
2545:
2542:
2540:
2539:Samuel Bowles
2537:
2535:
2534:Roger Myerson
2532:
2530:
2527:
2525:
2524:Robert Aumann
2522:
2520:
2517:
2515:
2512:
2510:
2507:
2505:
2502:
2500:
2497:
2495:
2492:
2490:
2487:
2485:
2482:
2480:
2479:Lloyd Shapley
2477:
2475:
2472:
2470:
2467:
2465:
2464:Kenneth Arrow
2462:
2460:
2457:
2455:
2452:
2450:
2447:
2445:
2444:John Harsanyi
2442:
2440:
2437:
2435:
2432:
2430:
2427:
2425:
2422:
2420:
2417:
2415:
2414:Herbert Simon
2412:
2410:
2407:
2405:
2402:
2400:
2397:
2395:
2392:
2390:
2387:
2385:
2382:
2380:
2377:
2375:
2372:
2370:
2367:
2365:
2362:
2360:
2357:
2355:
2352:
2351:
2349:
2343:
2337:
2334:
2332:
2329:
2327:
2324:
2322:
2319:
2317:
2314:
2312:
2309:
2307:
2304:
2302:
2299:
2297:
2294:
2293:
2291:
2287:
2281:
2278:
2276:
2273:
2271:
2268:
2266:
2263:
2261:
2258:
2256:
2253:
2251:
2248:
2246:
2243:
2241:
2238:
2236:
2233:
2231:
2228:
2226:
2223:
2221:
2218:
2216:
2215:Fair division
2213:
2211:
2208:
2206:
2203:
2201:
2198:
2196:
2193:
2191:
2190:Dictator game
2188:
2186:
2183:
2181:
2178:
2176:
2173:
2171:
2168:
2166:
2163:
2161:
2158:
2156:
2153:
2151:
2148:
2146:
2143:
2141:
2138:
2136:
2133:
2131:
2128:
2126:
2123:
2121:
2118:
2116:
2113:
2111:
2108:
2106:
2103:
2101:
2098:
2096:
2093:
2091:
2088:
2086:
2083:
2081:
2078:
2077:
2075:
2073:
2069:
2063:
2062:Zero-sum game
2060:
2058:
2055:
2053:
2050:
2048:
2045:
2043:
2040:
2038:
2035:
2033:
2032:Repeated game
2030:
2028:
2025:
2023:
2020:
2018:
2015:
2013:
2011:
2007:
2005:
2002:
2000:
1997:
1995:
1992:
1990:
1987:
1985:
1982:
1981:
1979:
1977:
1971:
1965:
1962:
1960:
1957:
1955:
1952:
1950:
1949:Pure strategy
1947:
1945:
1942:
1940:
1937:
1935:
1932:
1930:
1927:
1925:
1922:
1920:
1917:
1915:
1914:De-escalation
1912:
1910:
1907:
1905:
1902:
1900:
1897:
1895:
1892:
1890:
1887:
1886:
1884:
1882:
1878:
1872:
1869:
1867:
1864:
1862:
1859:
1857:
1856:Shapley value
1854:
1852:
1849:
1847:
1844:
1842:
1839:
1837:
1834:
1832:
1829:
1827:
1824:
1822:
1819:
1817:
1814:
1812:
1809:
1807:
1804:
1802:
1799:
1797:
1794:
1792:
1789:
1787:
1784:
1782:
1779:
1777:
1774:
1772:
1769:
1767:
1764:
1762:
1759:
1757:
1754:
1752:
1749:
1748:
1746:
1744:
1740:
1736:
1730:
1727:
1725:
1724:Succinct game
1722:
1720:
1717:
1715:
1712:
1710:
1707:
1705:
1702:
1700:
1697:
1695:
1692:
1690:
1687:
1685:
1682:
1680:
1677:
1675:
1672:
1670:
1667:
1665:
1662:
1660:
1657:
1655:
1652:
1650:
1647:
1645:
1642:
1641:
1639:
1635:
1631:
1623:
1618:
1616:
1611:
1609:
1604:
1603:
1600:
1593:
1592:GamesCrafters
1590:
1587:
1584:
1583:
1574:
1570:
1569:
1559:by Ed Gilbert
1558:
1553:
1544:
1537:
1533:
1530:
1525:
1516:
1512:
1506:
1499:
1494:
1487:
1483:
1479:
1476:
1473:Yew Jin Lim.
1470:
1463:
1459:
1458:
1453:
1447:
1438:
1433:
1426:
1408:
1401:
1387:on 2016-03-04
1383:
1379:
1375:
1371:
1367:
1366:
1358:
1351:
1336:
1329:
1315:
1309:
1301:
1297:
1293:
1289:
1284:
1279:
1275:
1271:
1267:
1263:
1259:
1252:
1244:
1240:
1236:
1232:
1226:
1219:
1214:
1207:
1202:
1191:
1184:
1177:
1172:
1164:
1158:
1139:
1135:
1128:
1121:
1113:
1109:
1103:
1095:
1089:
1074:
1067:
1061:
1054:
1049:
1041:
1035:
1028:
1023:
1009:on 2015-07-24
1005:
1001:
999:9780521574112
995:
988:
987:
979:
972:
968:
964:
960:
957:(14): 35–39,
956:
952:
951:
946:
942:
941:Bouton, C. L.
936:
929:
924:
917:
916:Solving Kalah
912:
904:
900:
893:
885:
881:
877:
870:
862:
858:
852:
844:
840:
834:
826:
822:
816:
814:
806:
802:
801:
796:
791:
783:
777:
773:
766:
764:
762:
757:
748:
745:
743:
740:
738:
735:
733:
730:
728:
725:
723:
720:
719:
710:
706:
702:
698:
694:
692:
690:
686:
682:
678:
674:
672:
669:
668:
664:
660:
656:
652:
648:
644:
640:
636:
632:
630:
627:
624:
620:
618:
615:
612:
608:
604:
601:
597:
593:
589:
585:
582:
581:Solving chess
577:
575:
572:
571:
562:
560:
557:
556:
552:
550:
547:
546:
542:
538:
534:
532:
529:
528:
524:
522:
519:
518:
514:
510:
507:
504:
503:
499:
497:
494:
493:
489:
487:
484:
483:
479:
475:
471:
467:
464:
461:
460:
451:
450:W. A. Wythoff
447:
445:
442:
439:
437:
434:
431:
429:
426:
423:
421:
418:
415:
411:
409:
406:
403:
400:
397:
394:
392:
389:
386:
382:
380:
377:
373:
371:
368:
365:
363:
360:
357:
355:
352:
349:
347:
344:
341:
339:
336:
333:
331:
328:
325:
323:
320:
316:
314:
311:
308:
306:
303:
300:
299:
294:
292:
289:
286:
282:
280:
276:
272:
264:
260:
258:
255:
252:
250:
247:
244:
240:
236:
232:
228:
225:
221:
218:
217:
211:
209:
205:
201:
196:
193:
189:
185:
180:
178:
173:
169:
159:
157:
153:
149:
143:
141:
137:
133:
128:
126:
122:
117:
113:
106:
102:
101:
92:
91:
88:Weak solution
82:
78:
74:
70:
69:
63:
61:
51:
49:
45:
41:
37:
33:
19:
2697:Solved games
2509:Peyton Young
2504:Paul Milgrom
2419:Hervé Moulin
2359:Amos Tversky
2301:Folk theorem
2012:-player game
2009:
1934:Grim trigger
1718:
1572:
1552:
1543:
1524:
1514:
1505:
1493:
1469:
1455:
1451:
1446:
1425:
1413:. Retrieved
1400:
1389:. Retrieved
1382:the original
1369:
1363:
1350:
1339:. Retrieved
1328:
1317:. Retrieved
1308:
1265:
1261:
1251:
1245:(2): 199–202
1242:
1238:
1225:
1213:
1201:
1183:
1171:
1145:. Retrieved
1133:
1120:
1112:the original
1102:
1088:
1076:. Retrieved
1072:
1060:
1048:
1034:
1022:
1011:. Retrieved
1004:the original
985:
978:
954:
948:
944:
935:
923:
911:
902:
892:
883:
879:
869:
860:
851:
842:
833:
824:
804:
798:
790:
781:90-9007488-0
771:
708:
704:
700:
688:
684:
680:
662:
658:
650:
646:
637:(as used by
541:Victor Allis
496:Losing chess
296:
285:Victor Allis
271:Victor Allis
257:Connect Four
214:Solved games
197:
181:
172:perfect play
171:
165:
162:Perfect play
144:
129:
118:
114:
110:
105:perfect play
73:perfect play
57:
31:
29:
2626:Coopetition
2429:Jean Tirole
2424:John Conway
2404:Eric Maskin
2200:Blotto game
2185:Pirate game
1994:Global game
1964:Tit for tat
1899:Bid shading
1889:Appeasement
1739:Equilibrium
1719:Solved game
1654:Determinacy
1637:Definitions
1630:game theory
1218:Tic-Tac-Toe
1078:29 February
727:Computer Go
539:(1980) and
521:Pentominoes
457:Weak-solves
436:Tic-tac-toe
168:game theory
132:tic-tac-toe
32:solved game
2676:Categories
2270:Trust game
2255:Kuhn poker
1924:Escalation
1919:Deterrence
1909:Cheap talk
1881:Strategies
1699:Preference
1628:Topics of
1437:2310.19387
1415:17 January
1391:2015-04-08
1341:2020-12-06
1319:2007-07-19
1013:2022-01-03
899:"Hexapawn"
861:github.com
753:References
602:as pieces.
465:(checkers)
414:Guy Steele
412:Solved by
283:Solved by
249:Chopsticks
2454:John Nash
2160:Stag hunt
1904:Collusion
880:Word Ways
639:John Nash
508:(Reversi)
243:Amsterdam
235:Henri Bal
195:outcome.
125:game tree
2595:Lazy SMP
2289:Theorems
2240:Deadlock
2095:Checkers
1976:of games
1743:concepts
1532:Archived
1478:Archived
1300:10274228
1292:17641166
1233:(1907),
1157:cite web
1147:24 April
1138:Archived
1108:"Quarto"
1066:"Quarto"
716:See also
596:endgames
486:Fanorona
470:draughts
452:in 1907.
305:Hexapawn
301:in 1987.
54:Overview
2347:figures
2130:Chicken
1984:Auction
1974:Classes
1571:Allis,
1488:, 2007.
1270:Bibcode
1262:Science
971:1967631
506:Othello
379:Pentago
362:Ohvalhu
226:family)
224:Mancala
200:endgame
121:minimax
1298:
1290:
996:
969:
778:
391:Quarto
375:moves.
370:Pangki
322:L game
318:cases.
279:gomoku
2085:Chess
2072:Games
1432:arXiv
1410:(PDF)
1385:(PDF)
1360:(PDF)
1296:S2CID
1193:(PDF)
1176:Teeko
1141:(PDF)
1130:(PDF)
1069:(PDF)
1007:(PDF)
990:(PDF)
967:JSTOR
691:-game
605:Some
600:kings
574:Chess
531:Qubic
408:Teeko
399:Renju
385:NERSC
313:Kalah
291:Ghost
277:Free
274:2024.
231:Oware
220:Awari
152:Chomp
34:is a
1766:Core
1417:2017
1288:PMID
1163:link
1149:2024
1080:2024
994:ISBN
886:(4).
776:ISBN
711:≥ 8.
40:draw
36:game
2345:Key
1462:pdf
1454:in
1374:doi
1278:doi
1266:317
959:doi
947:",
629:Hex
549:Sim
338:Nim
241:in
175:By
166:In
156:Hex
154:or
136:nim
2678::
2080:Go
1513:.
1368:.
1362:.
1294:.
1286:.
1276:.
1264:.
1260:.
1241:,
1237:,
1159:}}
1155:{{
1132:.
1071:.
965:,
953:,
901:.
884:20
882:.
878:.
859:.
841:.
823:.
812:^
803:,
760:^
661:×(
633:A
617:Go
590:,
170:,
142:.
58:A
30:A
2010:n
1621:e
1614:t
1607:v
1517:.
1464:.
1440:.
1434::
1419:.
1394:.
1376::
1370:4
1344:.
1322:.
1302:.
1280::
1272::
1243:7
1195:.
1165:)
1151:.
1096:.
1082:.
1042:.
1016:.
961::
955:3
905:.
863:.
845:.
827:.
784:.
709:k
705:k
701:k
689:k
687:,
685:n
683:,
681:m
663:N
659:N
651:N
649:×
647:N
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.