Author: Dann Corbit
Date: 10:45:04 01/13/05
Go up one level in this thread
On January 12, 2005 at 20:55:42, Uri Blass wrote: >On January 12, 2005 at 20:33:25, Dann Corbit wrote: > >>On January 12, 2005 at 20:25:24, Uri Blass wrote: >> >>>On January 12, 2005 at 19:56:25, Dann Corbit wrote: >>> >>>>On January 12, 2005 at 19:37:29, Steve Maughan wrote: >>>> >>>>>Dann, >>>>> >>>>>>Things that seem impossible quickly become possible. >>>>> >>>>>I recon about 300 years before a computer will solve chess. This assumes >>>>> >>>>>1) 10^120 possible positions >>>> >>>>This is far, far too large. Chess positions have been encoded in 162 bits, >>>>which puts an absolute upper limit at 10^58 (and it is probably much less than >>>>that). >>>> >>>>>2) Alpha-beta cutting this down to 10^60 sensible positions >>>> >>>>The incorrect first assumption renders this and all following assumtions as >>>>moot. >>> >>>The second assumption is also not correct. >>> >>>By the same logic alphabeta can cut less than 2^30 positions in KRB vs KR to >>>2^15 positions but it does not happen and solving some KRB vs KR position with >>>no KRB vs KR tablebases is not something that you need 2^15 nodes for it. >> >>No. The second assumption would be true if the first was true. This was >>formally PROVEN by Donald Knuth. In a perfectly ordered alpha-beta solution >>tree, the number of nodes is proportional to the square root of the nodes in the >>full tree. > >The problem is that the number of nodes in the full tree is bigger than the >number of positions because the same position can happen in many branches of the >tree. > >Even with perfect order of moves you cannot solve KRB vs KR by alpha beta with >sqrt(2^30) nodes. That is a very good point. However, we do not store the nodes simply in a tree but in a transposition table, the same as we do today. So we do not have to search the nodes over and over that we already searched. I am not sure that it solves the problem completely, but it will solve most of it. The other point may also be very true. We do not know that it will be exactly the square root of the tree size, but it will be proportional to the square root of the tree size. What the constant of proportionality is, it is hard to know and probably is different for every tree in real life.
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.