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