Author: Dann Corbit
Date: 12:44:28 05/14/01
Go up one level in this thread
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. Having 10^50 positions in a hash table is useless unless you have analyzed them clear to the end. The end is so far away that it is laughable to consider that we might possibly get there. What we are talking about is analyzing the whole tree. Forget that it is chess positions and imagine (instead) that the nodes are integers. We won't know what branches to take in our tree until we have gone all the way to the end. It may be that some branches close off, but likely some will continue very, very deeply. One single branch that goes all the way to the end destroys any hope of ever getting there (at least by the conventional method of tree search, and assuming that we have at least two viable choices along the way). The hash table must contain all the positions, so sqrt(10^50) has no place until the calculations are complete. We can (perhaps) carry the other information separately (hmc, castle, etc) and so 10^50th may be adequate [assuming that this estimate is correct]. It may actually be smaller, as Uri Blass has produced some calculations that seem fairly convincing to me that it might actually be smaller. The true size of this table is obviously crucial because each one of the zeros makes it either ten times harder or ten time smaller. 10^40 is cleary 10000000000 times easier to store than 10^50th (sorry about the obvious nature of this statement, but some might wonder about what the heck I am talking about and I am beginning to doubt my communications skills). At any rate, I should be very glad to see a solution to the game tree in my lifetime and would hail it as an incredible achievement. However, I am loathe to imagine that any such improbable event should ever occur, as I consider it about the same probability that all the molecules in my office should suddenly decide to go straight up, leaving me in a hard vacuum, and causing my immediate explosion.
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.