Editing Game complexity (section)

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

{{sticky header}}
{| class="wikitable sortable sticky-header"
|-
!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
([[Ply (game theory)|plies]])
!Branching factor
!Ref
![[Complexity class]] of suitable [[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"/>
|-
|[[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>
|-
|[[Pentomino]]es
|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
|-
|[[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 (complexity class)|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|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=etal|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>
|-
|[[Oware|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"/>
|-
|[[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 [[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|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 (board game)|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
 |author-link=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 [[Fifty-move rule|50-move drawing rule]])<ref name="Fraenkel1981">{{cite journal
 | last1 = Fraenkel | first1 = Aviezri S. |author1-link = Aviezri Fraenkel
 | 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>
|-
|[[Bejeweled (video game)|Bejeweled]] and [[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 (game)|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
|style="text-align:right;"|<ref name="Allis1994">{{cite thesis | author = Victor Allis | author-link = Victor Allis | year = 1994 | title = Searching for Solutions in Games and Artificial Intelligence | degree = Ph.D. |publisher= University of Limburg, Maastricht, The Netherlands | isbn = 90-900748-8-0 | url = https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf}}</ref><ref name="Hsu2004">{{cite journal | author1 = Shi-Jim Yen, Jr-Chang Chen | author2 = Tai-Ning Yang | author3 = Shun-Chin Hsu | title = Computer Chinese Chess | date = March 2004 | journal = International Computer Games Association Journal | volume = 27 | issue = 1 | pages = 3–18 | url = http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf | url-status = dead | archive-url = https://web.archive.org/web/20070614111609/http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf | archive-date = 2007-06-14 | doi=10.3233/ICG-2004-27102 | s2cid = 10336286 }}</ref><ref name="Donghwi">{{cite arXiv | author = Donghwi Park | title = Space-state complexity of Korean chess and Chinese chess | eprint= 1507.06401| year = 2015| class = math.GM }}</ref>
| {{dunno}}, believed to be [[EXPTIME-complete]]
|-
|[[Abalone (board game)|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 (board game)|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|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=[[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 (board game)|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
|-
|[[Game of the Amazons|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 | author-link=Bob 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 (board game)|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>
|
|-
|[[Go (game)|Go (19x19)]]
|style="text-align:right;"|361
|style="text-align:right;"|170
|style="text-align:right;"|505
|style="text-align:right;"|211
|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>
<ref>{{Cite web|url=https://homepages.cwi.nl/~aeb/go/misc/gostat.html|title = Statistics on the length of a go game}}</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>
|-
|[[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]]
|style="text-align:right;"|5
|style="text-align:right;"|4.113 (12,972)
|style="text-align:right;"|
|style="text-align:right;"|6
|style="text-align:right;"|
|style="text-align:right;"|<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
|}