Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: statespace complexity, game tree size, decision complexity, gametree complexity, and computational complexity.
Measures of game complexity
Statespace complexity
The statespace complexity of a game is the number of legal game positions reachable from the initial position of the game.^{[1]}
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.
Game tree size
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 tictactoe 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.
Decision trees
The next two measures use the idea of a decision tree. A decision tree 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
Decision complexity of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position. Such a tree includes all possible decisions for the player to move second, but only one possibility for each decision for the player who starts the game.
Gametree complexity
The gametree complexity of a game is the number of leaf nodes in the smallest fullwidth decision tree that establishes the value of the initial position.^{[1]} A fullwidth tree includes all nodes at each depth.
This is an estimate of the number of positions we would have to evaluate in a minimax search to determine the value of the initial position.
It's hard even to estimate the gametree complexity, but for some games a reasonable lower bound can be given by raising the game's average branching factor to the power of the number of plies in an average game, or:
GTC ≥ b^d
Computational complexity
The computational complexity of a game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation or as membership in a complexity class. This concept doesn't apply to particular games, but rather to games that have been generalized so they can be made arbitrarily large, typically by playing them on an nbyn board. (From the point of view of computational complexity a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a lookup table from positions to the best move in each position.)
Example: tictactoe
For tictactoe, a simple upper bound for the size of the state space is 3^{9} = 19,683. (There are three states for each cell and nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478. And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.
A simple upper bound for the size of the game tree is 9! = 362,880. (There are nine positions for the first move, eight for the second, and so on.) This includes illegal games that continue after one side has won. A more careful count gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games.
The computational complexity of tictactoe depends on how it is generalized. A natural generalization is to m,n,kgames: played on an m by n board with winner being the first player to get k in a row. It is immediately clear that this game can be solved in DSPACE(mn) by searching the entire game tree. This places it in the important complexity class PSPACE. With some more work it can be shown to be PSPACEcomplete.^{[2]}
Complexities of some wellknown games
Due to the large size of game complexities, this table gives the ceiling of their logarithm to base 10. All of the following numbers should be considered with caution: seeminglyminor changes to 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 numbers shown.
Game

Board size
(cells)

Statespace complexity
(as log to base 10)

Gametree complexity
(as log to base 10)

Average game length
(plies)

Branching factor

Ref

Complexity class of suitable generalized game

Tictactoe

9

3

5

9

4


PSPACEcomplete^{[2]}

Sim

15

3

8

14

3.7


PSPACEcomplete^{[3]}

Pentominoes

64

12

18

10

75

^{[4]} ^{[5]}

?, but in PSPACE

Kalah ^{[6]}

14

13

18



^{[4]}

Generalization is unclear

Connect Four

42

13

21

36

4

^{[7]} ^{[1]}

?, but in PSPACE

Domineering (8 × 8)

64

15

27

30

8

^{[4]}

?, but in PSPACE; in P for certain dimensions^{[8]}

Congkak6

14

15

33



^{[4]}


English draughts (8x8) (checkers)

32

20 or 18

31

70

2.8

^{[9]} or ^{[1]}

EXPTIMEcomplete^{[10]}

Awari^{[11]}

12

12

32

60

3.5

^{[1]}

Generalization is unclear

Qubic

64

30

34

20

54.2

^{[1]}

PSPACEcomplete^{[2]}

Fanorona

45

21

46

44

11

^{[12]}

?, but in EXPTIME

Nine Men's Morris

24

10

50

50

10

^{[1]}

?, but in EXPTIME

International draughts (10x10)

50

30

54

90

4

^{[1]}

EXPTIMEcomplete^{[10]}

Chinese checkers (2 sets)

121

23




^{[13]}

EXPTIMEcomplete ^{[14]}

Chinese checkers (6 sets)

121

78




^{[13]}

EXPTIMEcomplete ^{[14]}

Lines of Action

64

23

64

44

29

^{[15]}

?, but in EXPTIME

Reversi (Othello)

64

28

58

58

10

^{[1]}

PSPACEcomplete^{[16]}

On Top (2p base game)

72

88

62

31

23.77

^{[17]}


Hex (11x11)

121

57

98

40

280

^{[4]}

PSPACEcomplete^{[18]}

Gomoku (15x15, freestyle)

225

105

70

30

210

^{[1]}

PSPACEcomplete^{[2]}

Go (9x9)

81

38


45


^{[19]} ^{[1]}

EXPTIMEcomplete^{[20]}

Chess

64

47

123

80

35

^{[21]}

EXPTIMEcomplete^{[22]}

Connect6

361

172

140

30

46000

^{[23]}

PSPACEcomplete^{[24]}

Backgammon

28

20

144

5060

250

^{[25]}

Generalization is unclear

Xiangqi

90

48

150

95

38

^{[1]} ^{[26]}

?, believed to be EXPTIMEcomplete

Abalone

61

25

154

87

60

^{[27]}

?, but in EXPTIME

Havannah

271

127

157

66

240

^{[4]} ^{[28]}

?, but in PSPACE

Quoridor

81

42

162

91

60

^{[29]}

?, but in PSPACE

Carcassonne (2p base game)

72

>40

195

71

55

^{[30]}

Generalization is unclear

Amazons (10x10)

100

40

212

84

374 or 299^{[31]}

^{[32]} ^{[33]}

PSPACEcomplete^{[34]}

Go (13x13)

169

79


90


^{[1]} ^{[19]}

EXPTIMEcomplete^{[20]}

Shogi

81

71

226

115

92

^{[26]} ^{[35]}

EXPTIMEcomplete^{[36]}

Arimaa

64

43

402

92

17281

^{[37]} ^{[38]} ^{[39]}

?, but in EXPTIME

Go (19x19)

361

171

360

150

250

^{[19]} ^{[1]}

EXPTIMEcomplete^{[20]}

Stratego

92

115

535

381

21.739

^{[40]}


Double dummy bridge^{[41]}

(52)

<17

<40

52

5.6



See also
Notes and references
External links
 Computational Complexity of Games and Puzzles
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.