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. Mathematicians playing Konane at a Combinatorial game theory workshop (for technical content, see external link) This article is on the theory of combinatorial games. ...

Measures of game 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 including illegal positions or positions that can never arise in the course of a game. In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ...

• 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 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. In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. ... Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ...

  
  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.

• 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 we would have to evaluate in a minimax search to determinate the value of the initial position. “Minmax” redirects here. ...

  
  It's hard even to estimate the game-tree 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. In computing, tree data structures, and game theory, the branching factor is the number of children of each node. ... In chess, ply refers to a half-move: one turn of one of the players. ...

• 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.)

Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. ...

Example: tic-tac-toe

For tic-tac-toe, a simple upper bound for the size of the state space is 3⁹ = 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. Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ...

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 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.^[2] In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. ... An m,n,k-game is an abstract board game in which two players take turns in placing a stone of their color on an m×n board, the winner being the player who first gets k stones of their own color in a row, horizontally, vertically, or diagonally. ... DSpace is an open source software package which provides the tools for management of digital assets, and is commonly used as the basis for an institutional repository. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In complexity theory, PSPACE-complete is a complexity class. ...

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. 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. Logarithms to various bases: is to base e, is to base 10, and is to base 1. ...

In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computational complexity theory, a generalized game is a game that has been generalized so that it can be played on a board of any size. ... Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. ... In complexity theory, PSPACE-complete is a complexity class. ... A pentomino is a polyomino composed of five (Greek πέντε / pente) congruent squares, connected orthogonally. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... Connect Four (also known as Plot Four) is a two-player board game in which the objective is to be the first to get four of ones own discs in a line. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... English draughts, also called American checkers or straight checkers, commonly called checkers in the U.S., but commonly called draughts in some other countries, is a form of the draughts board game played on an 8×8 board with 12 pieces on each side that may only move and capture... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Owari game from Cameroon. ... a selfmade Qubic game Qubic is a four-in-a-row game played in a 4×4×4 matrix. ... In complexity theory, PSPACE-complete is a complexity class. ... Fanorona is a board game indigenous to Madagascar and derived from Alquerque. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Nine Mens Morris is an abstract strategy board game for two players that emerged from the Roman Empire. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... The starting position International draughts (also called Polish draughts or international checkers) is a board game, one of the variants of draughts. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Chinese checkers Chinese checkers or Chinese chequers is a board game that can be played by two to six people. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Chinese checkers Chinese checkers or Chinese chequers is a board game that can be played by two to six people. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Lines of Action is a two-player abstract strategy board game invented by Claude Soucie. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Reversi and Othello are names for an abstract strategy board game which involves play by two parties on an eight-by-eight square grid with pieces that have two distinct sides. ... In complexity theory, PSPACE-complete is a complexity class. ... Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as a 11x11 rhombus. ... In complexity theory, PSPACE-complete is a complexity class. ... Gomoku, go-moku, or gobang (Japanese: 五目, five points) is a board game traditionally played with go pieces (black and white stones) on a go board (19x19 intersections). ... In complexity theory, PSPACE-complete is a complexity class. ... This article is about the Western board game. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Connect6 (Chinese: 六子棋; Pinyin: liùzǐqí; Japanese: 六目並べ; Korean: 육목) introduced by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University, is a fair and highly complex game. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... Backgammon is a board game for two players in which pieces are moved according to the roll of dice. ... Chinese chess redirects here. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Quoridor is a 2–4-player abstract strategy game designed by Mirko Marchesi and published by both Gigamic Games and Great American Trading Company. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... Shogi ), or Japanese chess, is the most popular of a family of chess variants native to Japan. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Arimaa is a two-player abstract strategy board game that can be played using the same equipment as chess. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Irensei (Japanese: 囲連星) is an abstract strategy board game. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... Go is a strategic board game for two players. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ...

See also

• Go complexity
• Solved board games
• list of NP-complete games and puzzles
• list of PSPACE-complete games and puzzles

A game of Go The game of Go is one of the most popular games in the world, and is in on par with games such as Chess (and its Asian variants) in terms of game theory and as an intellectual activity. ... A two-player game can be solved on several levels. ... Here are some of the more commonly known problems that are NP-complete when expressed as decision problems. ... Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. ...

Notes and references

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 ac} Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 9090074880. 
2. ^ ^{a b c d} Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica 13: 5966. 
3. ^ Hilarie K. Orman: Pentominoes: A First Player Win in Games of no chance, MSRI Publications – Volume 29, 1996, pages 339-344. Online: pdf.
4. ^ Jonathan Schaeffer et al (July 6, 2007). "Checkers is Solved". Science. 
5. ^ ^{a b} J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing, 13 (2): 252–267. 
6. ^ See Allis 1994 for rules
7. ^ S. Iwata and T. Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theor. Comp. Sci. (123): 329–340. 
8. ^ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inf. (15): 167–191. 
9. ^ ^{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).  Shannon gave estimates of 10⁴³ and 10¹²⁰ respectively, smaller than the estimates in the table, which are from Victor Allis's thesis. See Shannon number for details.
10. ^ 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. 
11. ^ ^{a b} Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu (March 2004). "Computer Chinese Chess". International Computer Games Association Journal 27 (1): 3–18. 
12. ^ H. Adachi, H. Kamekawa, and S. Iwata (1987). "Shogi on n × n board is complete in exponential time". Trans. IEICE J70-D: 1843–1852. 
13. ^ ^{a b} Christ-Jan Cox (2006). Analysis and Implementation of the Game Arimaa.
14. ^ Brian Haskin (2007). Arimaa Branching Factor.
15. ^ John Tromp and Gunnar Farnebäck (2007). Combinatorics of Go. This paper derives the bounds 48<log(log(N))<171 on the number of possible games N.
16. ^ J. M. Robson (1983). "The complexity of Go", Information Processing; Proceedings of IFIP Congress, 413–417. 

L. Victor Allis is a Dutch computer expert who works to find better ways of developing artificial intelligence. ... Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001), an American electrical engineer and mathematician, has been called the father of information theory,[1] and was the founder of practical digital circuit design theory. ... L. Victor Allis is a Dutch computer expert who works to find better ways of developing artificial intelligence. ... The Shannon number, 1078, is an estimation of the game-tree complexity of chess. ... Aviezri Frankel in 2005 Aviezri Siegmund Fraenkel is an Israeli Mathematician, who has made notable contributions to combinatorial game theory. ...

External links

• David Eppstein's Computational Complexity of Games and Puzzles