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)
“It is well-known what a middleman is: he is a man who bamboozles one party and plunders the other.”
—Benjamin Disraeli (1804–1881)
“In the past, it seemed to make sense for a sportswriter on sabbatical from the playpen to attend the quadrennial hawgkilling when Presidential candidates are chosen, to observe and report upon politicians at play. After all, national conventions are games of a sort, and sports offers few spectacles richer in low comedy.”
—Walter Wellesley (Red)