Author: GuyHaworth
Date: 09:45:59 12/11/02
Go up one level in this thread
H.J. van den Herik, J.W.H.M.Uiterwijk and J. van Rijswijck, in a paper:
"Games Solved: Now and in the Future"
give a table (Table 6) of the 'state-space complexity' and 'Game-tree
complexity' [i.e. the number of positions and number of games] of some 18 games
... in alpha-order:
Awari, Checkers, Chess, Chinese Chess, Connect-Four, Dakon-6,
Domineering (8x8), Draughts, Go (19x19), Go-Moku (15x15), Hex (11x11),
Kalah (6, 4), Nine Men's Morris, Othello, Pentominoes, Qubic, Renju (15x15),
Shogi
Some of these like Connect-Four, Dakon-6, Domineering (for many board-sizes),
Go-Moku (some variants), Hex (to 6x6 if not 6x7 boards), Kalah, Qubic and Renju
have been 'weakly-solved', i.e. given a 'theoretical game-value' for the initial
position.
The authors address the question of the 'intrinsic difficulty of the game', for
which the state-space and game-tree complexity numbers give a rough indication.
However, it has to be admitted that there is a game with arbitrarily large
state-space and game-tree figures which is not complex at all but trivial to
evaluate, namely, Nim.
The numbers following are the power of 10 for the 'state-space complexity' and
'game-tree complexity' of the games:
state, game
Awari 12 32
Checkers 21 31
Chess 46 123
Chinese Chess 48 150
Connect-Four 14 21
Dakon-6 15 33
Domineering (8x8) 15 27
Draughts 30 54
Go (19x19) 172 360
Go-Moku (15x15) 105 70
Hex (11x11) 57 98
Kalah (6, 4) 13 18
Nine Men's Morris 10 50
Othello 28 58
Pentominoes 12 18
Qubic 30 34
Renju (15x15) 105 70
Shogi 71 226
As the counter-example of Nim shows, these figures are not necessarily
correlated with the difficulty of solving the game or writing a program.
But the survey is perhaps the most comprehensive done cross game-domains so far:
Artificial Intelligence, v134 (2002) p. 277-311.
Reprinted in "Chips Challenging Champions", Elsevier (2002),
(eds. J. Schaeffer and J. van den Herik)
ISBN 0-444-50949-6
This page took 0.01 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.