Author: Jesper Antonsson
Date: 15:22:06 05/06/01
Go up one level in this thread
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". 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.
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.