Author: Dann Corbit
Date: 16:07:26 05/08/01
Go up one level in this thread
On May 08, 2001 at 18:45:16, Dan Andersson wrote: >I don't think every problem is computable in practice, the folding of >generalized (road)maps is not computable yet AFAIK. And yet, there they are right alongside the console of my car. That's because lots of algorthms that are not computable (or at least provably NP-hard) are *pragmatically* computable to within an acceptable tolerance. >But I'm interested in the >possibility that given the finite state space of chess there might be a provable >way of computing the value of chess with a less than exponential function of the >number of positions. 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. 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. 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: 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. >A kind of useless intellectual curiosity of no practical >use, yet. My only real objection in this tread was the Profs. statement that >chess was an infinite game, and then only based on the fact of the finite state >space. I think this is a place for compromise. We are talking "practically infinite" or perhaps "pragmatically" infinite. I mean, if the sun burns out before you can calculate an answer, then you aren't going to get there. O(n^5) is not computable for n = 1 trillion (right now anyway). But you could easily work out with pencil and paper that (1e12)^5 is only 1e60 operations. Not only finite and countable, but there is the number sitting right before us. Not infinite by any stretch of the imagination. In fact, there are at least 10^20th times more things than that in the observable universe (if you count elementary particles). With algorithms, when we discuss computable there is an element of pragmatism. If it takes too long to compute the answer, the answer has no value. If (for instance) a particular calculation took ten years to complete, we could find out faster by waiting! Just wait one year and the computer will solve it in 5 years. But if we wait another year, we will solve it in 2.5 years. So it will be done faster if we don't do anything just yet. With things like the internet, the notion of what is computable may have to be rethought. Considering the factoring of the RSA challenges, these sort of things were long considered strictly impossible. >A game of chess might continue forever in the volontary drawing rules are >not applied. There are true infinite games with unbounded state spaces, some >even solvable. As for the Proof Set search idea, I'm not sure I can construct >the proof sets in polynomial time. It's all to easy to hide operations by >mistake. With an exponential process, only tiny sets are computable. To manage 13 plies is a pretty good feat at tournament time controls on good hardware. At correspondence time controls we might make 17 plies in the early middlegame. But because of the exponential nature, solving really deep puzzles (read -- 'positional questions') is still way out of reach. Anyway, arguing about whether chess is infinite is probably a minor case of angels dancing on the heads of pins. It's finite all right, but it's infinte "for us." A funny thought about infinite time. If I had infinite time, I could walk over to Mount Rainier (a 14000 foot peak in Washington state) once every hundred years and rub the mountain with my thumb. Eventually, the mountain would be gone. But what I am wondering is would I finish that game first, or laying out all chess positions, at one per second. I am guessing that the mountain would be gone long before I got any serious progress with the chess solutions. ;-)
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.