Author: Ricardo Gibert
Date: 23:08:12 05/06/01
Go up one level in this thread
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. > > > >> >>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.