Author: Michael Yee
Date: 18:03:54 01/12/05
Go up one level in this thread
On January 12, 2005 at 20:57:40, chandler yergin 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. >> >>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. > >It "Can't be LESS than that! > > But it cannot be more. > > >It Certainly CAN! > >In any TREE.. the TREE ONLY represents "What HAS Been PLayed." >REFUTE THAT! >Can't HUH? > >Give it up! What you just said is correct since you're talking about the *tree* of moves. But Uri and Dann are talking about the *set* of unique positions (many of which can arise through different move orders). So you and they are talking about different (mathematical) objects--trees (or paths in a tree) and graphs (or nodes in a graph). By the way, just because some quantity is large (or infinite) doesn't mean you can't prove something about it mathematically. For instance, you can prove that a geometric series (e.g., 1/2 + 1/4 + 1/8 + ...) convergences to a number even though their are an infinite number of terms. Michael
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.