Author: Dann Corbit
Date: 14:58:27 01/13/05
Go up one level in this thread
On January 13, 2005 at 17:21:35, Uri Blass wrote: >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. Yes, but I said 40 plies in one minute and using a one month search. That would be (assuming BF of 2): 1440 minutes per day * 30 days = 43200 minutes. log2(43200) = 15.4 plies more or about 55 plies Maybe still not enough. In another 10 years you get ten more plies. And so on.
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.