Author: Robert Hyatt
Date: 19:05:51 05/04/01
Go up one level in this thread
On May 04, 2001 at 15:01:52, Jesper Antonsson wrote: >On May 03, 2001 at 22:04:35, Dann Corbit wrote: >>Neither of which help all that much. Chess is an exponential process. In >>general, such problems are called "intractable" -- in other words, you can't >>solve them. In fact, this is the case with chess. We can only approximate >>solutions, which is usually good enough. >[...] >>If someone can invent a polynomial time chess algorithm, then chess could be >>solved. But I doubt if that will ever happen because chess is not a problem in >>polynomial space. > >Well, I would say that in a formal computer science framework, you are wrong. >Chess is clearly finite, and thus in polynomial space. First, what makes it "finite"? the 50-move rule is not absolute and both players _can_ ignore it. Second, a tree search such as minimax is already known (and proven) to be NP. Since the tree size is represented as an exponential, N=W^D, where W is the number of branches at any node and D is the depth of the tree, it is clearly an exponential function where every additional iteration depth takes W times as long as the previous one did. > Of course, the number of >nodes in the search tree is exponential in the tree depth, but *only* if you >don't search deeply enough. (We will probably never be able to search deeply >enough either, but that is beside the point.) > >Jesper Antonsson If you make several assumptions, like 50-move rule is absolute, then the game is finite and exponential. However... the 50-move rule can be ignored if the players choose, which changes this a bit... And then there is the 'practical' point of view of course... even if it is effectively finite, as is the number of atoms in the universe, it is practically infinite...
This page took 0.05 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.