Author: Robert Hyatt
Date: 09:09:57 01/22/05
Go up one level in this thread
On January 21, 2005 at 16:56:15, Dann Corbit wrote: >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. > >That is a good point. The best known algorithms for chess are exponential. >That does not rule out even a linear solution (your best node always chosen as >first example). That is simply not possible. You might find the best move for white at every WTM position, because sometimes even the 10th best move would be good enough to win. But to _prove_ the win, you do have to search _every_ move for black at each BTM position. No way around this... This is a tree, there is no way to avoid searching the tree. Even if you reduce white's choices to 1 for the "proof" every other ply is exponential growth since you have to look at everything for black.... > >When asked, "How many moves do you see ahead?", >Capablanca replied: "One move - the best one." > >So we just need a program that does that. >;-) Nope. I can show you _many_ moves Capa made that were _bad_... :)
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.