Author: Dan Andersson
Date: 16:35:28 05/08/01
Go up one level in this thread
>If you are right, your program will absolutely blow others out of the water. I >hope you are right also. Of course, the discovery of such an algorithm will >*still* mean that chess is O(exp(n)), for those that know what the term means. >-- wink, wink. There is no way in hell I can think of to get such behaviour from my programs search, but there are some theoretically correct pruning methods hidden in there. No, I won't tell. > >Be that as it may, I think it may stay exponential -- just thinking about the >problem set. As long as we have any sort of probability of two possible good >choices at multiple points in the path, I am sure you can visualize the >exponential nature. The beauty of the proof set and proof number search is that there is always one most proving node. The problem is generating the tree, generating a possibly new most proving node, if all positions are already available there might be some way to avoid a combinatorial explosion. > >Having said that, did you look at the knight's tour stuff I posted a little >while back? An incredibly clever algorithm that is *thousands* of times faster >than any I have ever seen before. Consider: Truly beautiful :) > >Solved 1.00e+005 (100000) 0.7 seconds >--------------------------------- >| 1| 30| 43| 40| 3| 62| 21| 24| >| 44| 41| 2| 63| 22| 25| 4| 61| >| 31| 64| 29| 42| 39| 20| 23| 10| >| 50| 45| 32| 37| 26| 11| 60| 5| >| 33| 28| 51| 46| 19| 38| 9| 12| >| 52| 49| 54| 27| 36| 15| 6| 59| >| 55| 34| 47| 18| 57| 8| 13| 16| >| 48| 53| 56| 35| 14| 17| 58| 7| >--------------------------------- > >... > >--------------------------------- >| 1| 26| 23| 38| 3| 34| 21| 40| >| 24| 49| 2| 33| 22| 39| 4| 35| >| 27| 64| 25| 48| 37| 20| 41| 10| >| 60| 47| 50| 63| 32| 11| 36| 5| >| 51| 28| 61| 46| 19| 42| 9| 12| >| 56| 59| 54| 31| 62| 15| 6| 43| >| 29| 52| 57| 18| 45| 8| 13| 16| >| 58| 55| 30| 53| 14| 17| 44| 7| >--------------------------------- >Solved 2.20e+006 (2200000) 16.2 seconds >--------------------------------- >| 1| 34| 23| 46| 3| 44| 21| 40| >| 24| 47| 2| 35| 22| 41| 4| 43| >| 33| 64| 49| 26| 45| 20| 39| 10| >| 48| 25| 36| 59| 38| 11| 42| 5| >| 63| 32| 27| 50| 19| 58| 9| 12| >| 28| 53| 30| 37| 60| 15| 6| 57| >| 31| 62| 51| 18| 55| 8| 13| 16| >| 52| 29| 54| 61| 14| 17| 56| 7| >--------------------------------- >Solved 2.30e+006 (2300000) 16.9 seconds >--------------------------------- >| 1| 30| 23| 38| 3| 48| 21| 40| >| 24| 27| 2| 49| 22| 39| 4| 47| >| 31| 64| 29| 26| 37| 20| 41| 10| >| 28| 25| 58| 63| 50| 11| 46| 5| >| 59| 32| 51| 36| 19| 42| 9| 12| >| 52| 35| 54| 57| 62| 15| 6| 45| >| 55| 60| 33| 18| 43| 8| 13| 16| >| 34| 53| 56| 61| 14| 17| 44| 7| >--------------------------------- > >That's right, in 17 seconds it solved 2.3 MILLION knight's tours. Can a similar >edge detection scheme be applied to regular chess? I have no idea, but there is >no reason that a clever person cannot come up with a revolution. Regards Dan Andersson
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.