Author: Uri Blass
Date: 19:07:58 01/12/05
Go up one level in this thread
On January 12, 2005 at 21:33:06, chandler yergin wrote: >On January 12, 2005 at 21:17:58, Uri Blass wrote: > >>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 > > >A NODE, IS a Position! Correct? Node is a position that is searched by the chess engine. > >If there are 10^120 Games.. then 'every move' in those 10^120 games ARE >Positions. Yes but not all of them are different so it is possible that there are only 10^40 different positions in a tree of 10^120 positions. There are too way to try to solve chess 1)search(in this case you may search the same node in a lot of branches and you search both 1.e4 e6 2.d4 d6 or 1.e4 d6 2.e4 e6 or 1.d4 e6 2.e4 d6 or 1.d4 d6 2.e4 e6) In 4 plies you can get the same position 4 times and in 80 plies that are 40 moves you may get it trillions of times in different branches of the tree. In tree alpha beta help to get sqrt of the number of games but it is not a good idea to solve chess. 2)tablebases that seems a better idea and the problem is that today there is not enough memory. In this case you do not build a tree. you look at all the position first time and mark all the mates. you look at all the position second time and mark all positions that you can get mate in 1(position that is already marked) you look at all the position and mark all the positions that you cannot prevent mate in 1(every move will need to position that is marked as mate in 1) There is no mate in 5000 because of the 50 move rule. so after repeating this process 10,000 times you can continue stop it and every position was searched only 10,000 times. This means that if the number of positions is 10^40 then time of searching 10^40*10,000 positions is going to be enough but you need also memory of 10^40 positions and this is the another problem with using this solution today. I do not know if we will be able to use memory of 10^40 positions or search 10^44 nodes in the next 100 years but I cannot say that I am sure that it is impossible. 10^40 positions is only an estimate and I do not know the exact number of positions. I remember that I proved that it is less than 10^50 and even less than 10^47 in the past by a computer program that counted the number of possible positions for every possible material configuration and part of the positions that I counted are also illegal because both kings are in check so the estimate of 10^40 seems to me a good estimate. Uri
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.