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 well-known old remark of Cato, who used to wonder how two soothsayers could look one another in the face without laughing.”
—Marcus Tullius Cicero (106–43 B.C.)
“The rules of drinking games are taken more serious than the rules of war.”
—Chinese proverb.