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

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