Author: Dann Corbit
Date: 12:58:05 05/08/01
Go up one level in this thread
On May 07, 2001 at 17:03:05, Jesper Antonsson wrote: >On May 06, 2001 at 21:51:58, Robert Hyatt wrote: >>On May 06, 2001 at 18:22:06, Jesper Antonsson wrote: > >>>This is the first time I have heard someone call an *algorithm* NP. I think you >>>should study the definition again, you seem to use it interchangeably with >>>"exponential". >> >>No. I just use the NP class to hold all cases that can be proven to _not_ >>be in deterministic polynomial time. And trees can certainly be proven to >>not be in that class, from the simply formula for nodes searched using either >>minimax or alpha/beta... > >Bob, that is so wrong. You can't use NP classifications like that. > >>If something is exponential it _clearly_ can't be polynomial... and we use >>the *exact* same algorithm to do the salesman problem and the tree search >>problem... > >It doesn't matter whether the same algorithm is used. It's the *problem class* >(not the algorithm) that is NP or not, and the chess search space is finite and >therefore P. The algorithm you choose is irrelevant, by the way, I can show you >exponential algorithms for polynomial problems. Your arguments are flawed on >several levels. > >>>No, you are wrong. In chess, no matter the position, I can give an upper finite >>>time bound T on the search that will hold *regardless* of search depth. In the >>>traveling salesman problem, there is no such T, you can always add more cities >>>and force the search time above T. >> >>What reference do you cite to say that the above statement doesn't apply to >>chess? I can _always_ search another ply deeper. > >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. 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. 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. 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. Your arguments are absurd.
This page took 0.05 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.