Author: Jesper Antonsson
Date: 14:03:05 05/07/01
Go up one level in this thread
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.
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.