Author: Robert Hyatt
Date: 18:51:58 05/06/01
Go up one level in this thread
On May 06, 2001 at 18:22:06, Jesper Antonsson wrote: >On May 06, 2001 at 10:16:01, Robert Hyatt wrote: >>No.. but "minimax" is _definitely_ NP. A linear pattern-matcher (for >>tic-tac-toe) would not be and it is not hard to write... but minimax... > >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... 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... Walking the branches to the end. Comparing results on the way back. > >http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?nondeterministic+polynomial+time > >>>2. What is a larger instance of the "tic-tac-toe problem"? Before you claimed >>> that the exponentiality existed as a function of search depth. Increase the >>> search depth in the mini-max beyond nine in tic-tac-toe, and your search >>> won't take longer time. *It has an upper time bound.* There is a similar >>> limit in chess, it is just too large for us to ever attain. >> >> >>You are therefore saying that some chess positions are not NP? > >No, I'm saying that *no* chess position is NP. > >>That is not how NP works. NP is not about how long a solution takes.. it is >about how hard it is to go one level deeper (in the case of the tree). It >doesn't really matter if some positions have a mate in 2... it is >the "general case" that is interesting when you look at NP. > >And I repeat my question: What is the "general case" in chess? I'll answer it >myself, there is none, there is just the chess search space, which means that >the "problem" can't be expanded. That's why the search time is theoretically >bounded, no matter what position or depth you choose. > >>Otherwise the traveling salesman problem would not be NP, yet any textbook >shows and proves that it is. Even though for 4 cities it is easy to do and >there is a finite depth limit for the final solution. > >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.
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.