• Images
• Videos
• Documents
• Books
• Articles

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.¹

When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions (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. This is the number of leaf nodes in the 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 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

A decision tree is a subtree of the game tree, with each position labelled "player A wins", "player B wins", or "draw" 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—with player A to move, a position can be labelled "player A wins" if any successor position is a win for A; "player B wins" if all successor positions are wins for B; or "draw" if all successor positions are either drawn or wins for B. (With player B to move, corresponding positions are marked similarly.)

The following two methods of measuring game complexity use decision trees:

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

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.² 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 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 G T C ≥ b d {\displaystyle GTC\geq b^{d}} , where b is the game's average branching factor and d is the number of plies in an average game.

Computational complexity

The computational complexity of a game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in بیگ و or as membership in a complexity class. This concept doesn't apply to particular games, but rather to games that have been 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 algorithm for solving the game (in terms of whatever computational resource one is considering). 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 space or 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 minimax strategy will use computation time proportional to the game's tree-complexity (since it must explore the whole tree), and an amount of memory polynomial in the logarithm of the tree-complexity (since the algorithm must always store one node of the tree at each possible move-depth, and the number of nodes at the highest move-depth is 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, a simple upper bound for the size of the state space is 39 = 19,683. (There are three states for each of the nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478.³⁴ And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.

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. 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. This game can be solved in DSPACE(mn) by searching the entire game tree. This places it in the important complexity class PSPACE; with more work, it can be shown to be PSPACE-complete.⁵

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.

Notes

See also

• Go and mathematics
• Solved game
• Solving chess
• Shannon number
• list of NP-complete games and puzzles
• list of PSPACE-complete games and puzzles

External links

• David Eppstein's Computational Complexity of Games and Puzzles

References

1. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

2. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

3. "combinatorics - TicTacToe State Space Choose Calculation". Mathematics Stack Exchange. Retrieved 2020-04-08. https://math.stackexchange.com/questions/485752/tictactoe-state-space-choose-calculation ↩

4. T, Brian (October 20, 2018). "Btsan/generate_tictactoe". GitHub. Retrieved 2020-04-08. https://github.com/Btsan/generate_tictactoe ↩

5. Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete)". Acta Informatica. 13 (1): 59–66. doi:10.1007/bf00288536. S2CID 21455572. /wiki/Doi_(identifier) ↩

6. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform (15): 167–191. ↩

7. Slany, Wolfgang (2000). "The complexity of graph Ramsey games". In Marsland, T. Anthony; Frank, Ian (eds.). Computers and Games, Second International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Revised Papers. Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 186–203. doi:10.1007/3-540-45579-5_12. /wiki/Doi_(identifier) ↩

8. H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7. https://doi.org/10.1016%2FS0004-3702%2801%2900152-7 ↩

9. Orman, Hilarie K. (1996). "Pentominoes: a first player win" (PDF). In Nowakowski, Richard J. (ed.). Games of No Chance: Papers from the Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994. Mathematical Sciences Research Institute Publications. Vol. 29. Cambridge University Press. pp. 339–344. ISBN 0-521-57411-0. MR 1427975. 0-521-57411-0 ↩

10. See van den Herik et al for rules. ↩

11. H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7. https://doi.org/10.1016%2FS0004-3702%2801%2900152-7 ↩

12. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

13. John Tromp (2010). "John's Connect Four Playground". https://tromp.github.io/c4/c4.html ↩

14. H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7. https://doi.org/10.1016%2FS0004-3702%2801%2900152-7 ↩

15. Lachmann, Michael; Moore, Cristopher; Rapaport, Ivan (2002). "Who wins Domineering on rectangular boards?". In Nowakowski, Richard (ed.). More Games of No Chance: Proceedings of the 2nd Combinatorial Games Theory Workshop held in Berkeley, CA, July 24–28, 2000. Mathematical Sciences Research Institute Publications. Vol. 42. Cambridge University Press. pp. 307–315. ISBN 0-521-80832-4. MR 1973019. 0-521-80832-4 ↩

16. H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7. https://doi.org/10.1016%2FS0004-3702%2801%2900152-7 ↩

17. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

18. Jonathan Schaeffer; et al. (July 6, 2007). "Checkers is Solved". Science. 317 (5844): 1518–1522. Bibcode:2007Sci...317.1518S. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228. https://doi.org/10.1126%2Fscience.1144079 ↩

19. Schaeffer, Jonathan (2007). "Game over: Black to play and draw in checkers" (PDF). ICGA Journal. 30 (4): 187–197. doi:10.3233/ICG-2007-30402. Archived from the original (PDF) on 2016-04-03. https://web.archive.org/web/20160403093928/https://ticc.uvt.nl/icga/journal/contents/Schaeffer07-01-08.pdf ↩

20. J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018. /wiki/SIAM_Journal_on_Computing ↩

21. See Allis 1994 for rules ↩

22. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

23. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

24. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform (15): 167–191. ↩

25. 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. /wiki/Contract_bridge ↩

26. Bonnet, Edouard; Jamain, Florian; Saffidine, Abdallah (2013). "On the complexity of trick-taking card games". In Rossi, Francesca (ed.). IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. IJCAI/AAAI. pp. 482–488. https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6920 ↩

27. M.P.D. Schadd; M.H.M. Winands; J.W.H.M. Uiterwijk; H.J. van den Herik; M.H.J. Bergsma (2008). "Best Play in Fanorona leads to Draw" (PDF). New Mathematics and Natural Computation. 4 (3): 369–387. doi:10.1142/S1793005708001124. https://dke.maastrichtuniversity.nl/m.winands/documents/Fanorona.pdf ↩

28. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

29. Andrea Galassi (2018). "An Upper Bound on the Complexity of Tablut". http://ai.unibo.it/biblio/galassiTablutComplexity ↩

30. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

31. J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018. /wiki/SIAM_Journal_on_Computing ↩

32. G.I. Bell (2009). "The Shortest Game of Chinese Checkers and Related Problems". Integers. 9. arXiv:0803.1245. Bibcode:2008arXiv0803.1245B. doi:10.1515/INTEG.2009.003. S2CID 17141575. /wiki/ArXiv_(identifier) ↩

33. Kasai, Takumi; Adachi, Akeo; Iwata, Shigeki (1979). "Classes of pebble games and complete problems". SIAM Journal on Computing. 8 (4): 574–586. doi:10.1137/0208046. MR 0573848. Proves completeness of the generalization to arbitrary graphs. /wiki/Doi_(identifier) ↩

34. G.I. Bell (2009). "The Shortest Game of Chinese Checkers and Related Problems". Integers. 9. arXiv:0803.1245. Bibcode:2008arXiv0803.1245B. doi:10.1515/INTEG.2009.003. S2CID 17141575. /wiki/ArXiv_(identifier) ↩

35. Kasai, Takumi; Adachi, Akeo; Iwata, Shigeki (1979). "Classes of pebble games and complete problems". SIAM Journal on Computing. 8 (4): 574–586. doi:10.1137/0208046. MR 0573848. Proves completeness of the generalization to arbitrary graphs. /wiki/Doi_(identifier) ↩

36. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

37. Iwata, Shigeki; Kasai, Takumi (1994). "The Othello game on an n × n {\displaystyle n\times n} board is PSPACE-complete". Theoretical Computer Science. 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7. MR 1256205. https://doi.org/10.1016%2F0304-3975%2894%2990131-7 ↩

38. Robert Briesemeister (2009). Analysis and Implementation of the Game OnTop (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering. https://project.dke.maastrichtuniversity.nl/games/files/msc/Briesemeister_Thesis.pdf ↩

39. Mark H.M. Winands (2004). Informed Search in Complex Games (PDF) (Ph.D. thesis). Maastricht University, Maastricht, The Netherlands. ISBN 90-5278-429-9. 90-5278-429-9 ↩

40. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

41. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform (15): 167–191. ↩

42. H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7. https://doi.org/10.1016%2FS0004-3702%2801%2900152-7 ↩

43. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform (15): 167–191. ↩

44. The size of the state space and game tree for chess were first estimated in Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 41 (314). Archived from the original (PDF) on 2010-07-06. Shannon gave estimates of 1043 and 10120 respectively, smaller than the upper bound in the table, which is detailed in Shannon number. /wiki/Claude_Shannon ↩

45. Fraenkel, Aviezri S.; Lichtenstein, David (1981). "Computing a perfect strategy for n × n {\displaystyle n\times n} chess requires time exponential in n {\displaystyle n} ". Journal of Combinatorial Theory, Series A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9. MR 0629595. /wiki/Aviezri_Fraenkel ↩

46. Gualà, Luciano; Leucci, Stefano; Natale, Emanuele (2014). "Bejeweled, Candy Crush and other match-three games are (NP-)hard". 2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, Dortmund, Germany, August 26-29, 2014. IEEE. pp. 1–8. arXiv:1403.5830. doi:10.1109/CIG.2014.6932866. /wiki/ArXiv_(identifier) ↩

47. Diederik Wentink (2001). Analysis and Implementation of the game Gipf (PDF) (Thesis). Maastricht University. https://project.dke.maastrichtuniversity.nl/games/files/msc/Wentink_thesis.pdf ↩

48. Chang-Ming Xu; Ma, Z.M.; Jun-Jie Tao; Xin-He Xu (2009). "Enhancements of proof number search in connect6". 2009 Chinese Control and Decision Conference. p. 4525. doi:10.1109/CCDC.2009.5191963. ISBN 978-1-4244-2722-2. S2CID 20960281. 978-1-4244-2722-2 ↩

49. Hsieh, Ming Yu; Tsai, Shi-Chun (October 1, 2007). "On the fairness and complexity of generalized k -in-a-row games". Theoretical Computer Science. 385 (1–3): 88–100. doi:10.1016/j.tcs.2007.05.031. Retrieved 2018-04-12 – via dl.acm.org. http://dl.acm.org/citation.cfm?id=1290195.1290250 ↩

50. Tesauro, Gerald (May 1, 1992). "Practical issues in temporal difference learning". Machine Learning. 8 (3–4): 257–277. doi:10.1007/BF00992697. https://doi.org/10.1007%2FBF00992697 ↩

51. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

52. Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (March 2004). "Computer Chinese Chess" (PDF). International Computer Games Association Journal. 27 (1): 3–18. doi:10.3233/ICG-2004-27102. S2CID 10336286. Archived from the original (PDF) on 2007-06-14. https://web.archive.org/web/20070614111609/http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf ↩

53. Donghwi Park (2015). "Space-state complexity of Korean chess and Chinese chess". arXiv:1507.06401 [math.GM]. /wiki/ArXiv_(identifier) ↩

54. Chorus, Pascal. "Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search" (PDF). Dept of Knowledge Engineering, Maastricht University. Retrieved 2012-03-29. https://project.dke.maastrichtuniversity.nl/games/files/msc/pcreport.pdf ↩

55. Kopczynski, Jacob S (2014). Pushy Computing: Complexity Theory and the Game Abalone (Thesis). Reed College. ↩

56. H. J. van den Herik; J. W. H. M. Uiterwijk; J. van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence. 134 (1–2): 277–311. doi:10.1016/S0004-3702(01)00152-7. https://doi.org/10.1016%2FS0004-3702%2801%2900152-7 ↩

57. Joosten, B. "Creating a Havannah Playing Agent" (PDF). Retrieved 2012-03-29. https://project.dke.maastrichtuniversity.nl/games/files/bsc/bscHavannah.pdf ↩

58. E. Bonnet; F. Jamain; A. Saffidine (March 25, 2014). "Havannah and TwixT are PSPACE-complete". arXiv:1403.6518 [cs.CC]. /wiki/ArXiv_(identifier) ↩

59. Kevin Moesker (2009). Txixt: Theory, Analysis, and Implementation (PDF) (Thesis). Faculty of Humanities and Sciences of Maastricht University. https://project.dke.maastrichtuniversity.nl/games/files/msc/Thesis_Moesker.pdf ↩

60. Donghwi Park (2015). "Space-state complexity of Korean chess and Chinese chess". arXiv:1507.06401 [math.GM]. /wiki/ArXiv_(identifier) ↩

61. Lisa Glendenning (May 2005). Mastering Quoridor (PDF). Computer Science (B.Sc. thesis). University of New Mexico. Archived from the original (PDF) on 2012-03-15. https://web.archive.org/web/20120315192840/http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf ↩

62. Cathleen Heyden (2009). Implementing a Computer Player for Carcassonne (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering. https://project.dke.maastrichtuniversity.nl/games/files/msc/MasterThesisCarcassonne.pdf ↩

63. The lower branching factor is for the second player. ↩

64. Kloetzer, Julien; Iida, Hiroyuki; Bouzy, Bruno (2007). "The Monte-Carlo approach in Amazons" (PDF). Computer Games Workshop, Amsterdam, the Netherlands, 15-17 June 2007. pp. 185–192. https://helios2.mi.parisdescartes.fr/~Bouzy/publications/KIB-MCAmazons-CGW07.pdf ↩

65. P. P. L. M. Hensgens (2001). "A Knowledge-Based Approach of the Game of Amazons" (PDF). Universiteit Maastricht, Institute for Knowledge and Agent Technology. https://project.dke.maastrichtuniversity.nl/games/files/msc/Hensgens_thesis.pdf ↩

66. R. A. Hearn (February 2, 2005). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013. /wiki/Bob_Hearn ↩

67. Shi-Jim Yen, Jr-Chang Chen; Tai-Ning Yang; Shun-Chin Hsu (March 2004). "Computer Chinese Chess" (PDF). International Computer Games Association Journal. 27 (1): 3–18. doi:10.3233/ICG-2004-27102. S2CID 10336286. Archived from the original (PDF) on 2007-06-14. https://web.archive.org/web/20070614111609/http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf ↩

68. Hiroyuki Iida; Makoto Sakuta; Jeff Rollason (January 2002). "Computer shogi". Artificial Intelligence. 134 (1–2): 121–144. doi:10.1016/S0004-3702(01)00157-6. https://doi.org/10.1016%2FS0004-3702%2801%2900157-6 ↩

69. H. Adachi; H. Kamekawa; S. Iwata (1987). "Shogi on n × n board is complete in exponential time". Trans. IEICE. J70-D: 1843–1852. ↩

70. F.C. Schadd (2009). Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis (PDF) (Thesis). Maastricht University. Archived from the original (PDF) on 2021-01-14. https://web.archive.org/web/20210114164554/https://project.dke.maastrichtuniversity.nl/games/files/msc/Fschadd_thesis.pdf ↩

71. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF) (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 90-900748-8-0. 90-900748-8-0 ↩

72. John Tromp; Gunnar Farnebäck (2007). "Combinatorics of Go". This paper derives the bounds 48https://tromp.github.io/go/gostate.ps ↩

73. John Tromp (2016). "Number of legal Go positions". https://tromp.github.io/go/legal.html ↩

74. "Statistics on the length of a go game". https://homepages.cwi.nl/~aeb/go/misc/gostat.html ↩

75. J. M. Robson (1983). "The complexity of Go". Information Processing; Proceedings of IFIP Congress. pp. 413–417. ↩

76. Christ-Jan Cox (2006). "Analysis and Implementation of the Game Arimaa" (PDF). https://project.dke.maastrichtuniversity.nl/games/files/msc/Cox_thesis1.pdf ↩

77. David Jian Wu (2011). "Move Ranking and Evaluation in the Game of Arimaa" (PDF). http://icosahedral.net/downloads/djwuthesis.pdf ↩

78. Brian Haskin (2006). "A Look at the Arimaa Branching Factor". http://arimaa.janzert.com/bf_study/ ↩

79. A.F.C. Arts (2010). Competitive Play in Stratego (PDF) (Thesis). Maastricht. https://project.dke.maastrichtuniversity.nl/games/files/msc/Arts_thesis.pdf ↩

80. CDA Evans and Joel David Hamkins (2014). "Transfinite game values in infinite chess". arXiv:1302.4377 [math.LO]. /wiki/ArXiv_(identifier) ↩

81. Stefan Reisch, Joel David Hamkins, and Phillipp Schlicht (2012). "The mate-in-n problem of infinite chess is decidable". Conference on Computability in Europe: 78–88. arXiv:1201.5597.{{cite journal}}: CS1 maint: multiple names: authors list (link) /wiki/ArXiv_(identifier) ↩

82. Alex Churchill, Stella Biderman, and Austin Herrick (2020). "Magic: the Gathering is Turing Complete". arXiv:1904.09828 [cs.AI].{{cite arXiv}}: CS1 maint: multiple names: authors list (link) /wiki/ArXiv_(identifier) ↩

83. Stella Biderman (2020). "Magic: the Gathering is as Hard as Arithmetic". arXiv:2003.05119 [cs.AI]. /wiki/ArXiv_(identifier) ↩

84. Lokshtanov, Daniel; Subercaseaux, Bernardo (May 14, 2022). "Wordle is NP-hard". arXiv:2203.16713 [cs.CC]. /wiki/ArXiv_(identifier) ↩