Author: Dann Corbit
Date: 13:56:15 01/21/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. 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). 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. ;-)
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.