Author: Robert Hyatt
Date: 18:19:58 05/14/01
Go up one level in this thread
On May 14, 2001 at 21:10:52, J. Wesley Cleveland wrote: >On May 14, 2001 at 15:44:28, Dann Corbit wrote: > >>On May 14, 2001 at 14:51:16, J. Wesley Cleveland wrote: >>[snip] >>>I thought that is what we were discussing. If you have a hash table large enough >>>to store every position found in the search, then you do not need total path >>>information with each position, which means you could solve chess by considering >>>"only" about 10^25 positions. So, if Moore's law holds up, we could solve chess >>>by the end of the century, rather than by the end of the universe. >> >>Not a chance. Let's ignore the complication of things like the half-move clock >>for now. We shall also ignore the fact that you can ignore all the draw rules >>except for material count, and that it may be beneficial to do so at times. >> >>One of the fields of the hash position is depth. You will not know the answer >>to the true value of the position until the position has reached either >>won/loss/draw. Since chess has a depth of nearly 12000 plies, that implies a >>search so long and so deep that even if it were purely a binary choice you would >>never solve it. Just consider 2^10000 [about 2e3010] (which is absurdly >>smaller than the chess tree). Take the square root of that. Hmmmm. > >What you are ignoring, is that with alpha-beta, one side is always making its >best move which will eliminate (virtually) all of these extrodinarily deep >lines. You are overlooking the same thing. First, for the left-most branch at each node in the tree, alpha-beta eliminates _nothing_ whatsoever. Then for every ply where you search one move, the next ply you search 'em all... Alpha/beta is "depth-first". To solve the game you are going to start off searching incredibly deep before you establish any alpha/beta bounds that will help elsewhere.
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.