Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Confusion on Null Move

Author: Eugene Nalimov

Date: 10:40:00 02/10/99

Go up one level in this thread


On February 10, 1999 at 13:02:44, Bruce Moreland wrote:

>
>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

Maybe my explanation was not very good :-(. I tried to say following:

Half of the nodes is alpha nodes, and in such nodes program has to
try *every* move. Most of those moves are bad, and positions after
such bad moves are bad, too ("not reasonable" in the terms of the
original post). That means that for the second player those
positions are good, and exactly here null-move pruning will work.

Eugene



This page took 0.02 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.