Author: Dieter Buerssner
Date: 16:01:12 12/12/02
Go up one level in this thread
On December 12, 2002 at 18:34:05, Dann Corbit wrote: Dann, I also have to contradict. I think, you now accepted, that not a whole tree of some size proportional to exp(depth) must be searched (or stored). Even for tree searching, it might be misleading. Humans have given provably correct mate problems with mate over 100. A tree searching program can prove it. One might ask, how this is possible? Well - the thing is very forced. Many side variations lead to fast mates. The whole search tree is not a tree at all - it is a graph. Variations of one side can sometimes be easily proven, that the other side can force the game to a transposition of another line (the alternative would be a fast mate). We have seen here, that normal chess programs can rather easily solve (=prove the mate, not necessarily the length of the mate) some mate in 15 problems. I have seen mate in 30. Proof number search can prove some very long mates. I have in few hours time proven (assuming the correctness of my code) mate in over 100 (no TBs involved). The current TBs can prove (depending on the rules, at least when we ignore 50 moves rule) very long mates in positions where the search tree is rather wide (say typically 20 moves or more). KQPKQ and KPPKP have mates in 127 (IIRC). Note that in KQPKQ, often both sides have many possible moves. KBBKN has very long mates. Still the number of positions to be searched is rather limited. For KBBKN around 462*62*61*60 "only". The longest mate is far longer than 100 half moves. One could ask - if there is an exponential effort of the size c1*sqrt(c2^(half_moves_to_mate)), what are reasonable c1 and c2? They would already here need to be extremely small ... All that said, I will not necessarily contradict the conclusion (chess is unsolvable for now). Regards, Dieter
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.