In computer science, board game complexity is a measure of the complexity of a game. It comes in at least four forms: state-space complexity, game-tree complexity, number of move-sequences, computational complexity.
State-space complexity refers to the number of different game-positions that can exist in a game.
Game-tree complexity is normally defined as the product of the games average branching factor and the number of plies (given as half-moves in Chess and as moves in "Go") in an average game. The game-tree complexity is normally higher than the state space complexity due to the fact that the same position can occur in multiple games.
A "move-sequence" is the succession of moves from the "game start" to the "game end". A "move" (Go term) is the action of a player performed during his turn and thereby transforming one "game state" to its successor, its next "game state". The "number of move-sequences" is the total number of move-sequences that might occur legally according to a game's rules. It is expressed as a function in a parameter. A typical parameter is the number of objects that form the board of a game. E.g., N = 64 squares in Chess or N = 361 intersections in Go. Since determining a "number of move-sequences" M(N) is a difficult mathematical problem for many interesting games, one uses bounds to limit the unknown, precise functions: a "lower bound" L(N) or an "upper bound" U(N). The following holds: L(N) < M(N) < U(N). E.g., for Go (with simple rules) trivial bounds are: L(N) = N! and U(N) = N^(3^N). So for the precise "computational complexity" M(N) of Go we can say: N! < M(N) < N^(3^N).
For computational complexity, see the link. In short, there are two types of "computational complexity". One describes the size of required storage space, the other describes the size of required computation time.
What follows is trivia. The really crucial information about a game is its "computational complexity". - Due to the large size of complexities often their logarithms (base 10) are given instead of their actual value. All of the following numbers should be considered with extremely great care. Tiny changes on 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 shown numbers.
| Game | State-space | Game Tree |
|---|---|---|
| Nine Men's Morris | 10 | 50 |
| Awari | 12 | 32 |
| Pentominoes | 12 | 18 |
| Connect Four | 14 | 21 |
| Backgammon | 20 | 144 |
| Checkers | 21 | 31 |
| Lines of Action | 24 | 56 |
| Othello | 28 | 58 |
| Chess | 46 | 123 |
| Xiangqi | ?? | 150 |
| Shogi | 71 | 226 |
| Go | 172 | 360 |
See also: Solved board games