Author: Ricardo Gibert
Date: 07:48:15 05/09/01
Go up one level in this thread
On May 08, 2001 at 19:07:26, Dann Corbit wrote: >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. But in chess, n is constant. Chess is O(1). If O(exp(n)) were correct, then there would not exist a constant c sth exp(n) = c*(1). Clearly such a constant exists, so you are mistaken. If the size of the chessboard were not limited to 8x8, then O(exp(n)) would make sense. > >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.