115:, which is a subtree of the game tree, with each position labelled with "player A wins", "player B wins" or "drawn", if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in the graph. (Terminal positions can be labelled directly; a position with player A to move can be labelled "player A wins" if any successor position is a win for A, or labelled "player B wins" if all successor positions are wins for B, or labelled "draw" if all successor positions are either drawn or wins for B. And correspondingly for positions with B to move.)
305:, a simple upper bound for the size of the state space is 3 = 19,683. (There are three states for each cell and nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478. And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.
1698:. The bridge table can be regarded as having one slot for each player and trick to play a card in, which corresponds to board size 52. Game-tree complexity is a very weak upper bound: 13! to the power of 4 players regardless of legality. State-space complexity is for one given deal; likewise regardless of legality but with many transpositions eliminated. The last 4 plies are always forced moves with branching factor 1.
257:) is always lower-bounded by the logarithm of the asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexity of any particular algorithm that works for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of
308:
To bound the game tree, there are 9 possible initial moves, 8 possible responses, and so on, so that there are at most 9! or 362,880 total games. However, games may take less than 9 moves to resolve, and an exact enumeration gives 255,168 possible games. When rotations and reflections of positions
285:
proportional to the game's tree-complexity, since it must explore the whole tree, and an amount of memory polynomial in the logarithm of the tree-complexity, since the algorithm must always store one node of the tree at each possible move-depth, and the number of nodes at the highest move-depth is
97:
game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for
371:
to base 10. (In other words, the number of digits). All of the following numbers should be considered with caution: seemingly-minor changes to the rules of a game can change the numbers (which are often rough estimates anyway) by tremendous factors, which might easily be much greater than the
2475:
2490:
270:, and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well (technically the bound is only a polynomial in this quantity; but it is usually known to be linear).
245:
board. (From the point of view of computational complexity a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.)
265:
used by the computation. It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be
205:
101:
For games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is generally infinite.
93:
The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a
2541:
2379:
2561:
3124:
2952:
3356:
3321:
292:
will use both memory and time proportional to the state-space complexity as it must compute and record the correct move for each possible position.
2105:
2014:
Lachmann, Michael; Moore, Cristopher; Rapaport, Ivan (2002). "Who wins
Domineering on rectangular boards?". In Nowakowski, Richard (ed.).
3440:
2567:
152:
It is hard even to estimate the game-tree complexity, but for some games an approximation can be given by raising the game's average
2774:
2216:
74:
can often be computed by also counting (some) illegal positions, meaning positions that can never arise in the course of a game.
2194:
IJCAI 2013, Proceedings of the 23rd
International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013
2604:
GualĂ , Luciano; Leucci, Stefano; Natale, Emanuele (2014). "Bejeweled, Candy Crush and other match-three games are (NP-)hard".
3483:
3435:
2674:
50:
These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios.
4382:
1775:
2983:
2016:
More Games of No Chance: Proceedings of the 2nd
Combinatorial Games Theory Workshop held in Berkeley, CA, July 24–28, 2000
3296:
Stefan Reisch, Joel David
Hamkins, and Phillipp Schlicht (2012). "The mate-in-n problem of infinite chess is decidable".
1746:
126:
of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position.
4545:
4199:
3734:
3532:
2421:
142:
decision tree that establishes the value of the initial position. A full-width tree includes all nodes at each depth.
4018:
3837:
2454:
2023:
2018:. Mathematical Sciences Research Institute Publications. Vol. 42. Cambridge University Press. pp. 307–315.
1966:
1961:. Mathematical Sciences Research Institute Publications. Vol. 29. Cambridge University Press. pp. 339–344.
1759:
1885:
Computers and Games, Second
International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Revised Papers
3639:
3012:
3034:
2498:
Shannon gave estimates of 10 and 10 respectively, smaller than the upper bound in the table, which is detailed in
4108:
3133:
2932:
2638:
217:
24:
2965:
3978:
3649:
3817:
3256:
3205:
2887:
2441:
4159:
3577:
3552:
2606:
2014 IEEE Conference on
Computational Intelligence and Games, CIG 2014, Dortmund, Germany, August 26-29, 2014
1883:
Slany, Wolfgang (2000). "The complexity of graph Ramsey games". In
Marsland, T. Anthony; Frank, Ian (eds.).
4509:
3935:
3689:
3679:
3614:
2847:
2657:
Chang-Ming Xu; Ma, Z.M.; Jun-Jie Tao; Xin-He Xu (2009). "Enhancements of proof number search in connect6".
1478:
43:
Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position),
3729:
3709:
4443:
4194:
4164:
3822:
3664:
3659:
3335:
Alex
Churchill, Stella Biderman, and Austin Herrick (2020). "Magic: the Gathering is Turing Complete".
2208:
1959:
Games of No Chance: Papers from the
Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994
4479:
4402:
4138:
3694:
3619:
3476:
2317:
Kasai, Takumi; Adachi, Akeo; Iwata, Shigeki (1979). "Classes of pebble games and complete problems".
2152:
21:
4494:
4227:
4113:
3910:
3704:
3522:
2961:
2189:
1392:
171:
4297:
2130:
4499:
4098:
4068:
3724:
3512:
3108:
H. Adachi; H. Kamekawa; S. Iwata (1987). "Shogi on n Ă— n board is complete in exponential time".
1951:
67:
of a game is the number of legal game positions reachable from the initial position of the game.
4524:
4504:
4484:
4433:
4103:
4008:
3867:
3812:
3744:
3714:
3634:
3562:
2910:
E. Bonnet; F. Jamain; A. Saffidine (March 25, 2014). "Havannah and TwixT are PSPACE-complete".
2520:
2358:
2206:
1100:
836:
250:
2207:
M.P.D. Schadd; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; M.H.J. Bergsma (2008).
40:
Decision complexity (number of leaf nodes in the smallest decision tree for initial position),
3983:
3968:
3542:
3315:
1277:
4550:
4317:
4302:
4189:
4184:
4088:
4073:
4038:
4003:
3602:
3547:
3469:
2590:
2406:
2338:
2280:
2060:
2033:
1976:
1622:
1244:
783:
609:
86:
is the total number of possible games that can be played: the number of leaf nodes in the
8:
4474:
4093:
4043:
3880:
3807:
3787:
3644:
3527:
3350:
1420:
222:
46:
Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large).
4133:
3295:
2805:
2284:
2064:
1916:
253:
one is considering) algorithm for solving the game; the most common complexity measure (
4453:
4312:
4143:
4123:
3973:
3852:
3757:
3684:
3629:
3415:
3392:
3371:
3336:
3301:
3276:
3055:
2911:
2826:
2797:
2680:
2609:
2546:
2296:
2270:
2086:
1843:
289:
275:
3275:
CDA Evans and Joel David
Hamkins (2014). "Transfinite game values in infinite chess".
3093:
3076:
1935:
1918:
351:) by searching the entire game tree. This places it in the important complexity class
34:
State-space complexity (the number of legal game positions from the initial position),
4438:
4407:
4362:
4257:
4128:
4083:
4058:
3988:
3862:
3792:
3782:
3674:
3624:
3572:
2670:
2581:
2516:
2450:
2397:
2354:
2078:
2019:
1962:
1755:
466:
413:
233:. This concept doesn't apply to particular games, but rather to games that have been
2848:"Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search"
2801:
2772:
2699:
2684:
2300:
2244:
2090:
1847:
4519:
4514:
4448:
4412:
4392:
4352:
4322:
4277:
4232:
4217:
4174:
4028:
3669:
3606:
3592:
3557:
3334:
3088:
2789:
2750:
2711:
2662:
2619:
2576:
2512:
2392:
2326:
2288:
2225:
2161:
2122:
2068:
1930:
1888:
1835:
1826:
Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete)".
1527:
1471:
1355:
1237:
1104:
1088:
1037:
894:
865:
858:
663:
641:
430:
426:
313:
282:
278:
254:
234:
230:
153:
3223:
367:
Due to the large size of game complexities, this table gives the ceiling of their
4417:
4377:
4332:
4247:
4242:
3963:
3915:
3802:
3567:
3507:
3456:
2825:
Donghwi Park (2015). "Space-state complexity of Korean chess and Chinese chess".
2586:
2402:
2334:
2029:
1972:
1887:. Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 186–203.
1695:
1691:
1668:
1442:
1299:
1092:
1059:
1030:
977:
946:
726:
719:
488:
459:
356:
262:
249:
The asymptotic complexity is defined by the most efficient (in terms of whatever
4282:
3391:
Lokshtanov, Daniel; Subercaseaux, Bernardo (May 14, 2022). "Wordle is NP-hard".
2261:
G.I. Bell (2009). "The Shortest Game of Chinese Checkers and Related Problems".
4357:
4347:
4337:
4272:
4262:
4252:
4237:
4033:
4013:
3998:
3993:
3953:
3920:
3905:
3900:
3890:
3699:
3452:
3430:
2499:
2471:
1595:
226:
145:
This is an estimate of the number of positions one would have to evaluate in a
2716:
2666:
2229:
1800:
4539:
4397:
4387:
4342:
4327:
4307:
4078:
4053:
3925:
3895:
3885:
3872:
3777:
3719:
3654:
3587:
3425:
2623:
1892:
1868:
Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)".
111:
2469:
The size of the state space and game tree for chess were first estimated in
2073:
2048:
1694:) is not a proper board game but has a similar game tree, and is studied in
4372:
4367:
4222:
3797:
2793:
2292:
2126:
2113:
2082:
1742:
1531:
551:
4489:
4292:
4287:
4267:
4063:
4048:
3857:
3827:
3762:
3752:
3582:
3517:
3493:
3420:
3370:
Stella Biderman (2020). "Magic: the Gathering is as Hard as Arithmetic".
1664:
1266:
1132:
581:
437:
302:
267:
160:
94:
71:
3461:
3175:
3151:
3040:. Universiteit Maastricht, Institute for Knowledge and Agent Technology.
4118:
3772:
3074:
2773:
Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (March 2004).
2755:
2738:
1839:
1187:
317:
237:
so they can be made arbitrarily large, typically by playing them on an
3241:
3126:
Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis
3060:
2940:(Thesis). Faculty of Humanities and Sciences of Maastricht University.
4023:
3943:
3767:
3051:
2000:
1917:
H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002).
1505:
495:
403:
393:
368:
87:
3020:
Computer Games Workshop, Amsterdam, the Netherlands, 15-17 June 2007
2449:(Ph.D. thesis). Maastricht University, Maastricht, The Netherlands.
2330:
2165:
1754:(Ph.D. thesis). University of Limburg, Maastricht, The Netherlands.
4458:
3958:
3397:
3376:
3341:
2831:
2656:
1690:
Double dummy bridge (i.e., double dummy problems in the context of
1569:
1362:
1158:
753:
3306:
3281:
2916:
2614:
2275:
343:
in a row. It is immediately clear that this game can be solved in
4179:
4169:
3847:
2700:"On the fairness and complexity of generalized k -in-a-row games"
1562:
1270:
1214:
1125:
1000:
923:
915:
886:
806:
776:
617:
312:
The computational complexity of tic-tac-toe depends on how it is
225:
difficulty of a game as it grows arbitrarily large, expressed in
146:
3274:
98:
example, by allowing illegal moves) until it becomes tractable.
2991:(Thesis). Maastricht University, Dept of Knowledge Engineering.
2429:(Thesis). Maastricht University, Dept of Knowledge Engineering.
1805:
1644:
1539:
1385:
1332:
1180:
1007:
813:
605:
574:
518:
352:
344:
309:
are considered the same, there are only 26,830 possible games.
258:
2909:
2343:
Proves completeness of the generalization to arbitrary graphs.
2188:
Bonnet, Edouard; Jamain, Florian; Saffidine, Abdallah (2013).
3948:
1449:
1306:
1066:
697:
670:
525:
296:
3107:
3075:
Hiroyuki Iida; Makoto Sakuta; Jeff Rollason (January 2002).
2150:
J. M. Robson (1984). "N by N checkers is Exptime complete".
1748:
Searching for Solutions in Games and Artificial Intelligence
3149:
1776:"combinatorics - TicTacToe State Space Choose Calculation"
362:
3011:
Kloetzer, Julien; Iida, Hiroyuki; Bouzy, Bruno (2007).
3004:
2873:
Pushy Computing: Complexity Theory and the Game Abalone
149:
search to determine the value of the initial position.
3390:
2853:. Dept of Knowledge Engineering, Maastricht University
138:
of a game is the number of leaf nodes in the smallest
2549:
2523:
2361:
2187:
2013:
174:
3191:
Information Processing; Proceedings of IFIP Congress
3032:
3001:
The lower branching factor is for the second player.
2511:
2419:
3224:"Move Ranking and Evaluation in the Game of Arimaa"
3035:"A Knowledge-Based Approach of the Game of Amazons"
3054:(February 2, 2005). "Amazons is PSPACE-complete".
2975:
2739:"Practical issues in temporal difference learning"
2698:Hsieh, Ming Yu; Tsai, Shi-Chun (October 1, 2007).
2555:
2535:
2373:
2046:
199:
3010:
2603:
2439:
4537:
3206:"Analysis and Implementation of the Game Arimaa"
2950:
2782:International Computer Games Association Journal
2636:
2316:
2047:Jonathan Schaeffer; et al. (July 6, 2007).
339:board with winner being the first player to get
37:Game tree size (total number of possible games),
3369:
3132:(Thesis). Maastricht University. Archived from
2981:
2106:"Game over: Black to play and draw in checkers"
3203:
3026:
2985:Implementing a Computer Player for Carcassonne
2924:
2650:
2630:
2470:
2242:
2190:"On the complexity of trick-taking card games"
53:
3477:
3457:Computational Complexity of Games and Puzzles
3328:
3221:
3189:J. M. Robson (1983). "The complexity of Go".
2930:
2423:Analysis and Implementation of the Game OnTop
2413:
2256:
2254:
2145:
2143:
1912:
1910:
1908:
1906:
1904:
1902:
1867:
1825:
3355:: CS1 maint: multiple names: authors list (
3320:: CS1 maint: multiple names: authors list (
3289:
3248:
3239:
3188:
3156:This paper derives the bounds 48<log(log(
2824:
2659:2009 Chinese Control and Decision Conference
2640:Analysis and Implementation of the game Gipf
2505:
2245:"An Upper Bound on the Complexity of Tablut"
2149:
1863:
1861:
1859:
1857:
1741:
1737:
1735:
355:. With some more work it can be shown to be
3254:
3122:
3050:
2934:Txixt: Theory, Analysis, and Implementation
2463:
2433:
2236:
1733:
1731:
1729:
1727:
1725:
1723:
1721:
1719:
1717:
1715:
210:
3484:
3470:
3233:
3182:
3173:
3160:))<171 on the number of possible games
3116:
2944:
2870:
2864:
2820:
2818:
2768:
2766:
2476:"Programming a Computer for Playing Chess"
2352:
2251:
2200:
2140:
1998:
1899:
1819:
297:Example: tic-tac-toe (noughts and crosses)
3491:
3441:list of PSPACE-complete games and puzzles
3396:
3375:
3340:
3305:
3280:
3167:
3092:
3059:
2915:
2830:
2754:
2715:
2697:
2613:
2580:
2568:Journal of Combinatorial Theory, Series A
2396:
2312:
2310:
2274:
2260:
2103:
2072:
1934:
1854:
58:
3363:
1712:
109:The next two measures use the idea of a
3242:"A Look at the Arimaa Branching Factor"
3197:
2839:
2815:
2763:
2736:
2217:New Mathematics and Natural Computation
129:
90:rooted at the game's initial position.
70:When this is too hard to calculate, an
4538:
3215:
2597:
2353:Iwata, Shigeki; Kasai, Takumi (1994).
2307:
118:
3465:
3436:list of NP-complete games and puzzles
3298:Conference on Computability in Europe
3150:John Tromp; Gunnar Farnebäck (2007).
3013:"The Monte-Carlo approach in Amazons"
2209:"Best Play in Fanorona leads to Draw"
1949:
1919:"Games solved: Now and in the future"
1882:
1617:UnÂknown, but mate-in-n is decidable
363:Complexities of some well-known games
3143:
2960:. Computer Science (B.Sc. thesis).
2888:"Creating a Havannah Playing Agent"
2885:
2543:chess requires time exponential in
1957:. In Nowakowski, Richard J. (ed.).
16:Notion in combinatorial game theory
13:
3533:First-player and second-player win
2845:
2517:"Computing a perfect strategy for
1989:See van den Herik et al for rules.
14:
4562:
3446:
1952:"Pentominoes: a first player win"
1798:
642:English draughts (8x8) (checkers)
316:. A natural generalization is to
104:
77:
3640:Coalition-proof Nash equilibrium
2646:(Thesis). Maastricht University.
2443:Informed Search in Complex Games
2001:"John's Connect Four Playground"
375:Note: ordered by game tree size
3384:
3268:
3101:
3068:
3044:
2995:
2903:
2879:
2737:Tesauro, Gerald (May 1, 1992).
2730:
2691:
2346:
2196:. IJCAI/AAAI. pp. 482–488.
2181:
2172:
2097:
2040:
2007:
1992:
1684:
3650:Evolutionarily stable strategy
3176:"Number of legal Go positions"
2515:; Lichtenstein, David (1981).
1983:
1943:
1876:
1792:
1768:
837:International draughts (10x10)
286:precisely the tree-complexity.
159:to the power of the number of
1:
3578:Simultaneous action selection
3094:10.1016/S0004-3702(01)00157-6
3033:P. P. L. M. Hensgens (2001).
2951:Lisa Glendenning (May 2005).
2420:Robert Briesemeister (2009).
2192:. In Rossi, Francesca (ed.).
1936:10.1016/S0004-3702(01)00152-7
1799:T, Brian (October 20, 2018).
1705:
200:{\displaystyle GTC\geq b^{d}}
4510:List of games in game theory
3690:Quantal response equilibrium
3680:Perfect Bayesian equilibrium
3615:Bayes correlated equilibrium
3258:Competitive Play in Stratego
2871:Kopczynski, Jacob S (2014).
2704:Theoretical Computer Science
2582:10.1016/0097-3165(81)90016-9
2398:10.1016/0304-3975(94)90131-7
2385:Theoretical Computer Science
2104:Schaeffer, Jonathan (2007).
7:
3979:Optional prisoner's dilemma
3710:Self-confirming equilibrium
3409:
54:Measures of game complexity
10:
4567:
4444:Principal variation search
4160:Aumann's agreement theorem
3823:Strategy-stealing argument
3735:Trembling hand equilibrium
3665:Markov perfect equilibrium
3660:Mertens-stable equilibrium
2440:Mark H.M. Winands (2004).
1950:Orman, Hilarie K. (1996).
1801:"Btsan/generate_tictactoe"
1780:Mathematics Stack Exchange
1415:Generalization is unclear
1209:Generalization is unclear
747:
692:Generalization is unclear
546:Generalization is unclear
4546:Combinatorial game theory
4480:Combinatorial game theory
4467:
4426:
4208:
4152:
4139:Princess and monster game
3934:
3836:
3743:
3695:Quasi-perfect equilibrium
3620:Bayesian Nash equilibrium
3601:
3500:
2717:10.1016/j.tcs.2007.05.031
2667:10.1109/CCDC.2009.5191963
2637:Diederik Wentink (2001).
2536:{\displaystyle n\times n}
2381:board is PSPACE-complete"
2374:{\displaystyle n\times n}
2319:SIAM Journal on Computing
2230:10.1142/S1793005708001124
2153:SIAM Journal on Computing
22:Combinatorial game theory
4495:Evolutionary game theory
4228:Antoine Augustin Cournot
4114:Guess 2/3 of the average
3911:Strictly determined game
3705:Satisfaction equilibrium
3523:Escalation of commitment
2982:Cathleen Heyden (2009).
2962:University of New Mexico
2775:"Computer Chinese Chess"
2624:10.1109/CIG.2014.6932866
2355:"The Othello game on an
2178:See Allis 1994 for rules
1893:10.1007/3-540-45579-5_12
1677:
221:of a game describes the
218:computational complexity
211:Computational complexity
166:in an average game, or:
4500:Glossary of game theory
4099:Stackelberg competition
3725:Strong Nash equilibrium
3204:Christ-Jan Cox (2006).
3081:Artificial Intelligence
2875:(Thesis). Reed College.
2726:– via dl.acm.org.
2243:Andrea Galassi (2018).
2074:10.1126/science.1144079
1923:Artificial Intelligence
612:for certain dimensions
390:State-space complexity
4525:Tragedy of the commons
4505:List of game theorists
4485:Confrontation analysis
4195:Sprague–Grundy theorem
3715:Sequential equilibrium
3635:Correlated equilibrium
3222:David Jian Wu (2011).
2931:Kevin Moesker (2009).
2794:10.3233/ICG-2004-27102
2608:. IEEE. pp. 1–8.
2557:
2537:
2483:Philosophical Magazine
2375:
2293:10.1515/INTEG.2009.003
2127:10.3233/ICG-2007-30402
251:computational resource
229:or as membership in a
201:
65:state-space complexity
59:State-space complexity
4298:Jean-François Mertens
3264:(Thesis). Maastricht.
3240:Brian Haskin (2006).
3152:"Combinatorics of Go"
2558:
2538:
2489:(314). Archived from
2376:
1671:with parametization.
953:OnTop (2p base game)
400:Game-tree complexity
202:
4427:Search optimizations
4303:Jennifer Tour Chayes
4190:Revelation principle
4185:Purification theorem
4124:Nash bargaining game
4089:Bertrand competition
4074:El Farol Bar problem
4039:Electronic mail game
4004:Lewis signaling game
3548:Hierarchy of beliefs
3255:A.F.C. Arts (2010).
3123:F.C. Schadd (2009).
2547:
2521:
2513:Fraenkel, Aviezri S.
2359:
2049:"Checkers is Solved"
1623:Magic: The Gathering
1093:50-move drawing rule
410:Average game length
172:
136:game-tree complexity
130:Game-tree complexity
4475:Bounded rationality
4094:Cournot competition
4044:Rock paper scissors
4019:Battle of the sexes
4009:Volunteer's dilemma
3881:Perfect information
3808:Dominant strategies
3645:Epsilon-equilibrium
3528:Extensive-form game
3193:. pp. 413–417.
3174:John Tromp (2016).
3112:. J70-D: 1843–1852.
3022:. pp. 185–192.
2285:2008arXiv0803.1245B
2065:2007Sci...317.1518S
2059:(5844): 1518–1522.
1999:John Tromp (2010).
1010:(15x15, freestyle)
727:Double dummy bridge
124:Decision complexity
119:Decision complexity
4454:Paranoid algorithm
4434:Alpha–beta pruning
4313:John Maynard Smith
4144:Rendezvous problem
3984:Traveler's dilemma
3974:Gift-exchange game
3969:Prisoner's dilemma
3886:Large Poisson game
3853:Bargaining problem
3758:Backward induction
3730:Subgame perfection
3685:Proper equilibrium
3416:Go and mathematics
2954:Mastering Quoridor
2756:10.1007/BF00992697
2553:
2533:
2371:
1840:10.1007/bf00288536
1354:?, believed to be
1236:?, believed to be
290:Backward induction
197:
30:in several ways:
4533:
4532:
4439:Aspiration window
4408:Suzanne Scotchmer
4363:Oskar Morgenstern
4258:Donald B. Gillies
4200:Zermelo's theorem
4129:Induction puzzles
4084:Fair cake-cutting
4059:Public goods game
3989:Coordination game
3863:Intransitive game
3793:Forward induction
3675:Pareto efficiency
3655:Gibbs equilibrium
3625:Berge equilibrium
3573:Simultaneous game
2676:978-1-4244-2722-2
2556:{\displaystyle n}
1675:
1674:
784:Nine men's morris
420:Branching factor
4558:
4520:Topological game
4515:No-win situation
4413:Thomas Schelling
4393:Robert B. Wilson
4353:Merrill M. Flood
4323:John von Neumann
4233:Ariel Rubinstein
4218:Albert W. Tucker
4069:War of attrition
4029:Matching pennies
3670:Nash equilibrium
3593:Mechanism design
3558:Normal-form game
3513:Cooperative game
3486:
3479:
3472:
3463:
3462:
3403:
3402:
3400:
3388:
3382:
3381:
3379:
3367:
3361:
3360:
3354:
3346:
3344:
3332:
3326:
3325:
3319:
3311:
3309:
3293:
3287:
3286:
3284:
3272:
3266:
3265:
3263:
3252:
3246:
3245:
3237:
3231:
3230:
3228:
3219:
3213:
3212:
3210:
3201:
3195:
3194:
3186:
3180:
3179:
3171:
3165:
3155:
3147:
3141:
3140:
3138:
3131:
3120:
3114:
3113:
3105:
3099:
3098:
3096:
3087:(1–2): 121–144.
3077:"Computer shogi"
3072:
3066:
3065:
3063:
3048:
3042:
3041:
3039:
3030:
3024:
3023:
3017:
3008:
3002:
2999:
2993:
2992:
2990:
2979:
2973:
2972:
2970:
2964:. Archived from
2959:
2948:
2942:
2941:
2939:
2928:
2922:
2921:
2919:
2907:
2901:
2900:
2898:
2897:
2892:
2883:
2877:
2876:
2868:
2862:
2861:
2859:
2858:
2852:
2846:Chorus, Pascal.
2843:
2837:
2836:
2834:
2822:
2813:
2812:
2810:
2804:. Archived from
2779:
2770:
2761:
2760:
2758:
2749:(3–4): 257–277.
2743:Machine Learning
2734:
2728:
2727:
2725:
2724:
2719:
2695:
2689:
2688:
2661:. p. 4525.
2654:
2648:
2647:
2645:
2634:
2628:
2627:
2617:
2601:
2595:
2594:
2584:
2562:
2560:
2559:
2554:
2542:
2540:
2539:
2534:
2509:
2503:
2497:
2495:
2480:
2467:
2461:
2460:
2448:
2437:
2431:
2430:
2428:
2417:
2411:
2410:
2400:
2380:
2378:
2377:
2372:
2350:
2344:
2342:
2314:
2305:
2304:
2278:
2258:
2249:
2248:
2240:
2234:
2233:
2213:
2204:
2198:
2197:
2185:
2179:
2176:
2170:
2169:
2147:
2138:
2137:
2135:
2129:. Archived from
2110:
2101:
2095:
2094:
2076:
2044:
2038:
2037:
2011:
2005:
2004:
1996:
1990:
1987:
1981:
1980:
1956:
1947:
1941:
1940:
1938:
1929:(1–2): 277–311.
1914:
1897:
1896:
1880:
1874:
1873:
1865:
1852:
1851:
1828:Acta Informatica
1823:
1817:
1816:
1814:
1813:
1796:
1790:
1789:
1787:
1786:
1772:
1766:
1765:
1753:
1739:
1699:
1688:
1528:EXPTIME-complete
1472:EXPTIME-complete
1356:EXPTIME-complete
1238:EXPTIME-complete
1089:EXPTIME-complete
895:Chinese checkers
866:Chinese checkers
859:EXPTIME-complete
748:PSPACE-complete
664:EXPTIME-complete
431:generalized game
427:Complexity class
378:
377:
283:computation time
279:minimax strategy
255:computation time
231:complexity class
206:
204:
203:
198:
196:
195:
154:branching factor
4566:
4565:
4561:
4560:
4559:
4557:
4556:
4555:
4536:
4535:
4534:
4529:
4463:
4449:max^n algorithm
4422:
4418:William Vickrey
4378:Reinhard Selten
4333:Kenneth Binmore
4248:David K. Levine
4243:Daniel Kahneman
4210:
4204:
4180:Negamax theorem
4170:Minimax theorem
4148:
4109:Diner's dilemma
3964:All-pay auction
3930:
3916:Stochastic game
3868:Mean-field game
3839:
3832:
3803:Markov strategy
3739:
3605:
3597:
3568:Sequential game
3553:Information set
3538:Game complexity
3508:Congestion game
3496:
3490:
3449:
3412:
3407:
3406:
3389:
3385:
3368:
3364:
3348:
3347:
3333:
3329:
3313:
3312:
3294:
3290:
3273:
3269:
3261:
3253:
3249:
3238:
3234:
3226:
3220:
3216:
3208:
3202:
3198:
3187:
3183:
3172:
3168:
3148:
3144:
3136:
3129:
3121:
3117:
3106:
3102:
3073:
3069:
3049:
3045:
3037:
3031:
3027:
3015:
3009:
3005:
3000:
2996:
2988:
2980:
2976:
2968:
2957:
2949:
2945:
2937:
2929:
2925:
2908:
2904:
2895:
2893:
2890:
2884:
2880:
2869:
2865:
2856:
2854:
2850:
2844:
2840:
2823:
2816:
2808:
2777:
2771:
2764:
2735:
2731:
2722:
2720:
2710:(1–3): 88–100.
2696:
2692:
2677:
2655:
2651:
2643:
2635:
2631:
2602:
2598:
2548:
2545:
2544:
2522:
2519:
2518:
2510:
2506:
2493:
2478:
2468:
2464:
2457:
2446:
2438:
2434:
2426:
2418:
2414:
2360:
2357:
2356:
2351:
2347:
2331:10.1137/0208046
2315:
2308:
2259:
2252:
2241:
2237:
2211:
2205:
2201:
2186:
2182:
2177:
2173:
2166:10.1137/0213018
2148:
2141:
2133:
2108:
2102:
2098:
2045:
2041:
2026:
2012:
2008:
1997:
1993:
1988:
1984:
1969:
1954:
1948:
1944:
1915:
1900:
1881:
1877:
1866:
1855:
1824:
1820:
1811:
1809:
1797:
1793:
1784:
1782:
1774:
1773:
1769:
1762:
1751:
1740:
1713:
1708:
1703:
1702:
1696:computer bridge
1692:contract bridge
1689:
1685:
1680:
1669:PSPACE-complete
1479:Thurn and Taxis
1443:PSPACE-complete
1421:Amazons (10x10)
1395:(2p base game)
1300:PSPACE-complete
1181:PSPACE-complete
1060:PSPACE-complete
1031:PSPACE-complete
978:Lines of Action
947:PSPACE-complete
720:PSPACE-complete
489:PSPACE-complete
460:PSPACE-complete
372:numbers shown.
365:
357:PSPACE-complete
331:: played on an
299:
263:computer memory
213:
191:
187:
173:
170:
169:
132:
121:
107:
80:
61:
56:
28:game complexity
17:
12:
11:
5:
4564:
4554:
4553:
4548:
4531:
4530:
4528:
4527:
4522:
4517:
4512:
4507:
4502:
4497:
4492:
4487:
4482:
4477:
4471:
4469:
4465:
4464:
4462:
4461:
4456:
4451:
4446:
4441:
4436:
4430:
4428:
4424:
4423:
4421:
4420:
4415:
4410:
4405:
4400:
4395:
4390:
4385:
4383:Robert Axelrod
4380:
4375:
4370:
4365:
4360:
4358:Olga Bondareva
4355:
4350:
4348:Melvin Dresher
4345:
4340:
4338:Leonid Hurwicz
4335:
4330:
4325:
4320:
4315:
4310:
4305:
4300:
4295:
4290:
4285:
4280:
4275:
4273:Harold W. Kuhn
4270:
4265:
4263:Drew Fudenberg
4260:
4255:
4253:David M. Kreps
4250:
4245:
4240:
4238:Claude Shannon
4235:
4230:
4225:
4220:
4214:
4212:
4206:
4205:
4203:
4202:
4197:
4192:
4187:
4182:
4177:
4175:Nash's theorem
4172:
4167:
4162:
4156:
4154:
4150:
4149:
4147:
4146:
4141:
4136:
4131:
4126:
4121:
4116:
4111:
4106:
4101:
4096:
4091:
4086:
4081:
4076:
4071:
4066:
4061:
4056:
4051:
4046:
4041:
4036:
4034:Ultimatum game
4031:
4026:
4021:
4016:
4014:Dollar auction
4011:
4006:
4001:
3999:Centipede game
3996:
3991:
3986:
3981:
3976:
3971:
3966:
3961:
3956:
3954:Infinite chess
3951:
3946:
3940:
3938:
3932:
3931:
3929:
3928:
3923:
3921:Symmetric game
3918:
3913:
3908:
3906:Signaling game
3903:
3901:Screening game
3898:
3893:
3891:Potential game
3888:
3883:
3878:
3870:
3865:
3860:
3855:
3850:
3844:
3842:
3834:
3833:
3831:
3830:
3825:
3820:
3818:Mixed strategy
3815:
3810:
3805:
3800:
3795:
3790:
3785:
3780:
3775:
3770:
3765:
3760:
3755:
3749:
3747:
3741:
3740:
3738:
3737:
3732:
3727:
3722:
3717:
3712:
3707:
3702:
3700:Risk dominance
3697:
3692:
3687:
3682:
3677:
3672:
3667:
3662:
3657:
3652:
3647:
3642:
3637:
3632:
3627:
3622:
3617:
3611:
3609:
3599:
3598:
3596:
3595:
3590:
3585:
3580:
3575:
3570:
3565:
3560:
3555:
3550:
3545:
3543:Graphical game
3540:
3535:
3530:
3525:
3520:
3515:
3510:
3504:
3502:
3498:
3497:
3489:
3488:
3481:
3474:
3466:
3460:
3459:
3453:David Eppstein
3448:
3447:External links
3445:
3444:
3443:
3438:
3433:
3431:Shannon number
3428:
3423:
3418:
3411:
3408:
3405:
3404:
3383:
3362:
3327:
3288:
3267:
3247:
3232:
3214:
3196:
3181:
3166:
3142:
3139:on 2021-01-14.
3115:
3100:
3067:
3043:
3025:
3003:
2994:
2974:
2971:on 2012-03-15.
2943:
2923:
2902:
2878:
2863:
2838:
2814:
2811:on 2007-06-14.
2762:
2729:
2690:
2675:
2649:
2629:
2596:
2575:(2): 199–214.
2552:
2532:
2529:
2526:
2504:
2500:Shannon number
2496:on 2010-07-06.
2472:Claude Shannon
2462:
2455:
2432:
2412:
2391:(2): 329–340.
2370:
2367:
2364:
2345:
2325:(4): 574–586.
2306:
2250:
2235:
2224:(3): 369–387.
2199:
2180:
2171:
2160:(2): 252–267.
2139:
2136:on 2016-04-03.
2121:(4): 187–197.
2096:
2039:
2024:
2006:
1991:
1982:
1967:
1942:
1898:
1875:
1872:(15): 167–191.
1853:
1818:
1791:
1767:
1760:
1710:
1709:
1707:
1704:
1701:
1700:
1682:
1681:
1679:
1676:
1673:
1672:
1662:
1660:
1658:
1655:
1653:
1650:
1647:
1641:
1640:
1637:
1635:
1633:
1631:
1629:
1627:
1625:
1619:
1618:
1615:
1613:
1610:
1607:
1604:
1601:
1598:
1596:Infinite chess
1592:
1591:
1589:
1587:
1584:
1581:
1578:
1575:
1572:
1566:
1565:
1559:
1557:
1554:
1551:
1548:
1545:
1542:
1536:
1535:
1525:
1523:
1520:
1517:
1514:
1511:
1508:
1502:
1501:
1499:
1497:
1494:
1491:
1488:
1485:
1482:
1475:
1474:
1469:
1467:
1464:
1461:
1458:
1455:
1452:
1446:
1445:
1440:
1438:
1435:
1432:
1429:
1426:
1423:
1417:
1416:
1413:
1411:
1408:
1405:
1402:
1399:
1396:
1389:
1388:
1382:
1380:
1377:
1374:
1371:
1368:
1365:
1359:
1358:
1352:
1350:
1347:
1344:
1341:
1338:
1335:
1329:
1328:
1326:
1324:
1321:
1318:
1315:
1312:
1309:
1303:
1302:
1297:
1295:
1292:
1289:
1286:
1283:
1280:
1274:
1273:
1264:
1262:
1259:
1256:
1253:
1250:
1247:
1241:
1240:
1234:
1232:
1229:
1226:
1223:
1220:
1217:
1211:
1210:
1207:
1205:
1202:
1199:
1196:
1193:
1190:
1184:
1183:
1178:
1176:
1173:
1170:
1167:
1164:
1161:
1155:
1154:
1152:
1150:
1147:
1144:
1141:
1138:
1135:
1129:
1128:
1123:
1121:
1118:
1116:
1114:
1111:
1108:
1097:
1096:
1086:
1084:
1081:
1078:
1075:
1072:
1069:
1063:
1062:
1057:
1055:
1052:
1049:
1046:
1043:
1040:
1034:
1033:
1028:
1026:
1023:
1020:
1017:
1014:
1011:
1004:
1003:
997:
995:
992:
989:
986:
983:
980:
974:
973:
971:
969:
966:
963:
960:
957:
954:
950:
949:
944:
942:
939:
936:
933:
930:
927:
920:
919:
913:
911:
908:
906:
904:
901:
898:
891:
890:
884:
882:
879:
877:
875:
872:
869:
862:
861:
856:
854:
851:
848:
845:
842:
839:
833:
832:
830:
828:
826:
824:
822:
819:
816:
810:
809:
803:
801:
798:
795:
792:
789:
786:
780:
779:
773:
771:
768:
765:
762:
759:
756:
750:
749:
746:
744:
741:
738:
735:
732:
729:
723:
722:
717:
715:
712:
709:
706:
703:
700:
694:
693:
690:
688:
685:
682:
679:
676:
673:
667:
666:
661:
659:
656:
653:
650:
647:
644:
638:
637:
635:
633:
631:
629:
626:
623:
620:
614:
613:
602:
600:
597:
594:
591:
588:
585:
578:
577:
571:
569:
566:
563:
560:
557:
554:
548:
547:
544:
542:
539:
537:
534:
531:
528:
522:
521:
515:
513:
510:
507:
504:
501:
498:
492:
491:
486:
484:
481:
478:
475:
472:
469:
463:
462:
457:
455:
452:
449:
446:
443:
440:
434:
433:
424:
421:
418:
408:
398:
388:
382:
364:
361:
298:
295:
294:
293:
287:
227:big O notation
212:
209:
194:
190:
186:
183:
180:
177:
131:
128:
120:
117:
106:
105:Decision trees
103:
84:game tree size
79:
78:Game tree size
76:
60:
57:
55:
52:
48:
47:
44:
41:
38:
35:
15:
9:
6:
4:
3:
2:
4563:
4552:
4549:
4547:
4544:
4543:
4541:
4526:
4523:
4521:
4518:
4516:
4513:
4511:
4508:
4506:
4503:
4501:
4498:
4496:
4493:
4491:
4488:
4486:
4483:
4481:
4478:
4476:
4473:
4472:
4470:
4468:Miscellaneous
4466:
4460:
4457:
4455:
4452:
4450:
4447:
4445:
4442:
4440:
4437:
4435:
4432:
4431:
4429:
4425:
4419:
4416:
4414:
4411:
4409:
4406:
4404:
4403:Samuel Bowles
4401:
4399:
4398:Roger Myerson
4396:
4394:
4391:
4389:
4388:Robert Aumann
4386:
4384:
4381:
4379:
4376:
4374:
4371:
4369:
4366:
4364:
4361:
4359:
4356:
4354:
4351:
4349:
4346:
4344:
4343:Lloyd Shapley
4341:
4339:
4336:
4334:
4331:
4329:
4328:Kenneth Arrow
4326:
4324:
4321:
4319:
4316:
4314:
4311:
4309:
4308:John Harsanyi
4306:
4304:
4301:
4299:
4296:
4294:
4291:
4289:
4286:
4284:
4281:
4279:
4278:Herbert Simon
4276:
4274:
4271:
4269:
4266:
4264:
4261:
4259:
4256:
4254:
4251:
4249:
4246:
4244:
4241:
4239:
4236:
4234:
4231:
4229:
4226:
4224:
4221:
4219:
4216:
4215:
4213:
4207:
4201:
4198:
4196:
4193:
4191:
4188:
4186:
4183:
4181:
4178:
4176:
4173:
4171:
4168:
4166:
4163:
4161:
4158:
4157:
4155:
4151:
4145:
4142:
4140:
4137:
4135:
4132:
4130:
4127:
4125:
4122:
4120:
4117:
4115:
4112:
4110:
4107:
4105:
4102:
4100:
4097:
4095:
4092:
4090:
4087:
4085:
4082:
4080:
4079:Fair division
4077:
4075:
4072:
4070:
4067:
4065:
4062:
4060:
4057:
4055:
4054:Dictator game
4052:
4050:
4047:
4045:
4042:
4040:
4037:
4035:
4032:
4030:
4027:
4025:
4022:
4020:
4017:
4015:
4012:
4010:
4007:
4005:
4002:
4000:
3997:
3995:
3992:
3990:
3987:
3985:
3982:
3980:
3977:
3975:
3972:
3970:
3967:
3965:
3962:
3960:
3957:
3955:
3952:
3950:
3947:
3945:
3942:
3941:
3939:
3937:
3933:
3927:
3926:Zero-sum game
3924:
3922:
3919:
3917:
3914:
3912:
3909:
3907:
3904:
3902:
3899:
3897:
3896:Repeated game
3894:
3892:
3889:
3887:
3884:
3882:
3879:
3877:
3875:
3871:
3869:
3866:
3864:
3861:
3859:
3856:
3854:
3851:
3849:
3846:
3845:
3843:
3841:
3835:
3829:
3826:
3824:
3821:
3819:
3816:
3814:
3813:Pure strategy
3811:
3809:
3806:
3804:
3801:
3799:
3796:
3794:
3791:
3789:
3786:
3784:
3781:
3779:
3778:De-escalation
3776:
3774:
3771:
3769:
3766:
3764:
3761:
3759:
3756:
3754:
3751:
3750:
3748:
3746:
3742:
3736:
3733:
3731:
3728:
3726:
3723:
3721:
3720:Shapley value
3718:
3716:
3713:
3711:
3708:
3706:
3703:
3701:
3698:
3696:
3693:
3691:
3688:
3686:
3683:
3681:
3678:
3676:
3673:
3671:
3668:
3666:
3663:
3661:
3658:
3656:
3653:
3651:
3648:
3646:
3643:
3641:
3638:
3636:
3633:
3631:
3628:
3626:
3623:
3621:
3618:
3616:
3613:
3612:
3610:
3608:
3604:
3600:
3594:
3591:
3589:
3588:Succinct game
3586:
3584:
3581:
3579:
3576:
3574:
3571:
3569:
3566:
3564:
3561:
3559:
3556:
3554:
3551:
3549:
3546:
3544:
3541:
3539:
3536:
3534:
3531:
3529:
3526:
3524:
3521:
3519:
3516:
3514:
3511:
3509:
3506:
3505:
3503:
3499:
3495:
3487:
3482:
3480:
3475:
3473:
3468:
3467:
3464:
3458:
3454:
3451:
3450:
3442:
3439:
3437:
3434:
3432:
3429:
3427:
3426:Solving chess
3424:
3422:
3419:
3417:
3414:
3413:
3399:
3394:
3387:
3378:
3373:
3366:
3358:
3352:
3343:
3338:
3331:
3323:
3317:
3308:
3303:
3299:
3292:
3283:
3278:
3271:
3260:
3259:
3251:
3243:
3236:
3225:
3218:
3207:
3200:
3192:
3185:
3177:
3170:
3163:
3159:
3153:
3146:
3135:
3128:
3127:
3119:
3111:
3104:
3095:
3090:
3086:
3082:
3078:
3071:
3062:
3061:cs.CC/0502013
3057:
3053:
3047:
3036:
3029:
3021:
3014:
3007:
2998:
2987:
2986:
2978:
2967:
2963:
2956:
2955:
2947:
2936:
2935:
2927:
2918:
2913:
2906:
2889:
2882:
2874:
2867:
2849:
2842:
2833:
2828:
2821:
2819:
2807:
2803:
2799:
2795:
2791:
2787:
2783:
2776:
2769:
2767:
2757:
2752:
2748:
2744:
2740:
2733:
2718:
2713:
2709:
2705:
2701:
2694:
2686:
2682:
2678:
2672:
2668:
2664:
2660:
2653:
2642:
2641:
2633:
2625:
2621:
2616:
2611:
2607:
2600:
2592:
2588:
2583:
2578:
2574:
2570:
2569:
2564:
2550:
2530:
2527:
2524:
2514:
2508:
2501:
2492:
2488:
2484:
2477:
2473:
2466:
2458:
2456:90-5278-429-9
2452:
2445:
2444:
2436:
2425:
2424:
2416:
2408:
2404:
2399:
2394:
2390:
2386:
2382:
2368:
2365:
2362:
2349:
2340:
2336:
2332:
2328:
2324:
2320:
2313:
2311:
2302:
2298:
2294:
2290:
2286:
2282:
2277:
2272:
2268:
2264:
2257:
2255:
2246:
2239:
2231:
2227:
2223:
2219:
2218:
2210:
2203:
2195:
2191:
2184:
2175:
2167:
2163:
2159:
2155:
2154:
2146:
2144:
2132:
2128:
2124:
2120:
2116:
2115:
2107:
2100:
2092:
2088:
2084:
2080:
2075:
2070:
2066:
2062:
2058:
2054:
2050:
2043:
2035:
2031:
2027:
2025:0-521-80832-4
2021:
2017:
2010:
2002:
1995:
1986:
1978:
1974:
1970:
1968:0-521-57411-0
1964:
1960:
1953:
1946:
1937:
1932:
1928:
1924:
1920:
1913:
1911:
1909:
1907:
1905:
1903:
1894:
1890:
1886:
1879:
1871:
1864:
1862:
1860:
1858:
1849:
1845:
1841:
1837:
1833:
1829:
1822:
1808:
1807:
1802:
1795:
1781:
1777:
1771:
1763:
1761:90-900748-8-0
1757:
1750:
1749:
1744:
1738:
1736:
1734:
1732:
1730:
1728:
1726:
1724:
1722:
1720:
1718:
1716:
1711:
1697:
1693:
1687:
1683:
1670:
1667:, unknown if
1666:
1663:
1661:
1659:
1656:
1654:
1651:
1648:
1646:
1643:
1642:
1638:
1636:
1634:
1632:
1630:
1628:
1626:
1624:
1621:
1620:
1616:
1614:
1611:
1608:
1605:
1602:
1599:
1597:
1594:
1593:
1590:
1588:
1585:
1582:
1579:
1576:
1573:
1571:
1568:
1567:
1564:
1560:
1558:
1555:
1552:
1549:
1546:
1543:
1541:
1538:
1537:
1533:
1530:(without the
1529:
1526:
1524:
1521:
1518:
1515:
1512:
1509:
1507:
1504:
1503:
1500:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1476:
1473:
1470:
1468:
1465:
1462:
1459:
1456:
1453:
1451:
1448:
1447:
1444:
1441:
1439:
1436:
1433:
1430:
1427:
1424:
1422:
1419:
1418:
1414:
1412:
1409:
1406:
1403:
1400:
1397:
1394:
1391:
1390:
1387:
1383:
1381:
1378:
1375:
1372:
1369:
1366:
1364:
1361:
1360:
1357:
1353:
1351:
1348:
1345:
1342:
1339:
1336:
1334:
1331:
1330:
1327:
1325:
1322:
1319:
1316:
1313:
1310:
1308:
1305:
1304:
1301:
1298:
1296:
1293:
1290:
1287:
1284:
1281:
1279:
1276:
1275:
1272:
1268:
1265:
1263:
1260:
1257:
1254:
1251:
1248:
1246:
1243:
1242:
1239:
1235:
1233:
1230:
1227:
1224:
1221:
1218:
1216:
1213:
1212:
1208:
1206:
1203:
1200:
1197:
1194:
1191:
1189:
1186:
1185:
1182:
1179:
1177:
1174:
1171:
1168:
1165:
1162:
1160:
1157:
1156:
1153:
1151:
1148:
1145:
1142:
1139:
1136:
1134:
1131:
1130:
1127:
1124:
1122:
1119:
1117:
1115:
1112:
1109:
1106:
1102:
1099:
1098:
1094:
1090:
1087:
1085:
1082:
1079:
1076:
1073:
1070:
1068:
1065:
1064:
1061:
1058:
1056:
1053:
1050:
1047:
1044:
1041:
1039:
1036:
1035:
1032:
1029:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1005:
1002:
998:
996:
993:
990:
987:
984:
981:
979:
976:
975:
972:
970:
967:
964:
961:
958:
955:
952:
951:
948:
945:
943:
940:
937:
934:
931:
928:
925:
922:
921:
917:
914:
912:
909:
907:
905:
902:
899:
896:
893:
892:
888:
885:
883:
880:
878:
876:
873:
870:
867:
864:
863:
860:
857:
855:
852:
849:
846:
843:
840:
838:
835:
834:
831:
829:
827:
825:
823:
820:
817:
815:
812:
811:
808:
804:
802:
799:
796:
793:
790:
787:
785:
782:
781:
778:
774:
772:
769:
766:
763:
760:
757:
755:
752:
751:
745:
742:
739:
736:
733:
730:
728:
725:
724:
721:
718:
716:
713:
710:
707:
704:
701:
699:
696:
695:
691:
689:
686:
683:
680:
677:
674:
672:
669:
668:
665:
662:
660:
657:
654:
651:
648:
645:
643:
640:
639:
636:
634:
632:
630:
627:
624:
621:
619:
616:
615:
611:
607:
603:
601:
598:
595:
592:
589:
586:
583:
580:
579:
576:
572:
570:
567:
564:
561:
558:
555:
553:
550:
549:
545:
543:
540:
538:
535:
532:
529:
527:
524:
523:
520:
516:
514:
511:
508:
505:
502:
499:
497:
494:
493:
490:
487:
485:
482:
479:
476:
473:
470:
468:
465:
464:
461:
458:
456:
453:
450:
447:
444:
441:
439:
436:
435:
432:
428:
425:
422:
419:
417:
415:
409:
407:
405:
399:
397:
395:
389:
387:
383:
380:
379:
376:
373:
370:
360:
358:
354:
350:
346:
342:
338:
334:
330:
328:
324:
320:
315:
310:
306:
304:
291:
288:
284:
280:
277:
273:
272:
271:
269:
264:
260:
256:
252:
247:
244:
240:
236:
232:
228:
224:
220:
219:
208:
192:
188:
184:
181:
178:
175:
167:
165:
162:
158:
155:
150:
148:
143:
141:
137:
127:
125:
116:
114:
113:
112:decision tree
102:
99:
96:
91:
89:
85:
75:
73:
68:
66:
51:
45:
42:
39:
36:
33:
32:
31:
29:
26:
23:
19:
4373:Peyton Young
4368:Paul Milgrom
4283:Hervé Moulin
4223:Amos Tversky
4165:Folk theorem
3876:-player game
3873:
3798:Grim trigger
3537:
3386:
3365:
3330:
3316:cite journal
3297:
3291:
3270:
3257:
3250:
3235:
3217:
3199:
3190:
3184:
3169:
3161:
3157:
3145:
3134:the original
3125:
3118:
3110:Trans. IEICE
3109:
3103:
3084:
3080:
3070:
3046:
3028:
3019:
3006:
2997:
2984:
2977:
2966:the original
2953:
2946:
2933:
2926:
2905:
2894:. Retrieved
2886:Joosten, B.
2881:
2872:
2866:
2855:. Retrieved
2841:
2806:the original
2785:
2781:
2746:
2742:
2732:
2721:. Retrieved
2707:
2703:
2693:
2658:
2652:
2639:
2632:
2605:
2599:
2572:
2566:
2507:
2491:the original
2486:
2482:
2465:
2442:
2435:
2422:
2415:
2388:
2384:
2348:
2322:
2318:
2266:
2262:
2238:
2221:
2215:
2202:
2193:
2183:
2174:
2157:
2151:
2131:the original
2118:
2114:ICGA Journal
2112:
2099:
2056:
2052:
2042:
2015:
2009:
1994:
1985:
1958:
1945:
1926:
1922:
1884:
1878:
1869:
1834:(1): 59–66.
1831:
1827:
1821:
1810:. Retrieved
1804:
1794:
1783:. Retrieved
1779:
1770:
1747:
1743:Victor Allis
1686:
1532:superko rule
552:Connect Four
429:of suitable
411:
406:to base 10)
401:
396:to base 10)
391:
386:(positions)
385:
374:
366:
348:
340:
336:
332:
326:
322:
318:
311:
307:
300:
248:
242:
238:
216:
214:
168:
163:
156:
151:
144:
139:
135:
133:
123:
122:
110:
108:
100:
92:
83:
81:
69:
64:
62:
49:
27:
20:
18:
4551:Game theory
4490:Coopetition
4293:Jean Tirole
4288:John Conway
4268:Eric Maskin
4064:Blotto game
4049:Pirate game
3858:Global game
3828:Tit for tat
3763:Bid shading
3753:Appeasement
3603:Equilibrium
3583:Solved game
3518:Determinacy
3501:Definitions
3494:game theory
3421:Solved game
3052:R. A. Hearn
2788:(1): 3–18.
1870:Acta Inform
1481:(2 player)
1437:374 or 299
1393:Carcassonne
1267:PSPACE-hard
1105:Candy Crush
1038:Hex (11x11)
918:-complete
889:-complete
582:Domineering
496:Pentominoes
438:Tic-tac-toe
384:Board size
314:generalized
303:tic-tac-toe
276:depth-first
268:PSPACE-hard
235:generalized
95:tic-tac-toe
72:upper bound
4540:Categories
4134:Trust game
4119:Kuhn poker
3788:Escalation
3783:Deterrence
3773:Cheap talk
3745:Strategies
3563:Preference
3492:Topics of
3398:2203.16713
3377:2003.05119
3351:cite arXiv
3342:1904.09828
2896:2012-03-29
2857:2012-03-29
2832:1507.06401
2723:2018-04-12
1812:2020-04-08
1785:2020-04-08
1706:References
1561:?, but in
1506:Go (19x19)
1384:?, but in
1188:Backgammon
999:?, but in
926:(Othello)
805:?, but in
775:?, but in
604:?, but in
573:?, but in
517:?, but in
223:asymptotic
140:full-width
4318:John Nash
4024:Stag hunt
3768:Collusion
3307:1201.5597
3300:: 78–88.
3282:1302.4377
2917:1403.6518
2615:1403.5830
2528:×
2366:×
2276:0803.1245
1612:infinite
1609:infinite
1606:infinite
1603:infinite
1600:infinite
1269:, and in
1101:Bejeweled
1091:(without
897:(6 sets)
868:(2 sets)
649:20 or 18
369:logarithm
281:will use
185:≥
88:game tree
4459:Lazy SMP
4153:Theorems
4104:Deadlock
3959:Checkers
3840:of games
3607:concepts
3410:See also
2802:10336286
2685:20960281
2474:(1950).
2301:17141575
2263:Integers
2091:10274228
2083:17641166
1848:21455572
1745:(1994).
1639:AH-hard
1570:Stratego
1363:Quoridor
1278:Havannah
1159:Connect6
754:Fanorona
584:(8 Ă— 8)
25:measures
4211:figures
3994:Chicken
3848:Auction
3838:Classes
2591:0629595
2407:1256205
2339:0573848
2281:Bibcode
2061:Bibcode
2053:Science
2034:1973019
1977:1427975
1665:NP-hard
1652:12,972
1586:21.739
1563:EXPTIME
1401:>40
1271:EXPTIME
1245:Abalone
1215:Xiangqi
1126:NP-hard
1113:<50
1001:EXPTIME
924:Reversi
916:EXPTIME
887:EXPTIME
807:EXPTIME
777:EXPTIME
737:<40
734:<17
618:Congkak
147:minimax
2800:
2683:
2673:
2589:
2453:
2405:
2337:
2299:
2089:
2081:
2032:
2022:
1975:
1965:
1846:
1806:GitHub
1758:
1645:Wordle
1556:17281
1540:Arimaa
1386:PSPACE
1333:Janggi
1175:46000
1107:(8x8)
1008:Gomoku
968:23.77
814:Tablut
606:PSPACE
575:PSPACE
519:PSPACE
353:PSPACE
345:DSPACE
329:-games
3949:Chess
3936:Games
3393:arXiv
3372:arXiv
3337:arXiv
3302:arXiv
3277:arXiv
3262:(PDF)
3227:(PDF)
3209:(PDF)
3137:(PDF)
3130:(PDF)
3056:arXiv
3038:(PDF)
3016:(PDF)
2989:(PDF)
2969:(PDF)
2958:(PDF)
2938:(PDF)
2912:arXiv
2891:(PDF)
2851:(PDF)
2827:arXiv
2809:(PDF)
2798:S2CID
2778:(PDF)
2681:S2CID
2644:(PDF)
2610:arXiv
2494:(PDF)
2479:(PDF)
2447:(PDF)
2427:(PDF)
2297:S2CID
2271:arXiv
2212:(PDF)
2134:(PDF)
2109:(PDF)
2087:S2CID
1955:(PDF)
1844:S2CID
1752:(PDF)
1678:Notes
1450:Shogi
1307:Twixt
1149:29.3
1067:Chess
731:(52)
714:54.2
698:Qubic
671:Awari
608:; in
526:Kalah
414:plies
381:Game
259:space
161:plies
3630:Core
3357:link
3322:link
2671:ISBN
2451:ISBN
2079:PMID
2020:ISBN
1963:ISBN
1756:ISBN
1583:381
1580:535
1577:115
1550:402
1522:250
1519:150
1516:360
1513:170
1510:361
1496:879
1490:240
1463:115
1460:226
1431:212
1425:100
1404:195
1373:162
1346:100
1343:160
1323:452
1317:159
1314:140
1311:572
1294:240
1288:157
1285:127
1282:271
1255:154
1225:150
1204:250
1198:144
1169:140
1166:172
1163:361
1143:132
1133:GIPF
1103:and
1077:123
1042:121
1025:210
1016:105
1013:225
910:600
900:121
881:180
871:121
743:5.6
687:3.5
658:2.8
483:3.7
423:Ref
402:(as
392:(as
301:For
274:The
241:-by-
215:The
134:The
82:The
63:The
4209:Key
3455:'s
3089:doi
3085:134
2790:doi
2751:doi
2712:doi
2708:385
2663:doi
2620:doi
2577:doi
2393:doi
2389:123
2327:doi
2289:doi
2226:doi
2162:doi
2123:doi
2069:doi
2057:317
1931:doi
1927:134
1889:doi
1836:doi
1574:92
1553:92
1547:43
1544:64
1493:56
1487:66
1484:33
1466:92
1457:71
1454:81
1434:84
1428:40
1410:55
1407:71
1398:72
1379:60
1376:91
1370:42
1367:81
1349:40
1340:44
1337:90
1320:60
1291:66
1261:60
1258:87
1252:25
1249:61
1231:38
1228:95
1222:40
1219:90
1201:55
1195:20
1192:28
1172:30
1146:90
1140:25
1137:37
1120:70
1110:64
1083:35
1080:70
1074:44
1071:64
1054:96
1051:50
1048:98
1045:57
1022:30
1019:70
994:29
991:44
988:64
985:23
982:64
965:31
962:62
959:88
956:72
941:10
938:58
935:58
932:28
929:64
903:78
874:23
850:90
847:54
844:30
841:50
821:27
818:81
800:10
797:50
794:50
791:10
788:24
770:11
767:44
764:46
761:21
758:45
740:52
711:20
708:34
705:30
702:64
684:60
681:32
678:12
675:12
655:70
652:40
646:32
628:33
625:15
622:14
596:30
593:27
590:15
587:64
565:36
562:21
559:13
556:42
541:50
536:18
533:13
530:14
512:75
509:10
506:18
503:12
500:64
480:14
471:15
467:Sim
404:log
394:log
335:by
261:or
4542::
3944:Go
3353:}}
3349:{{
3318:}}
3314:{{
3083:.
3079:.
3018:.
2817:^
2796:.
2786:27
2784:.
2780:.
2765:^
2745:.
2741:.
2706:.
2702:.
2679:.
2669:.
2618:.
2587:MR
2585:.
2573:31
2571:.
2565:.
2487:41
2485:.
2481:.
2403:MR
2401:.
2387:.
2383:.
2335:MR
2333:.
2321:.
2309:^
2295:.
2287:.
2279:.
2269:.
2265:.
2253:^
2220:.
2214:.
2158:13
2156:.
2142:^
2119:30
2117:.
2111:.
2085:.
2077:.
2067:.
2055:.
2051:.
2030:MR
2028:.
1973:MR
1971:.
1925:.
1921:.
1901:^
1856:^
1842:.
1832:13
1830:.
1803:.
1778:.
1714:^
1657:6
1649:5
1534:)
1095:)
853:4
599:8
568:4
477:8
474:3
454:4
451:9
448:5
445:3
442:9
416:)
359:.
349:mn
207:.
3874:n
3485:e
3478:t
3471:v
3401:.
3395::
3380:.
3374::
3359:)
3345:.
3339::
3324:)
3310:.
3304::
3285:.
3279::
3244:.
3229:.
3211:.
3178:.
3164:.
3162:N
3158:N
3154:.
3097:.
3091::
3064:.
3058::
2920:.
2914::
2899:.
2860:.
2835:.
2829::
2792::
2759:.
2753::
2747:8
2714::
2687:.
2665::
2626:.
2622::
2612::
2593:.
2579::
2563:"
2551:n
2531:n
2525:n
2502:.
2459:.
2409:.
2395::
2369:n
2363:n
2341:.
2329::
2323:8
2303:.
2291::
2283::
2273::
2267:9
2247:.
2232:.
2228::
2222:4
2168:.
2164::
2125::
2093:.
2071::
2063::
2036:.
2003:.
1979:.
1939:.
1933::
1895:.
1891::
1850:.
1838::
1815:.
1788:.
1764:.
610:P
412:(
347:(
341:k
337:n
333:m
327:k
325:,
323:n
321:,
319:m
243:n
239:n
193:d
189:b
182:C
179:T
176:G
164:d
157:b
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.