Content deleted Content added
→Complexities of some well-known games: repair citation broken in Special:Diff/1139905889 by the ReferenceExpander script (see User:XOR'easter/sandbox/ReferenceExpander) Tags: Mobile edit Mobile web edit Advanced mobile edit |
User:Folly Mox: thanks, but that is a conference proceedings, not a journal |
||
Line 40:
==Example: tic-tac-toe (noughts and crosses)==
For [[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>{{
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.
Line 90:
|style="text-align:right;"|10
|style="text-align:right;"|75
|style="text-align:right;"|<ref name="GamesSolved"/><ref>{{
| last = Orman | first = Hilarie K.
| editor-last = Nowakowski | editor-first = Richard J.
|
| contribution-url =
| isbn = 0-521-57411-0
| mr = 1427975
|
| 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]]
|-
Line 126 ⟶ 130:
|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>{{
| 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]]
Line 171 ⟶ 188:
|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]]
Line 216 ⟶ 243:
|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)
Line 234 ⟶ 272:
|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)
Line 294 ⟶ 342:
}} 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">{{
| 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]] and [[Candy Crush Saga|Candy Crush]] (8x8)
Line 302 ⟶ 360:
|style="text-align:right;"|
|style="text-align:right;"|70
|style="text-align:right;"|<ref name="Gual14">{{cite
| 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]]
|-
Line 407 ⟶ 475:
|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
|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>▼
| 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
▲ |
|[[PSPACE-complete]]<ref>{{cite arXiv | author = R. A. Hearn | title = Amazons is PSPACE-complete | date = 2005-02-02 | eprint = cs.CC/0502013 }}</ref>
|-
| |||