 Game complexity

Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: statespace complexity, game tree size, decision complexity, gametree complexity, and computational complexity.
Contents
Measures of game complexity
 The statespace complexity of a game is the number of legal game positions reachable from the initial position of the game.^{[1]}
Useful when this is too hard to calculate, an upper bound can often be computed by including illegal positions or positions that can never arise in the course of a game.
 The game tree size is the total number of possible games that can be played: it's 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 tictactoe 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.
However, 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 infinite.
The next two measures use the idea of a decision tree. A decision tree 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.)
 The decision complexity of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position. Such a tree includes all possible decisions for the player to move second, but only one possibility for each decision for the player who starts the game.
 The gametree complexity of a game is the number of leaf nodes in the smallest fullwidth decision tree that establishes the value of the initial position.^{[1]} A fullwidth tree includes all nodes at each depth.
This is an estimate of the number of positions we would have to evaluate in a minimax search to determine the value of the initial position.
It's hard even to estimate the gametree complexity, but for some games a reasonable lower bound can be given by raising the game's average branching factor to the power of the number of plies in an average game.
 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 nbyn 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 lookup table from positions to the best move in each position.)
Example: tictactoe
For tictactoe, a simple upper bound for the size of the state space is 3^{9} = 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. And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.
A simple upper bound for the size of the game tree is 9! = 362,880. (There are nine positions for the first move, eight for the second, and so on.) This includes illegal games that continue after one side has won. A more careful count 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 tictactoe depends on how it is generalized. A natural generalization is to m,n,kgames: 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 PSPACEcomplete.^{[2]}
Complexities of some wellknown games
Due to the large size of game complexities, this table gives the ceiling of their logarithm to base 10. All of the following numbers should be considered with caution: seeminglyminor 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.
Game Board size (cells)
Statespace complexity (as log to base 10)
Ref Gametree complexity (as log to base 10)
Ref Average game length (plies)
Complexity class of suitable generalized game Tictactoe 9 3 5 9 PSPACEcomplete^{[2]} Sim 15 3 8 14 ?, but in PSPACE^{[3]} Pentominoes 64 12 ^{[4]} 18 ^{[4]} 10 ^{[5]} ?, but in PSPACE Kalah ^{[6]} 14 13 ^{[4]} 18 ^{[4]} Generalization is unclear Connect Four 42 13 ^{[7]} 21 ^{[1]} 36^{[1]} ?, but in PSPACE Domineering (8 × 8) 64 15 ^{[4]} 27 ^{[4]} 32 ?, but in PSPACE; in P for certain dimensions^{[8]} Congkak6 14 15 ^{[4]} 33 ^{[4]} English draughts (8x8) (checkers) 32 20 or 18 ^{[9]} or ^{[1]} 31 ^{[1]} 70^{[1]} EXPTIMEcomplete^{[10]} Awari^{[11]} 12 12 ^{[1]} 32 ^{[1]} 60^{[1]} Generalization is unclear Qubic 64 30 ^{[1]} 34 ^{[1]} 20^{[1]} PSPACEcomplete^{[2]} Fanorona 45 21 ^{[12]} 46 ^{[12]} 22 ?, but in EXPTIME Nine Men's Morris 24 10 ^{[1]} 50 ^{[1]} ? ?, but in EXPTIME International draughts (10x10) 50 30 ^{[1]} 54 ^{[1]} 90^{[1]} EXPTIMEcomplete^{[10]} Chinese checkers (2 sets) 121 23 ^{[13]} ? ? EXPTIMEcomplete ^{[14]} Chinese checkers (6 sets) 121 78 ? ? EXPTIMEcomplete ^{[14]} Lines of Action 64 23 ^{[15]} 64 ^{[15]} 44^{[15]} ?, but in EXPTIME Reversi 64 28 ^{[1]} 58 ^{[1]} 58^{[1]} PSPACEcomplete^{[16]} On Top (2p base game) 72 88 ^{[17]} 62 ^{[17]} 31 Hex (11x11) 121 57 ^{[4]} 98 ^{[4]} 40 PSPACEcomplete^{[18]} Gomoku (15x15, freestyle) 225 105 ^{[1]} 70 ^{[1]} 30^{[1]} PSPACEcomplete^{[2]} Go (9x9) 81 38 ^{[19]} 45^{[1]} EXPTIMEcomplete^{[20]} Chess 64 47 ^{[21]} 123 ^{[21]} 80 EXPTIMEcomplete^{[22]} Connect6 361 172 ^{[23]} 140 ^{[23]} 30 PSPACEcomplete^{[24]} Backgammon 28 20 144 5060^{[25]} Generalization is unclear Xiangqi 90 48 ^{[1]} 150 ^{[1]} 95^{[26]} ?, believed to be EXPTIMEcomplete Havannah 271 127 ^{[4]} 157 ^{[4]} ? ? Quoridor 81 42 162 ^{[27]} 91^{[27]} ?, but in PSPACE Carcassonne (2p base game) 72 >40 ^{[28]} 195 ^{[28]} 71 Generalization is unclear Amazons (10x10) 100 40 ^{[29]} 212 ^{[29]} 80^{[30]} PSPACEcomplete^{[31]} Go (13x13) 169 79 ^{[19]} 90^{[1]} EXPTIMEcomplete^{[20]} Shogi 81 71 ^{[26]} 226 ^{[26]} 115 ^{[32]} EXPTIMEcomplete^{[33]} Arimaa 64 43 ^{[34]} 402 ^{[35]} 92^{[35]} ?, but in EXPTIME Go (19x19) 361 171 ^{[19]} 360 ^{[1]} 150^{[1]} EXPTIMEcomplete^{[20]} Stratego 92 115 ^{[36]} 535 ^{[36]} 381^{[36]} See also
 Go complexity
 Solved board games
 Shannon number
 list of NPcomplete games and puzzles
 list of PSPACEcomplete games and puzzles
Notes and references
 ^ ^{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} ^{ac} ^{ad} Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (Ph.D. thesis). University of Limburg, Maastricht, The Netherlands. ISBN 9090074880. http://fragrieu.free.fr/SearchingForSolutions.pdf.
 ^ ^{a} ^{b} ^{c} ^{d} Stefan Reisch (1980). "Gobang ist PSPACEvollstandig (Gomoku is PSPACEcomplete)". Acta Informatica 13: 5966.
 ^ Wolfgang Slany: The Complexity of Graph Ramsey Games
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} ^{i} ^{j} ^{k} ^{l} 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/S00043702(01)001527.
 ^ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339344. Online: pdf.
 ^ See van den Herik et al for rules.
 ^ John Tromp (2010). "John's Connect Four Playground". http://www.cwi.nl/~tromp/c4/c4.html.
 ^ Michael Lachmann; Christopher Moore; Ivan Rapaport (July 2000). Who wins domineering on rectangular boards?. MSRI Combinatorial Game Theory Research Workshop.
 ^ Jonathan Schaeffer et al. (July 6, 2007). "Checkers is Solved". Science 317 (5844): 1518–1522. doi:10.1126/science.1144079. PMID 17641166.
 ^ ^{a} ^{b} J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing, 13 (2): 252–267. doi:10.1137/0213018.
 ^ See Allis 1994 for rules
 ^ ^{a} ^{b} M.P.D. Schadd, M.H.M. Winands, J.W.H.M. Uiterwijk, H.J. van den Herik and M.H.J. Bergsma (2008). "Best Play in Fanorona leads to Draw". New Mathematics and Natural Computation 4 (3): 369–387. doi:10.1142/S1793005708001124. http://www.personeel.unimaas.nl/MaartenSchadd/Papers/2008FanoronaJNMNC.pdf.
 ^ G.I. Bell (2009). "The Shortest Game of Chinese Checkers and Related Problems". Integers. arXiv:0803.1245. http://emis.ams.org.
 ^ ^{a} ^{b} Takumi Kasai, Akeo Adachi, and 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.
 ^ ^{a} ^{b} ^{c} Mark H.M. Winands (2004). Informed Search in Complex Games (Ph.D. thesis). Maastricht University, Maastricht, The Netherlands. ISBN 9052784299. http://www.personeel.unimaas.nl/mwinands/documents/informed_search.pdf.
 ^ S. Iwata and T. Kasai (1994). "The Othello game on an n*n board is PSPACEcomplete". Theor. Comp. Sci. 123 (2): 329–340. doi:10.1016/03043975(94)901317.
 ^ ^{a} ^{b} Robert Briesemeister (2009). Analysis and Implementation of the Game OnTop (Thesis). Maastricht University, Dept of Knowledge Engineering. http://www.unimaas.nl/games/files/msc/briesemeister.pdf.
 ^ Stefan Reisch (1981). "Hex ist PSPACEvollständig (Hex is PSPACEcomplete)". Acta Inf. (15): 167–191.
 ^ ^{a} ^{b} ^{c} John Tromp and Gunnar Farnebäck (2007). "Combinatorics of Go". http://www.cwi.nl/~tromp/go/gostate.ps. This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
 ^ ^{a} ^{b} ^{c} J. M. Robson (1983). "The complexity of Go". Information Processing; Proceedings of IFIP Congress. pp. 413–417.
 ^ ^{a} ^{b} The size of the state space and game tree for chess were first estimated in Claude Shannon (1950). "Programming a Computer for Playing Chess". Philosophical Magazine 41 (314). http://archive.computerhistory.org/projects/chess/related_materials/text/20%20and%2021.Programming_a_computer_for_playing_chess.shannon/20%20and%2021.Programming_a_computer_for_playing_chess.shannon.062303002.pdf. Shannon gave estimates of 10^{43} and 10^{120} respectively, smaller than the upper bound in the table, which is detailed in Shannon number.
 ^ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214.
 ^ ^{a} ^{b} ChangMing Xu; Ma, Z.M.; JunJie Tao; XinHe Xu (2009). "Enhancements of proof number search in connect6". 2009 Chinese Control and Decision Conference. pp. 4525. doi:10.1109/CCDC.2009.5191963. ISBN 9781424427222.
 ^ On the fairness and complexity of generalized kinarow games
 ^ http://books.nips.cc/papers/txt/nips04/0259.txt
 ^ ^{a} ^{b} ^{c} ShiJim Yen, JrChang Chen, TaiNing Yang, and ShunChin Hsu (March 2004). "Computer Chinese Chess". International Computer Games Association Journal 27 (1): 3–18. http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf.
 ^ ^{a} ^{b} Lisa Glendenning (May 2005). Mastering Quoridor (Thesis). doi:10.1.1.100.5204.
 ^ ^{a} ^{b} Cathleen Heyden (2009). Implementing a Computer Player for Carcassonne (Thesis). Maastricht University, Dept of Knowledge Engineering. http://www.unimaas.nl/games/files/msc/masterthesiscarcassonne.pdf.
 ^ ^{a} ^{b} P. P. L. M. Hensgens (2001). A KnowledgeBased Approach of the Game of Amazons. Universiteit Maastricht, Institute for Knowledge and Agent Technology. http://www.unimaas.nl/games/files/msc/Hensgens_thesis.pdf.
 ^ Julien Kloetzer; Hiroyuki Iida; Bruno Bouzy (2007). The MonteCarlo Approach in Amazons. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.7640.
 ^ R. A. Hearn (20050202). "Amazons is PSPACEcomplete". arXiv:cs.CC/0502013 [cs.CC].
 ^ Hiroyuki Iida, Makoto Sakuta, Jeff Rollason (january 2002). Computer shogi. 134. pp. 121–144. doi:10.1016/S00043702(01)001576+journal+=+Artificial+Intelligence.
 ^ H. Adachi, H. Kamekawa, and S. Iwata (1987). "Shogi on n × n board is complete in exponential time". Trans. IEICE J70D: 1843–1852.
 ^ ChristJan Cox (2006). "Analysis and Implementation of the Game Arimaa". http://www.unimaas.nl/games/files/msc/Cox_thesis1.pdf.
 ^ ^{a} ^{b} David Jian Wu (2011). "Move Ranking and Evaluation in the Game of Arimaa". http://icosahedral.net/downloads/djwuthesis.pdf.
 ^ ^{a} ^{b} ^{c} A.F.C. Arts (2010). Competitive Play in Stratego (Thesis). http://www.unimaas.nl/games/files/msc/Arts_thesis.pdf.
External links
Categories:
Wikimedia Foundation. 2010.