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.

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

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 (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 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. A full-width tree includes all nodes at each depth.

...
Wikipedia