Author: Uri Blass
Date: 19:58:05 05/06/01
Go up one level in this thread
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. <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. There is no upper bound for the number of cities in the salesman problem. Uri
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.