Game complexity
Encyclopedia
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.
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 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.
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.)
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 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.
, 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. 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 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
.
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.
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
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.
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.
Useful when this is too hard to calculate, an upper bound
Upper bound
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
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 treeGame treeIn 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...
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
Tic-tac-toe
Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...
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 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 we would have to evaluate in a minimax
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
search to determine the value of the initial position.
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
Branching factor
In computing, tree data structures, and game theory, the branching factor is the number of children at each node. If this value is not uniform, an average branching factor can be calculated....
to the power of the number of plies in an average game.
- The computational complexityComputational ComplexityComputational Complexity may refer to:*Computational complexity theory*Computational Complexity...
of a game describes the asymptoticAsymptotic analysisIn mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
difficulty of a game as it grows arbitrarily large, expressed in big O notationBig O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
or as membership in a complexity classComplexity classIn computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
. This concept doesn't apply to particular games, but rather to games that have been generalizedGeneralized gameIn 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. For example, generalized chess is the game of chess played on an n-by-n board, with 2n pieces on each side.Complexity theory studies the asymptotic difficulty...
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.)
Example: tic-tac-toe
For tic-tac-toeTic-tac-toe
Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first...
, 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. 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 tic-tac-toe depends on how it is generalized
Generalized game
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. For example, generalized chess is the game of chess played on an n-by-n board, with 2n pieces on each side.Complexity theory studies the asymptotic difficulty...
. 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
DSPACE
In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a...
(mn) by searching the entire game tree. This places it in the important complexity class PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
. With some more work it can be shown to be PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
.
Complexities of some well-known games
Due to the large size of game complexities, this table gives the ceiling of their logarithmLogarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
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.
| Game | Board size (cells) |
State-space complexity (as log Logarithm The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written... to base 10) |
Ref | Game-tree complexity (as log Logarithm The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written... to base 10) |
Ref | Average game length (plies Ply (game theory) In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn".... ) |
Complexity class Complexity class In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:... of suitable generalized game Generalized game 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. For example, generalized chess is the game of chess played on an n-by-n board, with 2n pieces on each side.Complexity theory studies the asymptotic difficulty... |
|---|---|---|---|---|---|---|---|
| Tic-tac-toe Tic-tac-toe Tic-tac-toe, also called wick wack woe and noughts and crosses , is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first... |
9 | 3 | 5 | 9 | PSPACE-complete PSPACE-complete In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time... |
||
| Sim Sim (pencil game) The game of Sim is played by two players on a board consisting of six dots . Each dot is connected to every other dot by a line.Two players take turns coloring any uncolored lines... |
15 | 3 | 8 | 14 | ?, but in PSPACE PSPACE In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :... |
||
| Pentomino Pentomino A pentomino is a polyomino composed of five congruent squares, connected along their edges .... es |
64 | 12 | 18 | 10 | ?, but in PSPACE PSPACE In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :... |
||
| Kalah Kalah Kalah, also called Kalaha or Mancala, is a game in the mancala family invented by William Julius Champion Jr in 1940. This game heavily favors the starting player, who will always win the three-seed to six-seed versions with perfect play... |
14 | 13 | 18 | Generalization is unclear | |||
| Connect Four Connect Four Connect Four is a two-player game in which the players first choose a color and then take turns dropping their colored discs from the top into a seven-column, six-row vertically-suspended grid... |
42 | 13 | 21 | 36 | ?, but in PSPACE PSPACE In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :... |
||
| Domineering Domineering Domineering is a mathematical game played on a sheet of graph paper, with any set of designs traced out. For example, it can be played on a 6×6 square, a checkerboard, an entirely irregular polygon, or any combination thereof. Two players have a collection of dominoes which they place on the grid... (8 × 8) |
64 | 15 | 27 | 32 | ?, but in PSPACE PSPACE In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :... ; in P for certain dimensions |
||
| Congkak-6 | 14 | 15 | 33 | ||||
| English draughts (8x8) (checkers) English draughts English draughts or checkers , also called American checkers or straight checkers or in Israel damka, is a form of draughts board game. Unlike international draughts, it is played on an eight by eight squared board with twelve pieces on each side... |
32 | 20 or 18 | or | 31 | 70 | EXPTIME-complete | |
| Awari Oware Oware is an abstract strategy game of Akan origin. Part of the mancala family, it is played throughout West Africa and the Caribbean. Among its many names are Ayò , Awalé , Wari , Ouri, Ouril or Uril , Warri , Adji , and Awélé... |
12 | 12 | 32 | 60 | Generalization is unclear | ||
| Qubic Qubic Qubic is the brand name of a four-in-a-row game played in a 4×4×4 matrix sold by Parker Brothers starting in 1953. The original box, and the 1972 reissue, described the game as "Parker Brothers 3D Tic Tac Toe Game." Players take turn placing pieces to get four in a row horizontally or... |
64 | 30 | 34 | 20 | PSPACE-complete PSPACE-complete In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time... |
||
| Fanorona Fanorona Fanorona is an abstract strategy board game indigenous to Madagascar.-Introduction:Fanorona has three standard versions: Fanoron-Telo, Fanoron-Dimy, and Fanoron-Tsivy. The difference between these variants is the size of board played on. Fanoron-Telo is played on a 3×3 board and the difficulty of... |
45 | 21 | 46 | 22 | ?, but in EXPTIME EXPTIME In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n.... |
||
| Nine Men's Morris Nine Men's Morris Nine Men's Morris is an abstract strategy board game for two players that emerged from the Roman Empire. The game is also known as Nine Man Morris, Mill, Mills, Merels, Merelles, and Merrills in English.... |
24 | 10 | 50 | ? | ?, but in EXPTIME EXPTIME In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n.... |
||
| International draughts (10x10) International draughts International draughts is a board game, one of the variants of draughts. It is played on a 10×10 board with alternatingly dark and light squares, of which only the 50 dark ones are used. There are two players on opposite sides, with 20 pieces each, light for one player and dark for the other... |
50 | 30 | 54 | 90 | EXPTIME-complete | ||
| Chinese checkers Chinese checkers Chinese checkers is a board game that can be played by two, three, four, or six people, playing individually or with partners... (2 sets) |
121 | 23 | ? | ? | EXPTIME EXPTIME In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n.... -complete |
||
| Chinese checkers Chinese checkers Chinese checkers is a board game that can be played by two, three, four, or six people, playing individually or with partners... (6 sets) |
121 | 78 | ? | ? | EXPTIME EXPTIME In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n.... -complete |
||
| Lines of Action Lines of Action Lines of Action is a two-player abstract strategy board game invented by Claude Soucie. The objective of the game is to connect all of your pieces... |
64 | 23 | 64 | 44 | ?, but in EXPTIME EXPTIME In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n.... |
||
| Reversi Reversi Reversi is a board game involving abstract strategy and played by two players on a board with 8 rows and 8 columns and a set of distinct pieces for each side. Pieces typically are disks with a light and a dark face, each face belonging to one player... |
64 | 28 | 58 | 58 | PSPACE-complete PSPACE-complete In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time... |
||
| On Top On Top "On Top" is the second single by American rapper Twista of his seventh album Category F5. The song features R&B singer Akon and was produced by GoodWill & MGI, "On Top" was confirmed as the second official single of Twista's seventh album, after the lead single Wetter featuring singer Erika... (2p base game) |
72 | 88 | 62 | 31 | |||
| Hex (11x11) Hex (board game) Hex is a board game played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11x11 rhombus. Other popular dimensions are 13x13 and 19x19 as a result of the game's relationship to the older game of Go... |
121 | 57 | 98 | 40 | PSPACE-complete PSPACE-complete In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time... |
||
| Gomoku Gomoku Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game... (15x15, freestyle) |
225 | 105 | 70 | 30 | PSPACE-complete PSPACE-complete In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time... |
||
| Go (9x9) | 81 | 38 | 45 | EXPTIME-complete | |||
| Chess Chess Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player... |
64 | 47 | 123 | 80 | EXPTIME-complete | ||
| Connect6 Connect6 Connect6 introduced in 2003 by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University, is a two-player game similar to Gomoku.... |
361 | 172 | 140 | 30 | PSPACE-complete PSPACE In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :... |
||
| Backgammon Backgammon Backgammon is one of the oldest board games for two players. The playing pieces are moved according to the roll of dice, and players win by removing all of their pieces from the board. There are many variants of backgammon, most of which share common traits... |
28 | 20 | 144 | 50-60 | Generalization is unclear | ||
| Xiangqi Xiangqi Xiangqi is a two-player Chinese board game in the same family as Western chess, chaturanga, shogi, Indian chess and janggi. The present-day form of Xiangqi originated in China and is therefore commonly called Chinese chess in English. Xiangqi is one of the most popular board games in China... |
90 | 48 | 150 | 95 | ?, believed to be EXPTIME-complete | ||
| Havannah Havannah Havannah is an abstract strategy board game invented by Christian Freeling. It is played on a base-10 hexagonal board, ten hexes to a side... |
271 | 127 | 157 | ? | ? | ||
| Quoridor Quoridor Quoridor is a 2- or 4-player abstract strategy game designed by Mirko Marchesi and published by Gigamic Games. Quoridor received the Mensa Mind Game award in 1997 and the Game Of The Year in the USA, France, Canada and Belgium.-Rules of the game:... |
81 | 42 | 162 | 91 | ?, but in PSPACE PSPACE In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :... |
||
| Carcassonne Carcassonne (board game) Carcassonne is a tile-based German-style board game for two to five players, designed by Klaus-Jürgen Wrede and published in 2000 by Hans im Glück in German and Rio Grande Games in English.... (2p base game) |
72 | >40 | 195 | 71 | Generalization is unclear | ||
| Amazons (10x10) Game of the Amazons The Game of the Amazons is a two-player abstract strategy game invented in 1988 by Walter Zamkauskas of Argentina. It is a member of the territorial game family, a distant relative of Go and chess... |
100 | 40 | 212 | 80 | PSPACE-complete PSPACE-complete In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time... |
||
| Go (13x13) | 169 | 79 | 90 | EXPTIME-complete | |||
| Shogi Shogi , also known as Japanese chess, is a two-player board game in the same family as Western chess, chaturanga, and Chinese Xiangqi, and is the most popular of a family of chess variants native to Japan... |
81 | 71 | 226 | 115 | EXPTIME-complete | ||
| Arimaa Arimaa The objective of the game is to move a rabbit of one's own color onto the home rank of the opponent. Thus Gold wins by moving a gold rabbit to the eighth rank, and Silver wins by moving a silver rabbit to the first rank... |
64 | 43 | 402 | 92 | ?, but in EXPTIME EXPTIME In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n.... |
||
| Go (19x19) | 361 | 171 | 360 | 150 | EXPTIME-complete | ||
| Stratego Stratego Stratego is a board game featuring a 10×10 square board and two players with 40 pieces each. Pieces represent individual officers and soldiers in an army. The objective of the game is to either find and capture the opponent's Flag or to capture so many of the opponent's pieces that he/she cannot... |
92 | 115 | 535 | 381 |
See also
- Go complexity
- Solved board games
- Shannon numberShannon numberThe Shannon number, named after Claude Shannon, is an estimated lower bound on the game-tree complexity of chess. Shannon calculated it as an aside in his 1950 paper "Programming a Computer for Playing Chess"...
- list of NP-complete games and puzzles
- list of PSPACE-complete games and puzzles
External links
- David EppsteinDavid EppsteinDavid Arthur Eppstein is an American computer scientist and mathematician. He is professor of computer science at University of California, Irvine. He is known for his work in computational geometry, graph algorithms, and recreational mathematics.-Biography:Born in England of New Zealander...
's Computational Complexity of Games and Puzzles