Author: Robert Hyatt
Date: 11:51:22 05/07/01
Go up one level in this thread
On May 07, 2001 at 02:08:12, Ricardo Gibert wrote: >On May 07, 2001 at 00:14:10, Robert Hyatt wrote: > >>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. > > >But this point is irrelevant as far as solving chess is concerned. Neither does the "infinite number of cities" issue in the traveling salesman problem. Yet it is still NP. > > >> >> >> >>> >>>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.