Author: Robert Hyatt
Date: 21:14:10 05/06/01
Go up one level in this thread
On May 06, 2001 at 22:58:05, Uri Blass wrote: >On May 06, 2001 at 21:51:58, Robert Hyatt wrote: > >>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... > >It can be defined as polynomial when the only problem is that the constant is >very big. > I don't believe so. IE give me a polynomial that works for D=10, 11, 12, 13, ..., 500. The base formula for minimax is N=W^D. Let's forget alpha/beta to keep the math simple. So what I want is a polynomial expression that gives N for all D, assuming W is a constant. ><snipped> >>>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. > >The difference is that there is an upper bound for the number of effective plies >because of the 50 move rule and search at depth 100000 is going to give the same >result as search at depth 100001. Nope... technically the 50-move rule doesn't limit the game. The rules of chess don't demand that the game ends after 50 non-capture/non-pawnpush moves. > >There is no upper bound for the number of cities in the salesman problem. > >Uri Whether there is an upper bound or not has _nothing_ do do with NP completeness. NP has to do with the particular problem or its solution algorithm, and describes its behavior as the problem gets harder. Technically the game is infinite in length. Practically, if you enforce the 50 move rule, then it stops around 5000 plies or so. Either way it doesn't matter. I can do a polynomial solution to sort all the atoms in the universe by distance from some known point. I can do an NP solution to finding the shortest path to connect all those atoms starting at the same point. I am not going to accomplish _either_ however. Both are too hard. And will be too hard for millions of years if not forever.
This page took 0 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.