Wikipedia

Game complexity: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Citation bot (talk | contribs)
Bots
5,867,242 edits
Removed access-date with no URL. | Use this bot. Report bugs. | Suggested by Mako001 | Linked from User:Mako001/access-date | #UCB_webform_linked 5/118
SporkBot (talk | contribs)
Bots
1,251,469 edits
m Replace or disable a template per TFD outcome; no change in content
Line 67:
|-
|[[Tic-tac-toe]]
|style="text-align:right;"|9
|{{ts|ar}}|9
|style="text-align:right;"|3
|{{ts|ar}}|3
|style="text-align:right;"|5
|{{ts|ar}}|5
|style="text-align:right;"|9
|{{ts|ar}}|9
|style="text-align:right;"|4
|{{ts|ar}}|4
|style="text-align:right;"|
|{{ts|ar}}|
|[[PSPACE-complete]]<ref name="Reisch1980"/>
|-
|[[Sim (pencil game)|Sim]]
|style="text-align:right;"|15
|{{ts|ar}}|15
|style="text-align:right;"|3
|{{ts|ar}}|3
|style="text-align:right;"|8
|{{ts|ar}}|8
|style="text-align:right;"|14
|{{ts|ar}}|14
|style="text-align:right;"|3.7
|{{ts|ar}}|3.7
|style="text-align:right;"|
|{{ts|ar}}|
|[[PSPACE-complete]]<ref>{{cite book|url=http://dl.acm.org/citation.cfm?id=647481.728124|title=The Complexity of Graph Ramsey Games|first=Wolfgang|last=Slany|date=26 October 2000|publisher=Springer-Verlag|pages=186–203|access-date=12 April 2018|via=dl.acm.org|isbn=9783540430803}}</ref>
|-
|[[Pentomino]]es
|style="text-align:right;"|64
|{{ts|ar}}|64
|style="text-align:right;"|12
|{{ts|ar}}|12
|style="text-align:right;"|18
|{{ts|ar}}|18
|style="text-align:right;"|10
|{{ts|ar}}|10
|style="text-align:right;"|75
|{{ts|ar}}|75
|{{ts|ar}}style="text-align:right;"|<ref name="GamesSolved"/><ref>Hilarie K. Orman: ''Pentominoes: A First Player Win'' in ''[http://www.msri.org/publications/books/Book29/contents.html Games of no chance]'', MSRI Publications – Volume 29, 1996, pages 339-344. Online: [http://www.msri.org/publications/books/Book29/files/orman.pdf pdf].</ref>
| {{dunno}}, but in [[PSPACE]]
|-
|[[Kalah]]<ref>See van den Herik et al for rules.</ref>
|style="text-align:right;"|14
|{{ts|ar}}|14
|style="text-align:right;"|13
|{{ts|ar}}|13
|style="text-align:right;"|18
|{{ts|ar}}|18
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|50
|{{ts|ar}}|50
|{{ts|ar}}style="text-align:right;"|<ref name="GamesSolved"/>
|Generalization is unclear
|-
|[[Connect Four]]
|style="text-align:right;"|42
|{{ts|ar}}|42
|style="text-align:right;"|13
|{{ts|ar}}|13
|style="text-align:right;"|21
|{{ts|ar}}|21
|style="text-align:right;"|36
|{{ts|ar}}|36
|style="text-align:right;"|4
|{{ts|ar}}|4
|{{ts|ar}}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
|{{ts|ar}}|64
|style="text-align:right;"|15
|{{ts|ar}}|15
|style="text-align:right;"|27
|{{ts|ar}}|27
|style="text-align:right;"|30
|{{ts|ar}}|30
|style="text-align:right;"|8
|{{ts|ar}}|8
|{{ts|ar}}style="text-align:right;"|<ref name="GamesSolved"/>
| {{dunno}}, but in [[PSPACE]]; in [[P (complexity class)|P]] for certain dimensions<ref>{{citation |author=Michael Lachmann |author2=Cristopher Moore |author3=Ivan Rapaport |title=Who wins domineering on rectangular boards? |volume=MSRI Combinatorial Game Theory Research Workshop |date=July 2000}}</ref>
|-
|[[Congkak]]
|style="text-align:right;"|14
|{{ts|ar}}|14
|style="text-align:right;"|15
|{{ts|ar}}|15
|style="text-align:right;"|33
|{{ts|ar}}|33
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|{{ts|ar}}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
|{{ts|ar}}|32
|{{ts|ar}}style="text-align:right;"|20 or 18
|style="text-align:right;"|40
|{{ts|ar}}|40
|style="text-align:right;"|70
|{{ts|ar}}|70
|style="text-align:right;"|2.8
|{{ts|ar}}|2.8
|{{ts|ar}}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 }}</ref><ref>Schaeffer, Jonathan (2007). "Game over: Black to play and draw in checkers". ''[[ICGA Journal]]''. '''30''' (4): 187–197. [[CiteSeerX (identifier)|CiteSeerX]] 10.1.1.154.255. [[Doi (identifier)|doi]]:10.3233/ICG-2007-30402.</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
|{{ts|ar}}|12
|style="text-align:right;"|12
|{{ts|ar}}|12
|style="text-align:right;"|32
|{{ts|ar}}|32
|style="text-align:right;"|60
|{{ts|ar}}|60
|style="text-align:right;"|3.5
|{{ts|ar}}|3.5
|{{ts|ar}}style="text-align:right;"|<ref name="Allis1994"/>
|Generalization is unclear
|-
|[[Qubic]]
|style="text-align:right;"|64
|{{ts|ar}}|64
|style="text-align:right;"|30
|{{ts|ar}}|30
|style="text-align:right;"|34
|{{ts|ar}}|34
|style="text-align:right;"|20
|{{ts|ar}}|20
|style="text-align:right;"|54.2
|{{ts|ar}}|54.2
|{{ts|ar}}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. Note that the last 4 plies are always forced moves with branching factor 1.}}
|style="text-align:right;"|(52)
|{{ts|ar}}|(52)
|style="text-align:right;"|<17
|{{ts|ar}}|<17
|style="text-align:right;"|<40
|{{ts|ar}}|<40
|style="text-align:right;"|52
|{{ts|ar}}|52
|style="text-align:right;"|5.6
|{{ts|ar}}|5.6
||
|align="left"|PSPACE-complete<ref>{{Cite book|last1=Bonnet|first1=Édouard|last2=Jamain|first2=Florian|last3=Saffidine|first3=Abdallah|date=2013-08-03|title=On the complexity of trick-taking card games|url=http://dl.acm.org/citation.cfm?id=2540128.2540199|publisher=AAAI Press|pages=482–488|isbn=9781577356332}}</ref>
|-
|[[Fanorona]]
|style="text-align:right;"|45
|{{ts|ar}}|45
|style="text-align:right;"|21
|{{ts|ar}}|21
|style="text-align:right;"|46
|{{ts|ar}}|46
|style="text-align:right;"|44
|{{ts|ar}}|44
|style="text-align:right;"|11
|{{ts|ar}}|11
|{{ts|ar}}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
|{{ts|ar}}|24
|style="text-align:right;"|10
|{{ts|ar}}|10
|style="text-align:right;"|50
|{{ts|ar}}|50
|style="text-align:right;"|50
|{{ts|ar}}|50
|style="text-align:right;"|10
|{{ts|ar}}|10
|{{ts|ar}}style="text-align:right;"|<ref name="Allis1994"/>
| {{dunno}}, but in [[EXPTIME]]
|-
|[[Tablut]]
|style="text-align:right;"|81
|{{ts|ar}}|81
|style="text-align:right;"|27
|{{ts|ar}}|27
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|{{ts|ar}}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
|{{ts|ar}}|50
|style="text-align:right;"|30
|{{ts|ar}}|30
|style="text-align:right;"|54
|{{ts|ar}}|54
|style="text-align:right;"|90
|{{ts|ar}}|90
|style="text-align:right;"|4
|{{ts|ar}}|4
|{{ts|ar}}style="text-align:right;"|<ref name="Allis1994"/>
|[[EXPTIME-complete]]<ref name="robson1984"/>
|-
|[[Chinese checkers]] (2 sets)
|style="text-align:right;"|121
|{{ts|ar}}|121
|style="text-align:right;"|23
|{{ts|ar}}|23
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|180
|{{ts|ar}}|180
|{{ts|ar}}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|title=Classes of Pebble Games and Complete Problems|journal= SIAM Journal on Computing| volume = 8| year = 1979 |pages= 574–586|author1=Takumi Kasai |author2=Akeo Adachi |author3=Shigeki Iwata |doi=10.1137/0208046|issue=4}} Proves completeness of the generalization to arbitrary graphs.</ref>
|-
|[[Chinese checkers]] (6 sets)
|style="text-align:right;"|121
|{{ts|ar}}|121
|style="text-align:right;"|78
|{{ts|ar}}|78
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|600
|{{ts|ar}}|600
|{{ts|ar}}style="text-align:right;"|<ref name=Bell_Halma/>
|[[EXPTIME]]-complete <ref name=pebble/>
|-
|[[Reversi]] (Othello)
|style="text-align:right;"|64
|{{ts|ar}}|64
|style="text-align:right;"|28
|{{ts|ar}}|28
|style="text-align:right;"|58
|{{ts|ar}}|58
|style="text-align:right;"|58
|{{ts|ar}}|58
|style="text-align:right;"|10
|{{ts|ar}}|10
|{{ts|ar}}style="text-align:right;"|<ref name="Allis1994"/>
|[[PSPACE-complete]]<ref>{{cite journal |author1=S. Iwata |author2=T. Kasai | title = The Othello game on an n*n board is PSPACE-complete | journal = Theor. Comput. Sci. | issue = 2 | year = 1994 | pages = 329–340 | volume = 123 | doi = 10.1016/0304-3975(94)90131-7| doi-access = free }}</ref>
|-
|OnTop (2p base game)
|style="text-align:right;"|72
|{{ts|ar}}|72
|style="text-align:right;"|88
|{{ts|ar}}|88
|style="text-align:right;"|62
|{{ts|ar}}|62
|style="text-align:right;"|31
|{{ts|ar}}|31
|{{ts|ar}}style="text-align:right;"|23.77
|{{ts|ar}}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>
Line 240:
|-
|[[Lines of Action]]
|style="text-align:right;"|64
|{{ts|ar}}|64
|style="text-align:right;"|23
|{{ts|ar}}|23
|style="text-align:right;"|64
|{{ts|ar}}|64
|style="text-align:right;"|44
|{{ts|ar}}|44
|style="text-align:right;"|29
|{{ts|ar}}|29
|{{ts|ar}}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
|{{ts|ar}}|225
|style="text-align:right;"|105
|{{ts|ar}}|105
|style="text-align:right;"|70
|{{ts|ar}}|70
|style="text-align:right;"|30
|{{ts|ar}}|30
|style="text-align:right;"|210
|{{ts|ar}}|210
|{{ts|ar}}style="text-align:right;"|<ref name="Allis1994"/>
|[[PSPACE-complete]]<ref name="Reisch1980"/>
|-
|[[Hex (board game)|Hex (11x11)]]
|style="text-align:right;"|121
|{{ts|ar}}|121
|style="text-align:right;"|57
|{{ts|ar}}|57
|style="text-align:right;"|98
|{{ts|ar}}|98
|style="text-align:right;"|50
|{{ts|ar}}|50
|style="text-align:right;"|96
|{{ts|ar}}|96
|{{ts|ar}}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
|{{ts|ar}}|64
|style="text-align:right;"|44
|{{ts|ar}}|44
|style="text-align:right;"|123
|{{ts|ar}}|123
|style="text-align:right;"|70
|{{ts|ar}}|70
|style="text-align:right;"|35
|{{ts|ar}}|35
|{{ts|ar}}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
Line 289:
|-
|[[Bejeweled]] and [[Candy Crush Saga|Candy Crush]] (8x8)
|style="text-align:right;"|64
|{{ts|ar}}|64
|style="text-align:right;"|<50
|{{ts|ar}}|<50
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|70
|{{ts|ar}}|70
|{{ts|ar}}style="text-align:right;"|<ref name="Gual14">{{cite arXiv |author1=L. Gualà |author2=S. Leucci |author3=E. Natale | title = Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard | eprint= 1403.5830| year = 2014|class=cs.CC }}</ref>
|[[NP-hard]]
|-
|[[GIPF (game)|GIPF]]
|style="text-align:right;"|37
|{{ts|ar}}|37
|style="text-align:right;"|25
|{{ts|ar}}|25
|style="text-align:right;"|132
|{{ts|ar}}|132
|style="text-align:right;"|90
|{{ts|ar}}|90
|style="text-align:right;"|29.3
|{{ts|ar}}|29.3
|{{ts|ar}}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;"|
|{{ts|ar}}|
|-
|[[Connect6]]
|style="text-align:right;"|361
|{{ts|ar}}|361
|style="text-align:right;"|172
|{{ts|ar}}|172
|style="text-align:right;"|140
|{{ts|ar}}|140
|style="text-align:right;"|30
|{{ts|ar}}|30
|{{ts|ar}}style="text-align:right;"|46000
|{{ts|ar}}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
|{{ts|ar}}|28
|style="text-align:right;"|20
|{{ts|ar}}|20
|style="text-align:right;"|144
|{{ts|ar}}|144
|style="text-align:right;"|55
|{{ts|ar}}|55
|style="text-align:right;"|250
|{{ts|ar}}|250
|{{ts|ar}}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
|{{ts|ar}}|90
|style="text-align:right;"|40
|{{ts|ar}}|40
|style="text-align:right;"|150
|{{ts|ar}}|150
|style="text-align:right;"|95
|{{ts|ar}}|95
|style="text-align:right;"|38
|{{ts|ar}}|38
|{{ts|ar}}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 }}</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
|{{ts|ar}}|61
|style="text-align:right;"|25
|{{ts|ar}}|25
|style="text-align:right;"|154
|{{ts|ar}}|154
|style="text-align:right;"|87
|{{ts|ar}}|87
|style="text-align:right;"|60
|{{ts|ar}}|60
|{{ts|ar}}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
|{{ts|ar}}|271
|style="text-align:right;"|127
|{{ts|ar}}|127
|style="text-align:right;"|157
|{{ts|ar}}|157
|style="text-align:right;"|66
|{{ts|ar}}|66
|style="text-align:right;"|240
|{{ts|ar}}|240
|{{ts|ar}}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
|{{ts|ar}}|572
|style="text-align:right;"|140
|{{ts|ar}}|140
|style="text-align:right;"|159
|{{ts|ar}}|159
|style="text-align:right;"|60
|{{ts|ar}}|60
|style="text-align:right;"|452
|{{ts|ar}}|452
|{{ts|ar}}style="text-align:right;"|<ref name="Thesis_Moesker">{{cite thesis | title=TWIXT: THEORY, ANALYSIS AND IMPLEMENTATION |
url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Thesis_Moesker.pdf |
author = Kevin Moesker | year=2009 | publisher = Maastricht University, Faculty of Humanities and Sciences of Maastricht University }}</ref>
|style="text-align:right;"|
|{{ts|ar}}|
|-
|[[Janggi]]
|style="text-align:right;"|90
|{{ts|ar}}|90
|style="text-align:right;"|44
|{{ts|ar}}|44
|style="text-align:right;"|160
|{{ts|ar}}|160
|style="text-align:right;"|100
|{{ts|ar}}|100
|style="text-align:right;"|40
|{{ts|ar}}|40
|{{ts|ar}}style="text-align:right;"|<ref name="Donghwi"/>
| {{dunno}}, believed to be [[EXPTIME-complete]]
|-
|[[Quoridor]]
|style="text-align:right;"|81
|{{ts|ar}}|81
|style="text-align:right;"|42
|{{ts|ar}}|42
|style="text-align:right;"|162
|{{ts|ar}}|162
|style="text-align:right;"|91
|{{ts|ar}}|91
|style="text-align:right;"|60
|{{ts|ar}}|60
|{{ts|ar}}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
|{{ts|ar}}|72
|style="text-align:right;"|>40
|{{ts|ar}}|>40
|style="text-align:right;"|195
|{{ts|ar}}|195
|style="text-align:right;"|71
|{{ts|ar}}|71
|style="text-align:right;"|55
|{{ts|ar}}|55
|{{ts|ar}}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>
Line 394:
|-
|[[Game of the Amazons|Amazons (10x10)]]
|style="text-align:right;"|100
|{{ts|ar}}|100
|style="text-align:right;"|40
|{{ts|ar}}|40
|style="text-align:right;"|212
|{{ts|ar}}|212
|style="text-align:right;"|84
|{{ts|ar}}|84
|{{ts|ar}}style="text-align:right;"|374 or 299<ref>The lower branching factor is for the second player.</ref>
|{{ts|ar}}style="text-align:right;"|<ref name="Kloetzer_themonte-carlo">{{citation |author=Julien Kloetzer |author2=Hiroyuki Iida |author3=Bruno Bouzy |title=The Monte-Carlo Approach in Amazons |year=2007 |citeseerx=10.1.1.79.7640}}</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
|{{ts|ar}}|81
|style="text-align:right;"|71
|{{ts|ar}}|71
|style="text-align:right;"|226
|{{ts|ar}}|226
|style="text-align:right;"|115
|{{ts|ar}}|115
|style="text-align:right;"|92
|{{ts|ar}}|92
|{{ts|ar}}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
|{{ts|ar}}|33
|style="text-align:right;"|66
|{{ts|ar}}|66
|style="text-align:right;"|240
|{{ts|ar}}|240
|style="text-align:right;"|56
|{{ts|ar}}|56
|style="text-align:right;"|879
|{{ts|ar}}|879
|{{ts|ar}}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
|{{ts|ar}}|361
|style="text-align:right;"|170
|{{ts|ar}}|170
|style="text-align:right;"|360
|{{ts|ar}}|360
|style="text-align:right;"|150
|{{ts|ar}}|150
|style="text-align:right;"|250
|{{ts|ar}}|250
|{{ts|ar}}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]]<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
|{{ts|ar}}|64
|style="text-align:right;"|43
|{{ts|ar}}|43
|style="text-align:right;"|402
|{{ts|ar}}|402
|style="text-align:right;"|92
|{{ts|ar}}|92
|{{ts|ar}}style="text-align:right;"|17281
|{{ts|ar}}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
|{{ts|ar}}|92
|style="text-align:right;"|115
|{{ts|ar}}|115
|style="text-align:right;"|535
|{{ts|ar}}|535
|style="text-align:right;"|381
|{{ts|ar}}|381
|{{ts|ar}}style="text-align:right;"|21.739
|{{ts|ar}}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;"|
|{{ts|ar}}|
|-
|[[Infinite chess]]{{refn|group=nb|'''Infinite chess''' is a class of games, which includes [[Infinite chess#Variations|'''Chess on an Infinite Plane''']] and [[Infinite chess#Variations|'''Trappist-1''']] as examples.<ref>[http://www.chessvariants.com/invention/chess-on-an-infinite-plane Chess on an Infinite Plane] game rules</ref><ref>[http://www.chessvariants.com/invention/trappist-1 Trappist-1] game rules</ref>}}
|{{ts|ar}}style="text-align:right;"|infinite
|{{ts|ar}}style="text-align:right;"|infinite
|{{ts|ar}}style="text-align:right;"|infinite
|{{ts|ar}}style="text-align:right;"|infinite
|{{ts|ar}}style="text-align:right;"|infinite
|{{ts|ar}}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 | url = https://arxiv.org/pdf/1201.5597.pdf}}</ref>
|-
|[[Magic: the Gathering]]
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|style="text-align:right;"|
|{{ts|ar}}|
|{{ts|ar}}style="text-align:right;"|<ref name="Churchill2020">{{cite journal | author = Alex Churchill, Stella Biderman, and Austin Herrick | title = Magic: the Gathering is Turing Complete | journal = Fun with Algorithms | year = 2020 | arxiv = 1904.09828 | url = https://arxiv.org/pdf/1904.09828.pdf}}</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 <!-- | url = https://arxiv.org/pdf/2003.05119.pdf -->}}</ref>
|-
Retrieved from "https://en.wikipedia.org/wiki/Game_complexity"