Game complexity

from Wikipedia, the free encyclopedia

In combinatorial game theory, there are several ways to measure game complexity . These metrics are described below:

  • State space complexity
  • Game tree size
  • Decision Complexity
  • Game tree complexity
  • Computing effort

Game Complexity Metrics

  • The state space complexity of a game is the number of attainable positions from the starting position of the game. If this is too difficult to calculate, an upper limit can often be determined by counting inadmissible positions or those that cannot be reached in the course of the game.
  • The game tree size is the total number of possible game courses. It corresponds to the number of leaf nodes in the game tree .
  • The game tree is usually considerably larger than the state space, since the same positions occur in different games, as moves are performed in different order (e.g. in the tic-tac-toe game, with two Xs and an O, the position can can be 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 calculated by simplifying the game, which only increases the size of the game tree (e.g. allowing illegal moves). However, the game tree is infinite for games in which the number of moves is not limited (e.g. because of the size of the board, or if repetitions are allowed).

The next two metrics are based on the idea of ​​a decision tree . A decision tree is a subtree of the game tree in which each position is marked with "Player A wins", "Player B wins" or "Another move". End positions are marked directly. A position with which player A can achieve a "player A wins" position is also marked with "player A wins". The same procedure is used for player B.

  • The decision-making complexity of a game is the number of leaf nodes in the smallest decision tree, which retains the marking of the starting position (e.g. "Player A wins"). Such a tree contains all decision options for the second player, but only one option at a time for the player who starts the game.
  • The game tree complexity of a game is the number of leaf nodes in the smallest full-width decision tree that maintains the value of the starting position. (A tree in full width always contains all nodes of a depth.) This is the number of positions that one has to search in a minimax procedure in order to determine the value of the initial position. It is difficult to estimate the complexity of the game tree. But for some games a reasonable lower bound can be found by raising the branching factor to the power of the number of half-moves in an average game.
  • The complexity-theoretical computing effort of a game describes the asymptotic degree of difficulty of a game when it is of any size. This is expressed in the O notation or as belonging to a complexity class . This concept is not applicable everywhere, but there are games that have been generalized to be arbitrarily large. Typically, the game is played on an n × n board. (From the point of view of complexity theory , a game whose board size is fixed is a finite automaton that can be solved in O (1), e.g. via a table in which the best move is shown for each position.

Example: Tic Tac Toe

For tic-tac-toe a simple upper bound on the size of the state space is 3 9 = 19,683. (There are 3 states for each box and 9 boxes.) This number contains many illegal positions, such as: B. Positions with 5 crosses and no zeros or positions in which both players have a row full. A more precise estimate can therefore reduce the number to 5,478. If you consider reflections and rotations to be identical, only 765 fundamentally different positions are possible.

A simple upper bound for the game tree is 9! = 362,880 (9 choices for the first move, 8 for the second, 7 for the third, etc.). If you exclude illegal moves you get a maximum of 255,168 possible games. Taking into account the reflections and rotations, the number is reduced to 26,830.

The complexity-theoretical computational effort of Tic Tac Toe depends on how it was generalized. A simple generalization is the m, n, k game. On an n x m board, the first player to fill k boxes in a row wins . It becomes immediately clear that it can be solved in DSPACE ( mn ) by searching through the entire game tree. It is therefore in the PSPACE complexity class . It can be shown to be PSPACE-complete .

Complexities of some popular games

Due to the enormous size of some game complexities, the following table only gives their base 10 logarithm . All numbers should be viewed with caution, as seemingly small changes in the rules can result in large changes in the numbers that are often only rough estimates anyway.

game Board size State space complexity

(as log to base 10)

Game tree complexity

(as log to base 10)

Average playing time in half moves Complexity class of a suitable generalization
Tic-tac-toe 9 3 5 7th PSPACE-Complete
Sim 15th 3 8th 14th ?, but in PSPACE
Pentominos 64 12 18th 10 ?, but in PSPACE
Four wins 42 14th 21st 36 ?, but in PSPACE
Lady (8 × 8) 32 20 or 18 31 70 EXPTIME-Complete
Oware 12 12 32 60 Generalization unclear
Qubic 64 30th 34 20th PSPACE-Complete
Fanorona 45 21st 46 22nd ?, but in EXPTIME
Mill 24 10 50 ? ?, but in EXPTIME
Lady (10 × 10) 50 30? 54 90 EXPTIME-Complete
Halma (2 players) 121 28 ? ? EXPTIME-Complete
Halma (6 players) 121 78 ? ? EXPTIME-Complete
Lines of Action 64 23 64 44 ? but EXPTIME
Reversi 64 28 58 58 PSPACE-Complete
Hex (11 × 11) 121 56 ? 40 PSPACE-Complete
Gomoku (15 × 15, freestyle) 225 105? 70 30th PSPACE-Complete
chess 64 50 123 80 EXPTIME-Complete (without the 50-move rule )
Connect6 361 172 70 or 140 15 or 30 PSPACE-Complete
backgammon 28 20th 144 50-60 Generalization unclear
Xiangqi 90 40 150 95 ?, probably in EXPTIME-Complete
Janggi 90 44 160 100 ?, probably in EXPTIME-Complete
Quoridor 81 42 162 ? ?, but in PSPACE
Amazons (10 × 10) 100 ≤ 40 ? ? PSPACE-Complete
Shogi 81 71 226 110? EXPTIME-Complete
Arimaa 64 43 296 70 ? but EXPTIME
Go (19 × 19) 361 171 360 150 EXPTIME-Complete
Minesweeper 720 ? ? ? NP-complete

Web links

Individual evidence

  1. ↑ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab Victor Allis : Searching for Solutions in Games and Artificial Intelligence . 1994, ISBN 90-90-07488-0 ( fragrieu.free.fr [PDF] Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands).
  2. ↑ a b c d Stefan Reisch: Gobang is PSPACE-complete (Gobang is PSPACE-complete) . In: Acta Informatica . 13, No. 1, 1980, pp. 59-66. doi : 10.1007 / BF00288536 .
  3. ^ Wolfgang Slany: The Complexity of Graph Ramsey Games
  4. ^ Hilarie K. Orman: Pentominoes: A First Player Win in Games of No Chance , MSRI Publications - Volume 29, 1996, pages 339-344. Online: pdf .
  5. ↑ Jonathan Schaeffer et al .: Checkers is Solved . In: Science . July 6, 2007.
  6. ^ A b J. M. Robson: N by N checkers is Exptime complete . In: SIAM Journal on Computing , . 13, No. 2, 1984, pp. 252-267. doi : 10.1137 / 0213018 .
  7. ↑ Rules of the game see Allis 1994
  8. ↑ a b M.PD Schadd, MHM Winands, JWHM Uiterwijk, HJ van den Herik and MHJ Bergsma: Best Play in Fanorona leads to Draw Archived from the original on July 17, 2011. Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. In: New Mathematics and Natural Computation . 4, No. 3, 2008, pp. 369-387. doi : 10.1142 / S1793005708001124 . Retrieved November 14, 2009. @1@ 2Template: Webachiv / IABot / www.personeel.unimaas.nl
  9. ↑ a b Takumi Kasai, Akeo Adachi, and Shigeki Iwata: Classes of Pebble Games and Complete Problems , SIAM Journal on Computing, Volume 8, 1979, pages 574-586. Proves the completeness of the generalization to any graph.
  10. ^ A b c Mark HM Winands: Informed Search in Complex Games . 2004, ISBN 90-5278-429-9 ( personeel.unimaas.nl [PDF] Ph.D. Thesis, Maastricht University, Maastricht, The Netherlands).
  11. ^ S. Iwata and T. Kasai: The Othello game on an n * n board is PSPACE-complete . In: Theor. Comp. Sci. . 123, No. 123, 1994, pp. 329-340. doi : 10.1016 / 0304-3975 (94) 90131-7 .
  12. ↑ Stefan Reisch: Hex is PSPACE-complete (Hex is PSPACE-complete) . In: Acta Inf. . No. 15, 1981, pp. 167-191. doi : 10.1007 / BF00288964 .
  13. ↑ a b The size of the state space and the game tree for chess were first estimated in Claude Shannon : Programming a Computer for Playing Chess. Archived from the original on March 15, 2010. Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. In: Philosophical Magazine . 41, No. 314, 1950. Retrieved May 13, 2007. @1@ 2Template: Webachiv / IABot / archive.computerhistory.org Shannon gave the estimates 10 43 and 10 120 , respectively , values ​​smaller than those in the table, which come from the work of Victor Allis ' s. See Shannon number for details.
  14. ↑ Aviezri Fraenkel , D. Lichtenstein: Computing a perfect strategy for n × n chess requires time exponential in n . In: J. Comb. Th. A . No. 31, 1981, pp. 199-214. doi : 10.1016 / 0097-3165 (81) 90016-9 .
  15. ↑ On the fairness and complexity of generalized k-in-a-row games
  16. ↑ books.nips.cc ( Memento of the original dated February 26, 2009 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot / books.nips.cc
  17. ↑ a b Donghwi Park: Space-state complexity of Korean chess and Chinese chess . 2015, arxiv : 1507.06401 .
  18. ↑ a b c Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu: Computer Chinese Chess . In: International Computer Games Association Journal . tape 27 , no. 1 , March 2004, p. 3-18 ( csie.ndhu.edu.tw [PDF]). csie.ndhu.edu.tw ( Memento of the original from July 9, 2015 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  @1@ 2Template: Webachiv / IABot / www.csie.ndhu.edu.tw
  19. ^ RA Hearn: Amazons is PSPACE-complete . February 2, 2005, arxiv : cs / 0502013 .
  20. ↑ H. Adachi, H. Kamekawa, and S. Iwata: Shogi on n × n board is complete in exponential time . In: Trans. IEICE . J70-D, 1987, pp. 1843-1852.
  21. ↑ a b Christ-Jan Cox: Analysis and Implementation of the Game Arimaa (PDF; 806 kB) 2006. Retrieved on February 15, 2011.
  22. ^ Brian Haskin: Arimaa Branching Factor . 2007. Retrieved February 15, 2011.
  23. ↑ Combinatorics of Go  ( page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. This work is derived the estimates 48 <log (log ( N )) <171 for the number of possible game histories N ago.@1@ 2Template: Dead Link / www.cwi.nl  
  24. ^ JM Robson: Information Processing; Proceedings of IFIP Congress . 1983, The complexity of Go, p. 413-417 .
  25. ^ R. Kaye: Minesweeper is NP-complete. In: The Mathematical Intelligencer. Volume 22, Article 2, pp. 9-15, Springer-Verlag, 2000, doi: 10.1007 / BF03025367