### State space complexity

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.

## 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 including illegal positions or 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.

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.

### Decision trees

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

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

#### 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 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, or:

GTC ≥ b^d

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

## Example: tic-tac-toe

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

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

Game Board size

(cells)

State-space complexity

(as log to base 10)

Game-tree complexity

(as log to base 10)

Average game length

(plies)

Branching factor Ref Complexity class of suitable generalized game
Tic-tac-toe 9 3 5 9 4 PSPACE-complete[2]
Sim 15 3 8 14 3.7 PSPACE-complete[3]
Pentominoes 64 12 18 10 75 [4] [5] ?, but in PSPACE
Kalah [6] 14 13 18 [4] Generalization is unclear
Connect Four 42 13 21 36 4 [7] [1] ?, but in PSPACE
Domineering (8 × 8) 64 15 27 30 8 [4] ?, but in PSPACE; in P for certain dimensions[8]
Congkak-6 14 15 33 [4]
English draughts (8x8) (checkers) 32 20 or 18 31 70 2.8 [9] or [1] EXPTIME-complete[10]
Awari[11] 12 12 32 60 3.5 [1] Generalization is unclear
Qubic 64 30 34 20 54.2 [1] PSPACE-complete[2]
Fanorona 45 21 46 44 11 [12] ?, but in EXPTIME
Nine Men's Morris 24 10 50 50 10 [1] ?, but in EXPTIME
International draughts (10x10) 50 30 54 90 4 [1] EXPTIME-complete[10]
Chinese checkers (2 sets) 121 23 [13] EXPTIME-complete [14]
Chinese checkers (6 sets) 121 78 [13] EXPTIME-complete [14]
Lines of Action 64 23 64 44 29 [15] ?, but in EXPTIME
Reversi (Othello) 64 28 58 58 10 [1] PSPACE-complete[16]
On Top (2p base game) 72 88 62 31 23.77 [17]
Hex (11x11) 121 57 98 40 280 [4] PSPACE-complete[18]
Gomoku (15x15, freestyle) 225 105 70 30 210 [1] PSPACE-complete[2]
Go (9x9) 81 38 45 [19] [1] EXPTIME-complete[20]
Chess 64 47 123 80 35 [21] EXPTIME-complete[22]
Connect6 361 172 140 30 46000 [23] PSPACE-complete[24]
Backgammon 28 20 144 50-60 250 [25] Generalization is unclear
Xiangqi 90 48 150 95 38 [1] [26] ?, believed to be EXPTIME-complete
Abalone 61 25 154 87 60 [27] ?, but in EXPTIME
Havannah 271 127 157 66 240 [4] [28] ?, but in PSPACE
Quoridor 81 42 162 91 60 [29] ?, but in PSPACE
Carcassonne (2p base game) 72 >40 195 71 55 [30] Generalization is unclear
Amazons (10x10) 100 40 212 84 374 or 299[31] [32] [33] PSPACE-complete[34]
Go (13x13) 169 79 90 [1] [19] EXPTIME-complete[20]
Shogi 81 71 226 115 92 [26] [35] EXPTIME-complete[36]
Arimaa 64 43 402 92 17281 [37] [38] [39] ?, but in EXPTIME
Go (19x19) 361 171 360 150 250 [19] [1] EXPTIME-complete[20]
Stratego 92 115 535 381 21.739 [40]
Double dummy bridge[41] (52) <17 <40 52 5.6