View source for Game complexity

{{Short description|Notion in combinatorial game theory}}

[[Combinatorial game theory]] [[Computational complexity theory|measures]] '''game complexity''' in several ways: 

#State-space complexity (the number of legal game positions from the initial position), 
#Game tree size (total number of possible games), 
#Decision complexity (number of leaf nodes in the smallest decision tree for initial position), 
#Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position), 
#Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large). 

These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios.

==Measures of game complexity==

=== State-space complexity ===
The '''state-space complexity''' of a game is the number of legal game positions reachable from the initial position of the game.<ref name="Allis1994"/>

When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions, meaning positions that can never arise in the course of a game.

=== Game tree size ===
The '''game tree size''' is the total number of possible games that can be played: the number of leaf nodes in the [[Game tree|game tree]] rooted at the game's initial position.

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 [[Tic-tac-toe|tic-tac-toe]] 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 example, by allowing illegal moves) until it becomes tractable.

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.

=== Decision trees ===
The next two measures use the idea of a ''[[Decision tree|decision tree]]'', 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.)

==== Decision complexity ====
'''Decision complexity''' of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position.

==== Game-tree complexity ====
The '''game-tree complexity''' of a game is the number of leaf nodes in the smallest ''full-width'' decision tree that establishes the value of the initial position.<ref name="Allis1994"/> A full-width tree includes all nodes at each depth.

This is an estimate of the number of positions one would have to evaluate in a [[Minimax|minimax]] search to determine the value of the initial position.

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 [[Branching factor|branching factor]] ''b'' to the power of the number of plies ''d'' in an average game, or:

<math>GTC \geq b^d</math>.

=== Computational complexity ===
The '''[[Computational complexity theory|computational complexity]]''' of a game describes the [[Asymptotic analysis|asymptotic]] difficulty of a game as it grows arbitrarily large, expressed in [[Big O notation|big O notation]] or as membership in a [[Complexity class|complexity class]]. This concept doesn't apply to particular games, but rather to games that have been [[Generalized game|generalized]] so they can be made arbitrarily large, typically by playing them on an ''n''-by-''n'' 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.)

The asymptotic complexity is defined by the most efficient (in terms of whatever [[Computational resource|computational resource]] one is considering) algorithm for solving the game; the most common complexity measure (computation time) 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 [[DSPACE|space]] or [[Computer memory|computer memory]] 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 [[PSPACE-hard]], 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).
* The [[Depth-first search|depth-first]] minimax strategy will use computation time proportional to 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 precisely the tree-complexity.
* [[Backward induction]] 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.

==Example: tic-tac-toe (noughts and crosses)==
For [[Tic-tac-toe|tic-tac-toe]], a simple upper bound for the size of the state space is 3<sup>9</sup> = 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.<ref>{{Cite web|url=https://math.stackexchange.com/questions/485752/tictactoe-state-space-choose-calculation|title=combinatorics - TicTacToe State Space Choose Calculation|website=Mathematics Stack Exchange|access-date=2020-04-08}}</ref><ref>{{cite web|last=T|first=Brian|title=Btsan/generate_tictactoe|website=[[GitHub]] |date=2018-10-20|url=https://github.com/Btsan/generate_tictactoe|access-date=2020-04-08}}</ref> And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.

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 are considered the same, there are only 26,830 possible games.

The computational complexity of tic-tac-toe depends on how it is [[Generalized game|generalized]]. A natural generalization is to ''m'',''n'',''k''-games: played on an ''m'' by ''n'' board with winner being the first player to get ''k'' in a row. It is immediately clear that this game can be solved in [[DSPACE]](''mn'') by searching the entire game tree. This places it in the important complexity class [[PSPACE]]. With some more work it can be shown to be [[PSPACE-complete]].<ref name="Reisch1980b">{{cite journal | author = Stefan Reisch | title = Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete) | journal = Acta Informatica | volume = 13 | issue = 1 | pages = 59–66 | year = 1980 | doi=10.1007/bf00288536| s2cid = 21455572}}</ref>

==Complexities of some well-known games==
Due to the large size of game complexities, this table gives the ceiling of their [[Logarithm|logarithm]] 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 numbers shown.

Note: ordered by game tree size

{| class="wikitable sortable"
|-
!Game
!Board size
(positions)
!State-space complexity
(as [[Logarithm|log]] to base 10)
!Game-tree complexity
(as [[Logarithm|log]] to base 10)
!Average game length
([[Software:Ply (game theory)|plies]])
!Branching factor
!Ref
![[Complexity class]] of suitable [[Generalized game|generalized game]]
|-
|[[Tic-tac-toe]]
|style="text-align:right;"|9
|style="text-align:right;"|3
|style="text-align:right;"|5
|style="text-align:right;"|9
|style="text-align:right;"|4
|style="text-align:right;"|
|[[PSPACE-complete]]<ref name="Reisch1980"/>
|-
|[[Software:Sim (pencil game)|Sim]]
|style="text-align:right;"|15
|style="text-align:right;"|3
|style="text-align:right;"|8
|style="text-align:right;"|14
|style="text-align:right;"|3.7
|style="text-align:right;"|
|[[PSPACE-complete]]<ref>{{cite conference
 | last = Slany | first = Wolfgang
 | editor1-last = Marsland | editor1-first = T. Anthony
 | editor2-last = Frank | editor2-first = Ian
 | contribution = The complexity of graph Ramsey games
 | doi = 10.1007/3-540-45579-5_12
 | pages = 186–203
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Computers and Games, Second International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Revised Papers
 | volume = 2063
 | year = 2000}}</ref>
|-
|Pentominoes
|style="text-align:right;"|64
|style="text-align:right;"|12
|style="text-align:right;"|18
|style="text-align:right;"|10
|style="text-align:right;"|75
|style="text-align:right;"|<ref name="GamesSolved"/><ref>{{cite conference
 | last = Orman | first = Hilarie K.
 | editor-last = Nowakowski | editor-first = Richard J.
 | contribution = Pentominoes: a first player win
 | contribution-url = https://www.msri.org/publications/books/Book29/files/orman.pdf
 | isbn = 0-521-57411-0
 | mr = 1427975
 | pages = 339–344
 | publisher = Cambridge University Press
 | series = Mathematical Sciences Research Institute Publications
 | title = Games of No Chance: Papers from the Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994
 | volume = 29
 | year = 1996}}</ref>
| {{dunno}}, but in [[PSPACE]]
|-
|Kalah<ref>See van den Herik et al for rules.</ref>
|style="text-align:right;"|14
|style="text-align:right;"|13
|style="text-align:right;"|18
|style="text-align:right;"|
|style="text-align:right;"|50
|style="text-align:right;"|<ref name="GamesSolved"/>
|Generalization is unclear
|-
|[[Social:Connect Four|Connect Four]]
|style="text-align:right;"|42
|style="text-align:right;"|13
|style="text-align:right;"|21
|style="text-align:right;"|36
|style="text-align:right;"|4
|style="text-align:right;"|<ref name="Allis1994"/><ref>{{cite web | title = John's Connect Four Playground | author = John Tromp | year = 2010 | url = https://tromp.github.io/c4/c4.html}}</ref>
| {{dunno}}, but in [[PSPACE]]
|-
|[[Domineering]] (8 × 8)
|style="text-align:right;"|64
|style="text-align:right;"|15
|style="text-align:right;"|27
|style="text-align:right;"|30
|style="text-align:right;"|8
|style="text-align:right;"|<ref name="GamesSolved"/>
| {{dunno}}, but in [[PSPACE]]; in P for certain dimensions<ref>{{cite conference
 | last1 = Lachmann | first1 = Michael
 | last2 = Moore | first2 = Cristopher
 | last3 = Rapaport | first3 = Ivan
 | editor-last = Nowakowski | editor-first = Richard
 | contribution = Who wins Domineering on rectangular boards?
 | isbn = 0-521-80832-4
 | mr = 1973019
 | pages = 307–315
 | publisher = Cambridge University Press
 | series = Mathematical Sciences Research Institute Publications
 | title = More Games of No Chance: Proceedings of the 2nd Combinatorial Games Theory Workshop held in Berkeley, CA, July 24–28, 2000
 | volume = 42
 | year = 2002}}</ref>
|-
|Congkak
|style="text-align:right;"|14
|style="text-align:right;"|15
|style="text-align:right;"|33
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|<ref name="GamesSolved">{{cite journal | title= Games solved: Now and in the future | author = H. J. van den Herik | author2 = J. W. H. M. Uiterwijk | author3 = J. van Rijswijck | year = 2002 | journal = Artificial Intelligence | volume = 134 | issue=1–2 | pages=277–311 | doi= 10.1016/S0004-3702(01)00152-7| doi-access = free }}</ref>
|
|-
|English draughts (8x8) (checkers)
|style="text-align:right;"|32
|style="text-align:right;"|20 or 18
|style="text-align:right;"|40
|style="text-align:right;"|70
|style="text-align:right;"|2.8
|style="text-align:right;"|<ref name="Allis1994"/><ref>{{cite journal | author = Jonathan Schaeffer| title = Checkers is Solved | journal = Science | date = July 6, 2007 | doi=10.1126/science.1144079 | volume=317 |issue= 5844 |pages= 1518–1522 | pmid=17641166 |display-authors=0|bibcode=2007Sci...317.1518S | s2cid = 10274228 | doi-access= free }}</ref><ref>{{cite journal
 | last = Schaeffer | first = Jonathan
 | doi = 10.3233/ICG-2007-30402
 | issue = 4
 | journal = [[ICGA Journal]]
 | pages = 187–197
 | title = Game over: Black to play and draw in checkers
 | url = https://ticc.uvt.nl/icga/journal/contents/Schaeffer07-01-08.pdf
 | archive-url = https://web.archive.org/web/20160403093928/https://ticc.uvt.nl/icga/journal/contents/Schaeffer07-01-08.pdf
 | archive-date = 2016-04-03
 | url-status = dead
 | volume = 30
 | year = 2007}}</ref>
|EXPTIME-complete<ref name="robson1984">{{cite journal | author = J. M. Robson | title = N by N checkers is Exptime complete | journal = [[SIAM Journal on Computing]] | volume = 13 | issue = 2 | pages = 252–267 | year = 1984 | doi = 10.1137/0213018}}</ref>
|-
|Awari<ref>See Allis 1994 for rules</ref>
|style="text-align:right;"|12
|style="text-align:right;"|12
|style="text-align:right;"|32
|style="text-align:right;"|60
|style="text-align:right;"|3.5
|style="text-align:right;"|<ref name="Allis1994"/>
|Generalization is unclear
|-
|Qubic
|style="text-align:right;"|64
|style="text-align:right;"|30
|style="text-align:right;"|34
|style="text-align:right;"|20
|style="text-align:right;"|54.2
|style="text-align:right;"|<ref name=Allis1994/>
|[[PSPACE-complete]]<ref name="Reisch1980"/>
|-
|[[Software:Computer bridge|Double dummy bridge]]{{refn|group=nb|Double dummy bridge (i.e., double dummy problems in the context of contract bridge) is not a proper board game but has a similar game tree, and is studied in [[Software:Computer bridge|computer bridge]]. 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.}}
|style="text-align:right;"|(52)
|style="text-align:right;"|<17
|style="text-align:right;"|<40
|style="text-align:right;"|52
|style="text-align:right;"|5.6
||
|align="left"|PSPACE-complete<ref>{{cite conference
 | last1 = Bonnet | first1 = Edouard
 | last2 = Jamain | first2 = Florian
 | last3 = Saffidine | first3 = Abdallah
 | editor-last = Rossi | editor-first = Francesca
 | contribution = On the complexity of trick-taking card games
 | contribution-url = https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6920
 | pages = 482–488
 | publisher = IJCAI/AAAI
 | title = IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013
 | year = 2013}}</ref>
|-
|Fanorona
|style="text-align:right;"|45
|style="text-align:right;"|21
|style="text-align:right;"|46
|style="text-align:right;"|44
|style="text-align:right;"|11
|style="text-align:right;"|<ref name="Schadd2008">{{cite journal|author1=M.P.D. Schadd |author2=M.H.M. Winands |author3=J.W.H.M. Uiterwijk |author4=H.J. van den Herik |author5=M.H.J. Bergsma | year = 2008 | title = Best Play in Fanorona leads to Draw | journal = [[New Mathematics and Natural Computation]] | volume = 4 |issue = 3 | pages = 369–387| url = https://dke.maastrichtuniversity.nl/m.winands/documents/Fanorona.pdf| doi = 10.1142/S1793005708001124}}</ref>
| {{dunno}}, but in [[EXPTIME]]
|-
|Nine men's morris
|style="text-align:right;"|24
|style="text-align:right;"|10
|style="text-align:right;"|50
|style="text-align:right;"|50
|style="text-align:right;"|10
|style="text-align:right;"|<ref name="Allis1994"/>
| {{dunno}}, but in [[EXPTIME]]
|-
|Tablut
|style="text-align:right;"|81
|style="text-align:right;"|27
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|<ref name="Galassi2018">{{cite web |author=Andrea Galassi |title=An Upper Bound on the Complexity of Tablut |date=2018 |url=http://ai.unibo.it/biblio/galassiTablutComplexity}}</ref>
|
|-
|International draughts (10x10)
|style="text-align:right;"|50
|style="text-align:right;"|30
|style="text-align:right;"|54
|style="text-align:right;"|90
|style="text-align:right;"|4
|style="text-align:right;"|<ref name="Allis1994"/>
|EXPTIME-complete<ref name="robson1984"/>
|-
|Chinese checkers (2 sets)
|style="text-align:right;"|121
|style="text-align:right;"|23
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|180
|style="text-align:right;"|<ref name=Bell_Halma>{{cite journal|author=G.I. Bell|title=The Shortest Game of Chinese Checkers and Related Problems|journal=Integers|year=2009|volume=9|doi=10.1515/INTEG.2009.003|arxiv=0803.1245|bibcode=2008arXiv0803.1245B|s2cid=17141575}}</ref>
|[[EXPTIME]]-complete <ref name=pebble>{{cite journal
 | last1 = Kasai | first1 = Takumi
 | last2 = Adachi | first2 = Akeo
 | last3 = Iwata | first3 = Shigeki
 | doi = 10.1137/0208046
 | issue = 4
 | journal = SIAM Journal on Computing
 | mr = 573848
 | pages = 574–586
 | title = Classes of pebble games and complete problems
 | volume = 8
 | year = 1979}} Proves completeness of the generalization to arbitrary graphs.</ref>
|-
|Chinese checkers (6 sets)
|style="text-align:right;"|121
|style="text-align:right;"|78
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|600
|style="text-align:right;"|<ref name=Bell_Halma/>
|[[EXPTIME]]-complete <ref name=pebble/>
|-
|Reversi (Othello)
|style="text-align:right;"|64
|style="text-align:right;"|28
|style="text-align:right;"|58
|style="text-align:right;"|58
|style="text-align:right;"|10
|style="text-align:right;"|<ref name="Allis1994"/>
|[[PSPACE-complete]]<ref>{{cite journal
 | last1 = Iwata | first1 = Shigeki
 | last2 = Kasai | first2 = Takumi
 | doi = 10.1016/0304-3975(94)90131-7 | doi-access = free
 | issue = 2
 | journal = Theoretical Computer Science
 | mr = 1256205
 | pages = 329–340
 | title = The Othello game on an <math>n\times n</math> board is PSPACE-complete
 | volume = 123
 | year = 1994}}</ref>
|-
|OnTop (2p base game)
|style="text-align:right;"|72
|style="text-align:right;"|88
|style="text-align:right;"|62
|style="text-align:right;"|31
|style="text-align:right;"|23.77
|style="text-align:right;"|<ref name="OnTopComputer">{{cite thesis | title=Analysis and Implementation of the Game OnTop |
url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Briesemeister_Thesis.pdf |
author = Robert Briesemeister | year=2009 | publisher = Maastricht University, Dept of Knowledge Engineering }}</ref>
|
|-
|Lines of Action
|style="text-align:right;"|64
|style="text-align:right;"|23
|style="text-align:right;"|64
|style="text-align:right;"|44
|style="text-align:right;"|29
|style="text-align:right;"|<ref name="Winands2004">{{cite thesis | author = Mark H.M. Winands | year = 2004 | title =  Informed Search in Complex Games | degree = Ph.D. |publisher= Maastricht University, Maastricht, The Netherlands | isbn = 90-5278-429-9 | url = https://dke.maastrichtuniversity.nl/m.winands/documents/informed_search.pdf}}</ref>
| {{dunno}}, but in [[EXPTIME]]
|-
|Gomoku (15x15, freestyle)
|style="text-align:right;"|225
|style="text-align:right;"|105
|style="text-align:right;"|70
|style="text-align:right;"|30
|style="text-align:right;"|210
|style="text-align:right;"|<ref name="Allis1994"/>
|[[PSPACE-complete]]<ref name="Reisch1980"/>
|-
|Hex (11x11)
|style="text-align:right;"|121
|style="text-align:right;"|57
|style="text-align:right;"|98
|style="text-align:right;"|50
|style="text-align:right;"|96
|style="text-align:right;"|<ref name="GamesSolved"/>
|[[PSPACE-complete]]<ref name="Reisch1980">{{cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta Inform | issue = 15 | year = 1981 | pages = 167–191}}</ref>
|-
|Chess
|style="text-align:right;"|64
|style="text-align:right;"|44
|style="text-align:right;"|123
|style="text-align:right;"|70
|style="text-align:right;"|35
|style="text-align:right;"|<ref name="Shannon1950">The size of the state space and game tree for chess were first estimated in {{cite journal
 |author=Claude Shannon
 |title=Programming a Computer for Playing Chess 
 |journal=Philosophical Magazine 
 |volume=41 
 |issue=314 
 |year=1950 
|url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf 
 |url-status=dead
 |archive-url=https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf
 |archive-date=2010-07-06
}} Shannon gave estimates of 10<sup>43</sup> and 10<sup>120</sup> respectively, smaller than the upper bound in the table,
which is detailed in [[Shannon number]].</ref>
|EXPTIME-complete (without 50-move drawing rule)<ref name="Fraenkel1981">{{cite journal
 | last2 = Lichtenstein | first2 = David
 | doi = 10.1016/0097-3165(81)90016-9 | doi-access = free
 | issue = 2
 | journal = Journal of Combinatorial Theory, Series A
 | mr = 629595
 | pages = 199–214
 | title = Computing a perfect strategy for <math>n\times n</math> chess requires time exponential in <math>n</math>
 | volume = 31
 | year = 1981}}</ref>
|-
|[[Software:Bejeweled|Bejeweled]] and [[Software:Candy Crush Saga|Candy Crush]] (8x8)
|style="text-align:right;"|64
|style="text-align:right;"|<50
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|70
|style="text-align:right;"|<ref name="Gual14">{{cite conference
 | last1 = Gualà | first1 = Luciano
 | last2 = Leucci | first2 = Stefano
 | last3 = Natale | first3 = Emanuele
 | arxiv = 1403.5830
 | contribution = Bejeweled, Candy Crush and other match-three games are (NP-)hard
 | doi = 10.1109/CIG.2014.6932866
 | pages = 1–8
 | publisher = IEEE
 | title = 2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, Dortmund, Germany, August 26-29, 2014
 | year = 2014}}</ref>
|NP-hard
|-
|GIPF
|style="text-align:right;"|37
|style="text-align:right;"|25
|style="text-align:right;"|132
|style="text-align:right;"|90
|style="text-align:right;"|29.3
|style="text-align:right;"|<ref name="Wentink_thesis">{{cite thesis | title=Analysis and Implementation of the game Gipf |
url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Wentink_thesis.pdf |
author = Diederik Wentink | year=2001 | publisher = Maastricht University}}</ref>
|style="text-align:right;"|
|-
|Connect6
|style="text-align:right;"|361
|style="text-align:right;"|172
|style="text-align:right;"|140
|style="text-align:right;"|30
|style="text-align:right;"|46000
|style="text-align:right;"|<ref name=EnhancePNConn6>{{cite book | title=2009 Chinese Control and Decision Conference | doi=10.1109/CCDC.2009.5191963 | chapter=Enhancements of proof number search in connect6 | year=2009 | last1=Chang-Ming Xu | last2=Ma | first2=Z.M. | last3=Jun-Jie Tao | last4=Xin-He Xu | isbn=978-1-4244-2722-2 | pages=4525 | s2cid=20960281 }}</ref>
|[[PSPACE|PSPACE-complete]]<ref>{{cite journal|url=http://dl.acm.org/citation.cfm?id=1290195.1290250|title=On the fairness and complexity of generalized k -in-a-row games|first1=Ming Yu|last1=Hsieh|first2=Shi-Chun|last2=Tsai|date=1 October 2007|journal=Theoretical Computer Science|volume=385|issue=1–3|pages=88–100|access-date=12 April 2018|via=dl.acm.org|doi=10.1016/j.tcs.2007.05.031|doi-access=free}}</ref>
|-
|Backgammon
|style="text-align:right;"|28
|style="text-align:right;"|20
|style="text-align:right;"|144
|style="text-align:right;"|55
|style="text-align:right;"|250
|style="text-align:right;"|<ref>{{cite journal|title=Practical issues in temporal difference learning|first=Gerald|last=Tesauro|date=1 May 1992|journal=Machine Learning|volume=8|issue=3–4|pages=257–277|doi=10.1007/BF00992697|doi-access=free}}</ref>
|Generalization is unclear
|-
|Xiangqi
|style="text-align:right;"|90
|style="text-align:right;"|40
|style="text-align:right;"|150
|style="text-align:right;"|95
|style="text-align:right;"|38
| {{dunno}}, believed to be EXPTIME-complete
|-
|Abalone
|style="text-align:right;"|61
|style="text-align:right;"|25
|style="text-align:right;"|154
|style="text-align:right;"|87
|style="text-align:right;"|60
|style="text-align:right;"|<ref name=PasChor>{{cite web|last=Chorus|first=Pascal|title=Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/pcreport.pdf|publisher=Dept of Knowledge Engineering, Maastricht University|access-date=29 March 2012}}</ref><ref name=Kopczynski>{{cite thesis |first=Jacob S |last=Kopczynski |title=Pushy Computing: Complexity Theory and the Game Abalone |publisher=Reed College |year=2014}}</ref>
|[[PSPACE-hard]], and in [[EXPTIME]]
|-
|Havannah
|style="text-align:right;"|271
|style="text-align:right;"|127
|style="text-align:right;"|157
|style="text-align:right;"|66
|style="text-align:right;"|240
|style="text-align:right;"|<ref name="GamesSolved"/><ref>{{cite web|last=Joosten|first=B|title=Creating a Havannah Playing Agent|url=https://project.dke.maastrichtuniversity.nl/games/files/bsc/bscHavannah.pdf|access-date=29 March 2012}}</ref>
|[[PSPACE-complete]]<ref>{{cite arXiv |author1=E. Bonnet |author2=F. Jamain |author3=A. Saffidine | title = Havannah and TwixT are PSPACE-complete | date = 2014-03-25 | eprint = 1403.6518 | class = cs.CC}}</ref>
|-
|Twixt
|style="text-align:right;"|572
|style="text-align:right;"|140
|style="text-align:right;"|159
|style="text-align:right;"|60
|style="text-align:right;"|452
|style="text-align:right;"|<ref name="Thesis_Moesker">{{cite thesis | title=Txixt: Theory, Analysis, and Implementation |
url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Thesis_Moesker.pdf |
author = Kevin Moesker | year=2009 | publisher = Faculty of Humanities and Sciences of Maastricht University }}</ref>
|style="text-align:right;"|
|-
|Janggi
|style="text-align:right;"|90
|style="text-align:right;"|44
|style="text-align:right;"|160
|style="text-align:right;"|100
|style="text-align:right;"|40
|style="text-align:right;"|<ref name="Donghwi"/>
| {{dunno}}, believed to be EXPTIME-complete
|-
|Quoridor
|style="text-align:right;"|81
|style="text-align:right;"|42
|style="text-align:right;"|162
|style="text-align:right;"|91
|style="text-align:right;"|60
|style="text-align:right;"|<ref name=MasterQuor>{{cite thesis|author=Lisa Glendenning |title=Mastering Quoridor |date=May 2005 |department=Computer Science |degree=B.Sc. |publisher=[[Organization:University of New Mexico|University of New Mexico]] |url=http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf |url-status=dead |archive-url=https://web.archive.org/web/20120315192840/http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf |archive-date=2012-03-15 }}</ref>
| {{dunno}}, but in [[PSPACE]]
|-
|Carcassonne (2p base game)
|style="text-align:right;"|72
|style="text-align:right;"|>40
|style="text-align:right;"|195
|style="text-align:right;"|71
|style="text-align:right;"|55
|style="text-align:right;"|<ref name="CarcassoneComputer">{{cite thesis | title=Implementing a Computer Player for Carcassonne |
url = https://project.dke.maastrichtuniversity.nl/games/files/msc/MasterThesisCarcassonne.pdf |
author = Cathleen Heyden | year=2009 | publisher = Maastricht University, Dept of Knowledge Engineering }}</ref>
|Generalization is unclear
|-
|Amazons (10x10)
|style="text-align:right;"|100
|style="text-align:right;"|40
|style="text-align:right;"|212
|style="text-align:right;"|84
|style="text-align:right;"|374 or 299<ref>The lower branching factor is for the second player.</ref>
|style="text-align:right;"|<ref name="Kloetzer_themonte-carlo">{{cite conference
 | last1 = Kloetzer | first1 = Julien
 | last2 = Iida | first2 = Hiroyuki
 | last3 = Bouzy | first3 = Bruno
 | contribution = The Monte-Carlo approach in Amazons
 | contribution-url = https://helios2.mi.parisdescartes.fr/~Bouzy/publications/KIB-MCAmazons-CGW07.pdf
 | pages = 185–192
 | title = Computer Games Workshop, Amsterdam, the Netherlands, 15-17 June 2007
 | year = 2007}}</ref><ref name="Hengens_thesis">{{cite web |author=P. P. L. M. Hensgens |title=A Knowledge-Based Approach of the Game of Amazons |year=2001 |publisher=Universiteit Maastricht, Institute for Knowledge and Agent Technology |url=https://project.dke.maastrichtuniversity.nl/games/files/msc/Hensgens_thesis.pdf}}</ref>
|[[PSPACE-complete]]<ref>{{cite arXiv | author = R. A. Hearn | title = Amazons is PSPACE-complete | date = 2005-02-02 | eprint = cs.CC/0502013 }}</ref>
|-
|Shogi
|style="text-align:right;"|81
|style="text-align:right;"|71
|style="text-align:right;"|226
|style="text-align:right;"|115
|style="text-align:right;"|92
|style="text-align:right;"|<ref name="Hsu2004"/><ref>{{cite journal | title = Computer shogi | doi = 10.1016/S0004-3702(01)00157-6 | journal = Artificial Intelligence | volume=134 | issue=1–2 |date=January 2002 | pages=121–144 | author= Hiroyuki Iida |author2=Makoto Sakuta |author3=Jeff Rollason | doi-access=free }}</ref>
|EXPTIME-complete<ref>{{cite journal |author1=H. Adachi |author2=H. Kamekawa |author3=S. Iwata | title = Shogi on n × n board is complete in exponential time | journal = Trans. IEICE | volume= J70-D | pages = 1843–1852 | year = 1987}}</ref>
|-
|Thurn and Taxis (2 player)
|style="text-align:right;"|33
|style="text-align:right;"|66
|style="text-align:right;"|240
|style="text-align:right;"|56
|style="text-align:right;"|879
|style="text-align:right;"| <ref name="Schadd2010">{{cite thesis | author = F.C. Schadd | title = Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis | year = 2009 | url =https://project.dke.maastrichtuniversity.nl/games/files/msc/Fschadd_thesis.pdf | publisher = Maastricht University| archive-url = https://web.archive.org/web/20210114164554/https://project.dke.maastrichtuniversity.nl/games/files/msc/Fschadd_thesis.pdf | archive-date = 2021-01-14 }}</ref>
|
|-
|[[Software:Go (game)|Go (19x19)]]
|style="text-align:right;"|361
|style="text-align:right;"|170
|style="text-align:right;"|360
|style="text-align:right;"|150
|style="text-align:right;"|250
|style="text-align:right;"|<ref name="Allis1994"/><ref name="cwi">{{cite web | title = Combinatorics of Go |author1=John Tromp |author2=Gunnar Farnebäck | year = 2007 | url = https://tromp.github.io/go/gostate.ps}} This paper derives the bounds 48&lt;log(log(''N''))&lt;171 on the number of possible games ''N''.</ref><ref name="Tromp2016">{{cite web | title=Number of legal Go positions | author=John Tromp | year=2016 | url=https://tromp.github.io/go/legal.html}}</ref>
|EXPTIME-complete (without the superko rule)<ref name="Robson1983">{{Cite book | author = J. M. Robson | chapter = The complexity of Go | title = Information Processing; Proceedings of IFIP Congress | year = 1983 | pages = 413–417}}</ref>
|-
|[[Software:Arimaa|Arimaa]]
|style="text-align:right;"|64
|style="text-align:right;"|43
|style="text-align:right;"|402
|style="text-align:right;"|92
|style="text-align:right;"|17281
|style="text-align:right;"|<ref name="Cox2006">{{cite web | title = Analysis and Implementation of the Game Arimaa | author = Christ-Jan Cox | year = 2006 | url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Cox_thesis1.pdf}}</ref><ref name="Wu2011">{{cite web | title = Move Ranking and Evaluation in the Game of Arimaa | author = David Jian Wu | year = 2011 | url = http://icosahedral.net/downloads/djwuthesis.pdf}}</ref><ref name="Haskin2006">{{cite web | title = A Look at the Arimaa Branching Factor | author = Brian Haskin | year = 2006 | url = http://arimaa.janzert.com/bf_study/}}</ref>
| {{dunno}}, but in [[EXPTIME]]
|-
|Stratego
|style="text-align:right;"|92
|style="text-align:right;"|115
|style="text-align:right;"|535
|style="text-align:right;"|381
|style="text-align:right;"|21.739
|style="text-align:right;"|<ref name="ArtsStratego">{{cite thesis | author = A.F.C. Arts | title = Competitive Play in Stratego | year = 2010 | url =https://project.dke.maastrichtuniversity.nl/games/files/msc/Arts_thesis.pdf | publisher = Maastricht }}</ref>
|style="text-align:right;"|
|-
|[[Infinite chess]]
|style="text-align:right;"|infinite
|style="text-align:right;"|infinite
|style="text-align:right;"|infinite
|style="text-align:right;"|infinite
|style="text-align:right;"|infinite
|style="text-align:right;"|<ref>{{cite arXiv | author = CDA Evans and Joel David Hamkins | title = Transfinite game values in infinite chess | year = 2014| class = math.LO | eprint = 1302.4377 }}</ref>
|{{Unknown}}, but mate-in-n is decidable<ref name="Brumleve2012">{{cite journal | author = Stefan Reisch, Joel David Hamkins, and Phillipp Schlicht | title = The mate-in-n problem of infinite chess is decidable | journal = Conference on Computability in Europe | year = 2012 | pages = 78–88 | arxiv = 1201.5597 }}</ref>
|-
|Magic: The Gathering
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|
|style="text-align:right;"|<ref name="Churchill2020">{{cite arXiv | author = Alex Churchill, Stella Biderman, and Austin Herrick | title = Magic: the Gathering is Turing Complete | year = 2020 | class = cs.AI | eprint = 1904.09828 }}</ref>
|AH-hard<ref name="Biderman">{{cite arXiv | author = Stella Biderman | title = Magic: the Gathering is as Hard as Arithmetic | year = 2020 | class = cs.AI | eprint = 2003.05119}}</ref>
|-
|Wordle
|5
|12,972
|
|6
|
|<ref>{{cite arXiv |last1=Lokshtanov |first1=Daniel |last2=Subercaseaux |first2=Bernardo |date=2022-05-14 |title=Wordle is NP-hard |class=cs.CC |eprint=2203.16713 }}</ref>
|[[NP-hardness|NP-hard]], unknown if [[PSPACE-complete]] with parametization.
|}

==Notes==
{{Reflist|group=nb}}

==References==
{{Reflist}}

==See also==
* [[Go and mathematics]]
* [[Solved game]]
* [[Solving chess]]
* [[Shannon number]]
* [[List of NP-complete problems#Games and puzzles|list of NP-complete games and puzzles]]
* [[List of PSPACE-complete problems#Games and puzzles|list of PSPACE-complete games and puzzles]]

==External links==
* [[Biography:David Eppstein|David Eppstein]]'s [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]

{{Game theory}}

[[Category:Combinatorial game theory]]
[[Category:Game theory]]

{{Sourceattribution|Game complexity}}