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)
“Nature is an endless combination and repetition of a very few laws. She hums the old well-known air through innumerable variations.”
—Ralph Waldo Emerson (1803–1882)
“Whatever games are played with us, we must play no games with ourselves, but deal in our privacy with the last honesty and truth.”
—Ralph Waldo Emerson (1803–1882)