Author: Robert Hyatt
Date: 07:40:11 01/20/05
Go up one level in this thread
On January 20, 2005 at 10:20:09, Robert Hyatt wrote: >On January 20, 2005 at 06:43:18, Oreopoulos Kostas wrote: > >>Is there a proof the Chess ia actually an Hard NP problem? > > >yes, it is exponential, which is non-polynomial. Tree size = W ^ D. That puts >it out of any sort of polynomial representation instantly... wrote that poorly. It is an exponential problem, which is not solvable by any non-deterministic polynomial algorithm. It fits in the class of NP-complete problems that include the traveling salesman problem and any other problem that is exponential with respect to the size of the problem. If you are not familiar with the tern "NP" the basic idea is that if you have infinite parallelism could you spawn a huge number of parallel tasks, that would solve the stated problem, where each task would complete in a time that can be represented by a polynomial equation. Chess fails this because no matter how many tasks you use, the size of the problem given to each task is _still_ an exponential function. That does not say that a non-NPC solution does not exist for chess. For example, serious forward-pruning could conceivably produce a non-exponential tree growth done properly. In any case, it is as intractable a problem as you will find. Other such games are similar, including go, etc. Even checkers although checkers, like chess, is theoretically finite and we are getting very close to solving that game. There are those that will argue that the complexity of chess is O(1) simply because chess is finite. And once you search to the end of the game, further searches will take no longer (going deeper produces no new information and takes no more additional time since every branch stops when the game ends along that branch). But I'll leave that nonsense to those that want to take things too literally. :) I'll use the good old stand-by O(W^D) for the complexity of chess for today, tomorrow, and for as long as I personally will live... This is one of those discussions that do nothing more than waste time and bandwidth, with neither side able to convince the other of whether it is O(1) or exponential. :)
This page took 0.01 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.