User talk:Falcon9x5.com
| Game | Board size
(cells) |
State-space complexity
(as log to base 10) |
Game-tree complexity
(as log to base 10) |
Average game length
(plies) |
Complexity class of suitable generalized game |
|---|---|---|---|---|---|
| Tic-tac-toe | 9 | 3 | 5 | 9 | PSPACE-complete |
| Connect Four | 42 | 14 | 21 | 36 | ?, but in PSPACE |
| English draughts (8x8) | 32 | 20 or 18 | 31 | 70 | EXPTIME-complete |
| International draughts (10x10) | 50 | 30? | 54 | 90 | EXPTIME-complete |
| Reversi | 64 | 28 | 58 | 58 | PSPACE-complete |
| Hex (11x11) | 121 | 56 | ? | 40 | PSPACE-complete |
| Chess | 64 | 50 | 123 | 80 | EXPTIME-complete |
| Backgammon | 28 | 20 | 144 | 50-60 | Generalization is unclear |
| Amazons (10x10) | 100 | 40 (upper bound) | ? | ? | PSPACE-complete |
| Shogi | 81 | 71 | 226 | 110? | EXPTIME-complete |
| Go (19x19) | 361 | 171 | 360 | 150 | EXPTIME-complete |