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

Shogi 71 226

Go 172 360