Author: Uri Blass
Date: 18:17:58 01/12/05
Go up one level in this thread
On January 12, 2005 at 20:58:47, chandler yergin wrote: >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. >> >>Uri >>Uri > > >I think you are on my side... >;) I disagree both with you and Dann. If you want to generate tablebases you cannot use sqrt like Dan suggest. If you want to analyze possibility in games then sqrt is enough. In case that there are 10^120 games and 10^40 positions then chess can be solved by sqrt(10^120) nodes or by 10^40 nodes (you may need to multiply it by a small constant like 1000 so it may be 10^43 nodes) but not by sqrt(10^40) nodes. I disagree both with you and Dann about solving the game. Dann claim possible in the life of part of the readers You claim impossible in the life of part of the readers. I claim unknown if possible or impossible in the life of part of the readers. I do not know if it will be possible to build the 32 piece tablebases in the next 100 years(you need something in the order of 10^40 both in memory and in speed). I do not know if it will be possible to solve chess by other means like finding that only 10^30 of the possible positions are relevant to build tablebases for them. Uri
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.