Main Page | See live article | Alphabetical index

Board game complexity

In computer science, board game complexity is a measure of the complexity of a game. It comes in two forms, state-space complexity and game-tree 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 (half-moves) 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.

Due to the large size of these complexities often their logarithms (base 10) are given instead of their actual value.

Logs of Complexities
GameState-spaceGame Tree
Nine Men's Morris1050
Awari1232
Pentominoes1218
Connect Four1421
Backgammon20144
Checkers2131
Lines of Action2456
Othello2858
Chess46123
Shogi71226
Go172360

See also: Solved board games