Author: Dann Corbit
Date: 17:22:56 12/12/02
Go up one level in this thread
On December 12, 2002 at 19:01:12, Dieter Buerssner wrote: >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). My claim has never been that. Rather, that some size proportional to sqrt(exp(depth)) must be stored for perfect move ordering, when optimal. >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). Forced lines can and do happen (probably more often for stalemate than for checkmate). It is also possible that there are 100 legal moves from a given position and all of them are about the same and must be searched nearly full width. I do realize that there is no proof of my earlier conjecture. In fact, I am equally sure now that it *cannot* be proven (except by demonstration) one way or the other. The question (originally) was "Can we solve the game of chess." The answer is "Yes, but it will take a very long time." The debate is over whether 'a very long time' is probably exponential with both a base and exponent so large that the problem is intractible. I think it will have to be an open question. The more I thought about Uri's "Mate in 15" statement, the more I realized he was right. It is very unlikely, but possible that the entire game can be closed off to a single branch that is not very deep.
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.