Author: Uri Blass
Date: 14:21:35 01/13/05
Go up one level in this thread
On January 13, 2005 at 16:26:53, Dann Corbit wrote: >On January 13, 2005 at 15:48:14, Uri Blass wrote: > >>On January 13, 2005 at 13:45:04, Dann Corbit 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. >>> >>>That is a very good point. >>> >>>However, we do not store the nodes simply in a tree but in a transposition >>>table, the same as we do today. So we do not have to search the nodes over and >>>over that we already searched. >> >>If this is the case then why cannot program solve KRB vs KR without tablebases >>even with 2^25 nodes(it is known that programs cannot see mate in 50 in relevant >>positions even with 1024*sqrt(). >> >>You can claim that the constant is very large but my guess is simply that there >>is no constant and all the assumption including the assumption of good order of >>moves collapse when you search deep and my guess is that one of the problems is >>that after many plies the order of moves is not good because there were good >>moves that did not cause cutoff only because they were not searched deep enough >>and now they cause a cutoff. > >Perfect move ordering is definitely a big problem in some positions. I do not >know how to achive it (and my tree solution demands it to achieve sqrt() nodes). > Perhaps there are some engines that will be able to at least approximate it >with enough chess knowledge. Perhaps in 20 or 40 years, the chess engines will >be much better at it. If move ordering is far from perfect, then you will >clearly need a lot more nodes. In fact, if we had truly perfect move ordering, >there is no need to do the search. We already chose the best move. So we can >only hope to approximate it. Maybe 99% is doable. I don't know. > >I suspect that in the case of the problem I describe, a proof search is really >what is wanted. And the evaluation function can be quite a bit simpler, >therefore. > >In any case, the solution to the problem that you describe cannot be more >difficult than the problem of creation of that tablebase, since we already have >an algorithm for that. > >In the actual case of trying to solve chess, it would clearly be valuable to use >any existing table base files to good advantage. > >Suppose (for instance) that we never get beyond the full set of 7 piece files >even in 40 years. > >Suppose (further) that some interesting parallel machine is able to search 40 >plies in one minute at that same date 40 years from now. > >It is possible that such a combination of hardware can reach the 7-piece >tablebase files from the root because of combinations that it can see after a >month long search. > >In that case, we may have solved the game of chess. My guess is that you will not get to the 7 piece tablebases in 40 plies from the opening position by logical lines. you need 25 captures to get there and 25 captures in 40 plies from the opening position do not happen in logical lines espacialy when the first 2 moves are quiet moves. 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.