Author: Jesper Antonsson
Date: 18:13:15 05/05/01
Go up one level in this thread
On May 04, 2001 at 22:05:51, Robert Hyatt wrote: >On May 04, 2001 at 15:01:52, Jesper Antonsson wrote: >>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. The search space (the number of possible positions) is finite. Finding a best move can thus be done in finite time and space. >Second, a tree search such as minimax is already known (and proven) to be NP. So, Tic-Tac-Toe (which can also be solved with minimax) is NP? Hardly. >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. If Crafty finds mate, the next plies won't take long... >> 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... Que? Finite AND exponential? The search space is finite, so searching it is finite too. Thus the search only exhibits exponentiality until a certain depth is reached, as I said before. We don't *need* the 50-move rule for this, cutoffs of repetitions suffice. >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... Yeah, I've never disputed that. Jesper
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.