Author: chandler yergin
Date: 21:50:00 01/12/05
Go up one level in this thread
On January 12, 2005 at 22:07:58, Uri Blass wrote: >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 Argue with Dr. Hyatt, Dr. John Nunn & Frederick Freidel! THEY agree with ME!
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.