Author: Robert Hyatt
Date: 20:10:20 05/05/01
Go up one level in this thread
On May 05, 2001 at 21:13:15, Jesper Antonsson wrote: >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. > Yes it is, in fact. If it has a tree shape, it is NP by definition. NP doesn't mean specific instance problems are not solvable... >>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. If you search with the rules of chess, the game can go something like 5500 plies deep. I claim 38^5500 is essentially infinite. :) The 5500 is an estimate I didn't compute, based on 49 non-pawn/non-captures, followed by one pawn move or capture, and start the process over. > >>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.04 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.