Author: Dieter Buerssner
Date: 04:19:18 01/02/03
Go up one level in this thread
On January 02, 2003 at 06:03:58, Edward Seid wrote: >Definitions: [...] >game-tree complexity - number of leaf nodes in the solution search tree of the >initial position of the game I am not sure, I understand the definition. It seems not related to the effort needed to solve the game. > State-space Game-tree > Complexity Complexity > ----------- ---------- [...] >13. Nine Men's Morris 10^10 10^50 10^50 is something very big. Even square root of it (assuming one needs to visit only this many nodes in an alpha-beta search) is very big. Assuming 10 years calculation time, one would need to visit 10^25/(10*365*3600) nodes/s = 3.2*10^16 nodes/s But Nine Men's Morris is solved (from what I read here and at other places). I think, it is also understandable, that this can be solved with effort. It has only 24 sqaures. Each square can have at most 3 states (black, white, empty). So, for the moving phase of the game, it is clear that a table base of at most 2*3^24 positions is more than enough. (factor 2 because of side to move). This does not even take into account the symmetries, neither many illegal positions. The "setting phase" has exactly 18 plies. An 18 ply search should be possible. Regards, Dieter
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.