Game complexity


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.
When this is too hard to calculate, an upper bound can often be computed by also counting illegal positions, meaning 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. 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 until it becomes tractable.
For games where the number of moves is not limited the game tree is generally infinite.

Decision trees

The next two measures use the idea of a decision tree, which 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 by examining only other positions in the graph.

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.

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. A full-width tree includes all nodes at each depth.
This is an estimate of the number of positions one would have to evaluate in a minimax search to determine the value of the initial position.
It is hard even to estimate the game-tree complexity, but for some games an approximation can be given by raising the game's average branching factor b to the power of the number of plies d in an average game, or:

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.
The asymptotic complexity is defined by the most efficient algorithm for solving the game; the most common complexity measure is always lower-bounded by the logarithm of the asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexity of any particular algorithm that works for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of space or computer memory used by the computation. It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be PSPACE-hard, and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well.
For tic-tac-toe, a simple upper bound for the size of the state space is 39 = 19,683. 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.
To bound the game tree, there are 9 possible initial moves, 8 possible responses, and so on, so that there are at most 9! or 362,880 total games. However, games may take less than 9 moves to resolve, and an exact enumeration 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 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.

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 by tremendous factors, which might easily be much greater than the numbers shown.
Note: ordered by game tree size
GameBoard size
State-space complexity
Game-tree complexity
Average game length
Branching factorRefComplexity class of suitable generalized game
Tic-tac-toe93594PSPACE-complete
Sim1538143.7PSPACE-complete
Pentominoes6412181075?, but in PSPACE
Kalah141318Generalization is unclear
Connect Four421321364?, but in PSPACE
Domineering 641527308?, but in PSPACE; in P for certain dimensions
Congkak141533
English draughts 3220 or 1831702.8EXPTIME-complete
Awari121232603.5Generalization is unclear
Qubic6430342054.2PSPACE-complete
Double dummy bridge<17<40525.6PSPACE-complete
Fanorona4521464411?, but in EXPTIME
Nine men's morris2410505010?, but in EXPTIME
International draughts 503054904EXPTIME-complete
Chinese checkers 12123EXPTIME-complete
Chinese checkers 12178EXPTIME-complete
Reversi 6428585810PSPACE-complete
OnTop 7288623123.77
Lines of Action6423644429?, but in EXPTIME
Gomoku 2251057030210PSPACE-complete
Hex 12157985096PSPACE-complete
Chess64471237035EXPTIME-complete
Bejeweled and Candy Crush 64<50NP-hard
GIPF37251329029.3
Connect63611721403046000PSPACE-complete
Backgammon282014455250Generalization is unclear
Xiangqi90401509538?, believed to be EXPTIME-complete
Abalone61251548760PSPACE-hard, and in EXPTIME
Havannah27112715766240PSPACE-complete
Twixt57214015960452
Janggi904416010040?, believed to be EXPTIME-complete
Quoridor81421629160?, but in PSPACE
Carcassonne 72>401957155Generalization is unclear
Amazons 1004021284374 or 299PSPACE-complete
Shogi817122611592EXPTIME-complete
Go 361170360150250EXPTIME-complete
Arimaa64434029217281?, but in EXPTIME
Stratego9211553538121.739
Infinite chessunboundedEXPTIME-complete