Author: Bruce Moreland
Date: 10:02:44 02/10/99
Go up one level in this thread
On February 09, 1999 at 20:39:07, KarinsDad wrote: >On February 09, 1999 at 20:18:20, Eugene Nalimov wrote: >>Programs plays reasonable moves, but most of the positions >>in the game trees are not reasonable. For example, in half >>of the nodes, program must check *every* possible move, so >>null move will help greatly after majority of that moves. >> >>Eugene >> > >For someone who understand this well, your answer may be sufficient. But there >isn't enough detail for me to get the gist of the "why of it". Sorry. > >For example, if as you state that in half of the nodes, the program must check >every possible move, then it would seem that those nodes were acquired by one >side or the other making a reasonable move (as opposed to a move which was >easily refuted with a one or a few move search response). When the null move is >applied to all of the responses to the reasonable move (giving the responder two >consecutive moves), it would seem that the reasonable move would be blown out of >the water quite often by at least one of the responses and you haven't >accomplished anything. > >I would think that null move would be useful when you get a cutoff. If you can >refute my move and even if I make two moves in a row, you can still refute it, >then I have picked a really lousy move. But in this case, you already have a >cutoff, so why search deeper on it. I think I must be missing something here. There are three kinds of nodes, alpha nodes, beta nodes, and PV nodes. I'll explain each, given a perfectly ordered tree. The PV nodes are the left edge of the tree. You enter one of these, and you have to search each successor, and you'll get a value back that's between alpha and beta. The beta nodes are the siblings of PV nodes, and the children of alpha nodes. These nodes will all fail high. The alpha nodes are the children of beta nodes. These will all fail low. In a perfectly ordered tree, approximately half of the nodes are alpha nodes. These are nodes where every successor will fail low. Every move in these nodes is bad. You have to search all of them, because you can't cut off on a bad move, you can only cut off on a good one. Of course, when you return alpha after processing all of the successors, it gets negated, if the caller was a beta node it sees something that is >= beta from its point of view, and it immediately fails high. You won't have an alpha node that's a child of a PV node in a perfectly ordered tree, but if the tree isn't perfectly ordered you might get one, and it would change the PV line and its value. There is a discussion of this on page 14 of Carl Ebeling's "All the Right Moves", 1987, MIT Press, ISBN 0-262-05035-8. I believe it is also explained in Knuth, but I haven't looked. I think that Eugene's comments about these types of nodes and null-move forward-pruning don't sound right though. What you're trying to do with the null-move is identify beta nodes quickly. If you know for sure you are in an alpha node, you don't even need to do the null-move search, since it will fail low, which means that it was wasted. I've found that it's still useful to do it, because it doesn't cost much, and you mess up enough that the few times it works will still save you a lot of effort. But mainly you are allowed to cut off a beta node on a D-3 ply search rather than searching one successor to D-1 and cutting off after that. Of course this has the side-effect of reducing the number of alpha nodes as well, since the successor that you didn't search would have been an alpha node with an average of 35 successors of its own. bruce
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.