Game complexity

Last updated

Combinatorial game theory has several ways of measuring game complexity . This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.

Contents

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. [1]

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

The next two measures use the idea of a 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. [1] 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 raising the game's average branching factor b to the power of the number of plies d in an average game, or:

.

Computational complexity

The computational complexity of a game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation 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 (in terms of whatever 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 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).

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 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. [2] [3] 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. 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. [4]


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.

Note: ordered by game tree size

GameBoard size

(positions)

State-space complexity

(as log to base 10)

Game-tree complexity

(as log to base 10)

Average game length

(plies)

Branching factorRef Complexity class of suitable generalized game
Tic-tac-toe 93594 PSPACE-complete [4]
Sim 1538143.7 PSPACE-complete [5]
Pentominoes 6412181075 [6] [7] ?, but in PSPACE
Kalah [8] 141318 [6] Generalization is unclear
Connect Four 421321364 [1] [9] ?, but in PSPACE
Domineering (8 × 8)641527308 [6] ?, but in PSPACE; in P for certain dimensions [10]
Congkak 141533 [6]
English draughts (8x8) (checkers) 3220 or 1831702.8 [1] [11] EXPTIME-complete [12]
Awari [13] 121232603.5 [1] Generalization is unclear
Qubic 6430342054.2 [1] PSPACE-complete [4]
Double dummy bridge [nb 1] (52)<17<40525.6PSPACE-complete [14]
Fanorona 4521464411 [15] ?, but in EXPTIME
Nine men's morris 2410505010 [1] ?, but in EXPTIME
Tablut 8127 [16]
International draughts (10x10) 503054904 [1] EXPTIME-complete [12]
Chinese checkers (2 sets)12123 [17] EXPTIME-complete [18]
Chinese checkers (6 sets)12178 [17] EXPTIME-complete [18]
Reversi (Othello)6428585810 [1] PSPACE-complete [19]
OnTop (2p base game)7288623123.77 [20]
Lines of Action 6423644429 [21] ?, but in EXPTIME
Gomoku (15x15, freestyle)2251057030210 [1] PSPACE-complete [4]
Hex (11x11) 12157985096 [6] PSPACE-complete [22]
Chess 64471237035 [23] EXPTIME-complete (without 50-move drawing rule) [24]
Bejeweled and Candy Crush (8x8)64<50 [25] NP-hard
GIPF 37251329029.3 [26]
Connect6 3611721403046000 [27] PSPACE-complete [28]
Backgammon 282014455250 [29] Generalization is unclear
Xiangqi 90401509538 [1] [30] [31] ?, believed to be EXPTIME-complete
Abalone 61251548760 [32] [33] PSPACE-hard, and in EXPTIME
Havannah 27112715766240 [6] [34] PSPACE-complete [35]
Twixt 57214015960452 [36]
Janggi 904416010040 [31] ?, believed to be EXPTIME-complete
Quoridor 81421629160 [37] ?, but in PSPACE
Carcassonne (2p base game)72>401957155 [38] Generalization is unclear
Amazons (10x10) 1004021284374 or 299 [39] [40] [41] PSPACE-complete [42]
Shogi 817122611592 [30] [43] EXPTIME-complete [44]
Go (19x19) 361170360150250 [1] [45] [46] EXPTIME-complete [47]
Arimaa 64434029217281 [48] [49] [50] ?, but in EXPTIME
Stratego 9211553538121.739 [51]
Infinite chess [nb 2] unboundedEXPTIME-complete (without 50-move drawing rule) [24]

Notes

  1. 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.
  2. Infinite chess is a class of games, which includes Chess on an Infinite Plane and Trappist-1 as examples. [52] [53]

See also

Related Research Articles

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<i>Hex</i> (board game) board game

Hex is a strategy board game for two players played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11×11 rhombus. Players alternate placing markers or stones on unoccupied spaces in an attempt to link their opposite sides of the board in an unbroken chain. One player must win; there are no draws. The game has deep strategy, sharp tactics and a profound mathematical underpinning related to the Brouwer fixed-point theorem. It was invented in the 1940s independently by two mathematicians, Piet Hein and John Nash. The game was first marketed as a board game in Denmark under the name Con-tac-tix, and Parker Brothers marketed a version of it in 1952 called Hex; they are no longer in production. Hex can also be played with paper and pencil on hexagonally ruled graph paper.

<i>Sokoban</i> video game

Sokoban is a puzzle video game in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

In computational complexity theory, the complexity class EXPTIME is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p) time, where p(n) is a polynomial function of n. EXPTIME is one class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2-EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound . This can be generalized to higher and higher time bounds. EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space.

A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

Game tree tree diagram used to find and analyze potential moves in a game

In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation.

Complexity class Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.

Generalized game

In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid.

In computational complexity theory, generalized geography is a well-known PSPACE-complete problem.

Shannon number lower bound on the game-tree complexity for chess

The Shannon number, named after the American mathematician Claude Shannon, is a conservative lower bound (not an estimate) of the game-tree complexity of chess of 10120, based on an average of about 103 possibilities for a pair of moves consisting of a move for White followed by one for Black, and a typical game lasting about 40 such pairs of moves.

Go and mathematics Mathematical studies about the game of go

The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, a Chinese scholar in 11th century, estimated that the number of possible board positions is around 10172 in The Dream Pool Essays. In more recent years, research of the game by John H. Conway led to the invention of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).

In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified, using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false. If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

Solving chess means finding an optimal strategy for playing chess, i.e. one by which one of the players can always force a victory, or both can force a draw. It also means more generally solving chess-like games, such as infinite chess. According to Zermelo's theorem, a hypothetically determinable optimal strategy does exist for chess and chess-like games.

In computational complexity theory, and more specifically in the analysis of algorithms with integer data, the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size. The model was proposed by Michael Fredman and Dan Willard, who chose its name "because the dichotomy between the machine model and the problem size is crossed in a reasonable manner."

In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in software that plays board games. In that context MCTS is used to solve the game tree.

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

References

  1. 1 2 3 4 5 6 7 8 9 10 11 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.
  2. "combinatorics - TicTacToe State Space Choose Calculation". Mathematics Stack Exchange. Retrieved 2020-04-08.
  3. T, Brian (2018-10-20), Btsan/generate_tictactoe , retrieved 2020-04-08
  4. 1 2 3 4 Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete)". Acta Informatica. 13 (1): 59–66. doi:10.1007/bf00288536.
  5. Slany, Wolfgang (26 October 2000). The Complexity of Graph Ramsey Games. Springer-Verlag. pp. 186–203. ISBN   9783540430803 . Retrieved 12 April 2018 via dl.acm.org.
  6. 1 2 3 4 5 6 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.
  7. Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance , MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf.
  8. See van den Herik et al for rules.
  9. John Tromp (2010). "John's Connect Four Playground".
  10. Michael Lachmann; Cristopher Moore; Ivan Rapaport (July 2000). "Who wins domineering on rectangular boards?". MSRI Combinatorial Game Theory Research Workshop.Cite journal requires |journal= (help)
  11. 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.
  12. 1 2 J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing . 13 (2): 252–267. doi:10.1137/0213018.
  13. See Allis 1994 for rules
  14. Bonnet, Édouard; Jamain, Florian; Saffidine, Abdallah (2013-08-03). On the complexity of trick-taking card games. AAAI Press. pp. 482–488. ISBN   9781577356332.
  15. 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.
  16. Andrea Galassi (2018). "An Upper Bound on the Complexity of Tablut" (PDF).Cite journal requires |journal= (help)
  17. 1 2 G.I. Bell (2009). "The Shortest Game of Chinese Checkers and Related Problems". Integers. arXiv: 0803.1245 . Bibcode:2008arXiv0803.1245B.
  18. 1 2 Takumi Kasai; Akeo Adachi; Shigeki Iwata (1979). "Classes of Pebble Games and Complete Problems". SIAM Journal on Computing. 8 (4): 574–586. doi:10.1137/0208046. Proves completeness of the generalization to arbitrary graphs.
  19. S. Iwata; T. Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theor. Comput. Sci. 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7.
  20. Robert Briesemeister (2009). Analysis and Implementation of the Game OnTop (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering.
  21. Mark H.M. Winands (2004). Informed Search in Complex Games (PDF) (Ph.D. thesis). Maastricht University, Maastricht, The Netherlands. ISBN   90-5278-429-9.
  22. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform. (15): 167–191.
  23. 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.
  24. 1 2 Aviezri Fraenkel; D. Lichtenstein (1981), "Computing a perfect strategy for n×n chess requires time exponential in n", J. Combin. Theory Ser. A, 31 (2): 199–214, doi: 10.1016/0097-3165(81)90016-9
  25. L. Gualà; S. Leucci; E. Natale (2014). "Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard". arXiv: 1403.5830 [cs.CC].
  26. Diederik Wentink (2001). Analysis and Implementation of the game Gipf (PDF) (Thesis). Maastricht University.
  27. 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.
  28. Hsieh, Ming Yu; Tsai, Shi-Chun (1 October 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 12 April 2018 via dl.acm.org.
  29. Tesauro, Gerald (1 May 1992). "Practical issues in temporal difference learning". Machine Learning. 8 (3–4): 257–277. doi: 10.1007/BF00992697 .
  30. 1 2 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. Archived from the original (PDF) on 2007-06-14.
  31. 1 2 Donghwi Park (2015). "Space-state complexity of Korean chess and Chinese chess". arXiv: 1507.06401 [math.GM].
  32. Chorus, Pascal. "Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search" (PDF). Dept of Knowledge Engineering, Maastricht University. Retrieved 29 March 2012.
  33. Kopczynski, Jacob S (2014). Pushy Computing: Complexity Theory and the Game Abalone (Thesis). Reed College.
  34. Joosten, B. "Creating a Havannah Playing Agent" (PDF). Retrieved 29 March 2012.
  35. E. Bonnet; F. Jamain; A. Saffidine (2014-03-25). "Havannah and TwixT are PSPACE-complete". arXiv: 1403.6518 [cs.CC].
  36. Kevin Moesker (2009). TWIXT: THEORY, ANALYSIS AND IMPLEMENTATION (PDF) (Thesis). Maastricht University, Faculty of Humanities and Sciences of Maastricht University.
  37. 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.
  38. Cathleen Heyden (2009). Implementing a Computer Player for Carcassonne (PDF) (Thesis). Maastricht University, Dept of Knowledge Engineering.
  39. The lower branching factor is for the second player.
  40. Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy (2007). "The Monte-Carlo Approach in Amazons". CiteSeerX   10.1.1.79.7640 .Cite journal requires |journal= (help)
  41. P. P. L. M. Hensgens (2001). "A Knowledge-Based Approach of the Game of Amazons" (PDF). Universiteit Maastricht, Institute for Knowledge and Agent Technology.Cite journal requires |journal= (help)
  42. R. A. Hearn (2005-02-02). "Amazons is PSPACE-complete". arXiv: cs.CC/0502013 .
  43. 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.
  44. H. Adachi; H. Kamekawa; S. Iwata (1987). "Shogi on n × n board is complete in exponential time". Trans. IEICE. J70-D: 1843–1852.
  45. John Tromp; Gunnar Farnebäck (2007). "Combinatorics of Go". This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
  46. John Tromp (2016). "Number of legal Go positions".
  47. J. M. Robson (1983). "The complexity of Go". Information Processing; Proceedings of IFIP Congress. pp. 413–417.
  48. Christ-Jan Cox (2006). "Analysis and Implementation of the Game Arimaa" (PDF).
  49. David Jian Wu (2011). "Move Ranking and Evaluation in the Game of Arimaa" (PDF).
  50. Brian Haskin (2006). "A Look at the Arimaa Branching Factor".
  51. A.F.C. Arts (2010). Competitive Play in Stratego (PDF) (Thesis). Maastricht.
  52. Chess on an Infinite Plane game rules
  53. Trappist-1 game rules