Author: Dann Corbit
Date: 17:33:25 01/12/05
Go up one level in this thread
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. If there were 10^120 in the full tree, then about 10^60 would be in the solution tree. It can be less than that. But it cannot be more.
This page took 0.04 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.