Author: Edward Seid
Date: 03:03:58 01/02/03
Definitions:
state-space complexity - the number of legal game positions reachable from the
initial position of the game
game-tree complexity - number of leaf nodes in the solution search tree of the
initial position of the game
State-space Game-tree
Complexity Complexity
----------- ----------
1. Awari 10^12 10^32
2. Checkers 10^21 10^31
3. Chess 10^46 10^123
4. Chinese Chess 10^48 10^150
5. Connect-Four 10^14 10^21
6. Dakon-6 10^15 10^33
7. Domineering (8x8) 10^15 10^27
8. Draughts 10^30 10^54
9. Go (19x19) 10^172 10^360
10. Go-Moku (15x15) 10^105 10^70
11. Hex (11x11) 10^57 10^98
12. Kalah (6,4) 10^13 10^18
13. Nine Men's Morris 10^10 10^50
14. Othello 10^28 10^58
15. Pentominoes 10^12 10^18
16. Qubic 10^30 10^34
17. Renju (15x15) 10^105 10^70
18. Shogi 10^71 10^226
Source: H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, Games
solved: Now and in the future, Artificial Intelligence 134 (2002) 277-311.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.