Complexities of Some Well-known 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: seemingly-minor 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) |
State-space complexity
(as log to base 10) |
Ref | Game-tree complexity
(as log to base 10) |
Ref | Average game length
(plies) |
Complexity class of suitable generalized game |
|---|---|---|---|---|---|---|---|
| Tic-tac-toe | 9 | 3 | 5 | 9 | PSPACE-complete | ||
| Sim | 15 | 3 | 8 | 14 | ?, but in PSPACE | ||
| Pentominoes | 64 | 12 | 18 | 10 | ?, but in PSPACE | ||
| Kalah | 14 | 13 | 18 | Generalization is unclear | |||
| Connect Four | 42 | 13 | 21 | 36 | ?, but in PSPACE | ||
| Domineering (8 × 8) | 64 | 15 | 27 | 32 | ?, but in PSPACE; in P for certain dimensions | ||
| Congkak-6 | 14 | 15 | 33 | ||||
| English draughts (8x8) (checkers) | 32 | 20 or 18 | or | 31 | 70 | EXPTIME-complete | |
| Awari | 12 | 12 | 32 | 60 | Generalization is unclear | ||
| Qubic | 64 | 30 | 34 | 20 | PSPACE-complete | ||
| Fanorona | 45 | 21 | 46 | 22 | ?, but in EXPTIME | ||
| Nine Men's Morris | 24 | 10 | 50 | ? | ?, but in EXPTIME | ||
| International draughts (10x10) | 50 | 30 | 54 | 90 | EXPTIME-complete | ||
| Chinese checkers (2 sets) | 121 | 23 | ? | ? | EXPTIME-complete | ||
| Chinese checkers (6 sets) | 121 | 78 | ? | ? | EXPTIME-complete | ||
| Lines of Action | 64 | 23 | 64 | 44 | ?, but in EXPTIME | ||
| Reversi | 64 | 28 | 58 | 58 | PSPACE-complete | ||
| On Top (2p base game) | 72 | 88 | 62 | 31 | |||
| Hex (11x11) | 121 | 57 | 98 | 40 | PSPACE-complete | ||
| Gomoku (15x15, freestyle) | 225 | 105 | 70 | 30 | PSPACE-complete | ||
| Go (9x9) | 81 | 38 | 45 | EXPTIME-complete | |||
| Chess | 64 | 47 | 123 | 80 | EXPTIME-complete | ||
| Connect6 | 361 | 172 | 140 | 30 | PSPACE-complete | ||
| Backgammon | 28 | 20 | 144 | 50-60 | Generalization is unclear | ||
| Xiangqi | 90 | 48 | 150 | 95 | ?, believed to be EXPTIME-complete | ||
| Abalone | 61 | 25 | 154 | 87 | ?, but in EXPTIME | ||
| Havannah | 271 | 127 | 157 | 66 | ?, but in PSPACE | ||
| Quoridor | 81 | 42 | 162 | 91 | ?, but in PSPACE | ||
| Carcassonne (2p base game) | 72 | >40 | 195 | 71 | Generalization is unclear | ||
| Amazons (10x10) | 100 | 40 | 212 | 80 | PSPACE-complete | ||
| Go (13x13) | 169 | 79 | 90 | EXPTIME-complete | |||
| Shogi | 81 | 71 | 226 | 115 | EXPTIME-complete | ||
| Arimaa | 64 | 43 | 402 | 92 | ?, but in EXPTIME | ||
| Go (19x19) | 361 | 171 | 360 | 150 | EXPTIME-complete | ||
| Stratego | 92 | 115 | 535 | 381 |
Read more about this topic: Game Complexity
Famous quotes containing the words complexities of, complexities, well-known and/or games:
“From infancy, a growing girl creates a tapestry of ever-deepening and ever- enlarging relationships, with her self at the center. . . . The feminine personality comes to define itself within relationship and connection, where growth includes greater and greater complexities of interaction.”
—Jeanne Elium (20th century)
“From infancy, a growing girl creates a tapestry of ever-deepening and ever- enlarging relationships, with her self at the center. . . . The feminine personality comes to define itself within relationship and connection, where growth includes greater and greater complexities of interaction.”
—Jeanne Elium (20th century)
“The Ultimate Day really begins the night before, when you sit up until one o’clock trying to get things into trunk and bags. This is when you discover the well-known fact that summer air swells articles to twice or three times their original size.”
—Robert Benchley (1889–1945)
“Intelligence and war are games, perhaps the only meaningful games left. If any player becomes too proficient, the game is threatened with termination.”
—William Burroughs (b. 1914)