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)
“Self-determination has to mean that the leader is your individual gut, and heart, and mind or we’re talking about power, again, and its rather well-known impurities. Who is really going to care whether you live or die and who is going to know the most intimate motivation for your laughter and your tears is the only person to be trusted to speak for you and to decide what you will or will not do.”
—June Jordan (b. 1939)
“In 1600 the specialization of games and pastimes did not extend beyond infancy; after the age of three or four it decreased and disappeared. From then on the child played the same games as the adult, either with other children or with adults. . . . Conversely, adults used to play games which today only children play.”
—Philippe Ariés (20th century)