Author: Bruce Cleaver
Date: 09:58:02 12/11/02
Go up one level in this thread
On December 11, 2002 at 12:45:59, GuyHaworth wrote: >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 Thanks for posting this - I have seen estimates of some games in some places, but not conveniently gathered together. Go is very hard not only for its large state space, but because material differences appear to be unimportant (unlike chess where being a piece up USUALLY means you win). Connect-4 has been solved completely by Victor Allis in his PhD dissertation. First player wins.
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.