Author: Robert Hyatt
Date: 09:07:28 01/22/05
Go up one level in this thread
On January 21, 2005 at 06:06:51, Oreopoulos Kostas wrote: >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. The tree is exponential. To _prove_ that you have a solution you have to traverse all the branches, just like the TSP. There might be a good solution to playing the game without exhaustive search, but it will not _prove_ that the resulting solution is correct. So you get to search the entire tree, less those positions / branches that alpha/beta proves are irrelevant to the search result, or else you don't have a "proof" that your suggested winning move wins for _all_ cases... If the three is a win for white, then you have to search _all_ black moves at every point in the tree. You don't have to search all white moves since if you find any combination of white moves where black can't avoid losing no matter what is played, your proof is done. That is essentially what alpha/beta does.
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.