Author: Oreopoulos Kostas
Date: 03:06:51 01/21/05
Go up one level in this thread
Forgive me but i think that its another thing how big the problem space is and if there is a polynomial solution. The tree is certainly exponential, but is there a proof that finding a solution is about equal to visiting all nodes? [ like the traveling salesman problem ] It is certain that chess evaluation can cut the trees size down BUT that does not provide any clue on wether the problem is NP compete or not. If we had a perfect evaluation function that will pick the best move always, then we have of course an O(1) problem. Anything else keeps the problem in NP space, (an i wrong) but of course cuts down the time required for solving the problem.
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.