Author: Jesper Antonsson
Date: 15:05:08 05/08/01
Go up one level in this thread
On May 08, 2001 at 15:58:05, Dann Corbit wrote: >On May 07, 2001 at 17:03:05, Jesper Antonsson wrote: >>I can use you as a reference. I remember you in RGCC discussing upper limits on >>the number of distinct positions in chess and as far as I can remember you >>agreed there was such a limit. Thus the search space is finite and you can store >>partial results as you search, and when you have searched all nodes once, you >>are done. "Another ply deeper" will be almost instantaneous, just as when you >>find a mate in an easy position and then pull results from hash. NOTE: The >>practicality of the above approach, or the number of atoms in the universe, is >>totally irrelevant. >All inputs into any computer program must be finite. Otherwise, the program >cannot ever terminate or even stop reading the input. Yes, and that is irrelevant. I haven't mentioned anything about infinite inputs, by the way. >O(f(N)) means that the time spent by the algorithm will always lie below some >constant times the function f() if N is large enough. Yes, and for chess we can choose a constant that suffices for all N if f(N)=1. In other words, when the depth is large enough, the search stops exhibiting exponential properties and another ply won't take any more time than the current ply, just as when you find mate. Is this so damned hard to understand? >Chess is exponential (with all current algorithms). To argue otherwise is just >plain silly. Similarly for other NP-hard problems or problems of any nature. It's you who don't know your theory. >Consider sorting. We are not going to insert an infinite set into our sorting >algorithm. Even if we could magically sort in O(N) it will never terminate. >So >we are *ALWAYS* talking about finite inputs. The type of function determines >how large a value of N is feasible. Will you solve a chess tree of depth 5000? >No. Not now. Probably not ever. As in never-ever. Correct, and irrelevant. >Your arguments are absurd. *sigh* I will never solve chess. Humanity will probably never solve chess either. A practical, live, chess search from the initial position will exhibit exponential behaviour. Any real input to an algorithm will be finite. And all that is all totally irrelevant. The point is that the chess search space is theoretically finite, and therefore, at a large depth, the search will stop it's exponential behaviour. That this depth cannot be attained in *practise* has nothing to do with chess' NP-ness, because that is a theoretical property for which such practical considerations is irrelevant. If you want to misuse well defined theory, I can't stop you, but this is getting ridiculous.
This page took 0.04 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.