Computer Chess Club Archives




Subject: Re: Verified Null-moving

Author: Peter Fendrich

Date: 07:16:33 08/12/04

Go up one level in this thread

On August 12, 2004 at 09:28:24, Tord Romstad wrote:

>On August 12, 2004 at 08:42:28, martin fierz wrote:
>>>hi tord,
>>>i'm intrigued by your last sentence - that null move at all nodes more than
>>>doubles your node count! i wonder how this is possible at all? why? if i
>>>understand what you write you have an oracle which can tell you whether you
>>>should do a null-move search at a given node or not.
>>>int alphabeta(....)
>>grrr, hitting tab-return is not such a good idea :-)
>Happens to me too, sometimes.  :-)
>>let me continue: you have
>>int alphabeta(...)
>>  {
>>  ...
>>  if(null_oracle(position) == NULL_OK)
>>    do_nullmove_search()
>>  ...
>>  }
>Almost, but there is one important part missing above:  I return a
>fail high score *before* doing the null move search when I am very
>sure of a fail high.  It's more like this:
>int alphabeta(...)
>  if(almost_certainly_fail_high(position, beta))
>    return beta;
>  else if(probably_fail_high(position, beta))
>    do_nullmove_search()
>  ...

Mine is more like this:
  if (known_fail_high(position, beta)  //from hash, quick_endgame_recogn etc
     return beta;
  else if (! probably_fail_low(postition, alpha)

I can't find out how to get almost_certainly_fail_high in my engine that doesn't
evaluate interior nodes. There are a few endgame cases that I handle as
known_fail_high even if they are (very) probably_fail_high.

>>if you remove that null_oracle thing you get twice as many nodes?
>If I remove the almost_certainly_fail_high() and probably_fail_high()
>functions (I don't have functions with these two exact names, but you get
>the idea), I search twice as many nodes.
>>i don't
>>understand how that can happen. your null_oracle would basically be telling you
>>not to do a null move search if it thinks it will fail low anyway. so for all
>>nodes where you don't have to do a null move search with R=3 you have to do a
>>normal search. you save yourself searching the R=3 part, but that should be very
>>small compared to the normal search part, shouldn't it?
>>what am i missing?
>That recursive null move pruning is not the only kind of pruning I do.
>At fail low nodes, most of the moves are not searched with full depth.
>When the first 3 moves have failed low, I search all remaining moves with
>reduced depth except when they look especially interesting or forcing.
>If a move searched with reduced depth surprisingly turns out to fail high,
>it is re-searched with full depth.

Also here I do something similar but 3 is not a constant. It varies due to how
many hash-move + killer-moves + good captures etc I have.
I have also tested to vary the depth-reduction due to if move[ply-2] and
move[ply-4] etc are all in this category (probably_fail_lows). Reduce depth less
in the beginning and reduce it more if still in a path with only
probably_fail_lows. However it didn't give any improvements at all. Probably
because I mix this with extensions as well and can't sort out in my mind how all
this interact together...

>For some reason, most of the published research on selective search
>mechanisms has concentrated on ways to reduce the work at fail-high
>nodes.  Nullmove pruning, Multicut pruning and ProbCut are a few examples.
>Pruning techniques for fail-low nodes are much less commonly seen.  The only
>ones I can think of is futility pruning and razoring, but these are too
>dangerous to use except when the remaining depth is very small.
>Reducing the search depth towards the end of the move list is my own
>attempt to do selective search at expected fail-low nodes.  It is
>probably possible to invent better techniques (and it wouldn't surprise
>me if it has already been done in some of the professional engines), but
>at least in my engine, what I do works far better than nothing.

Once again, with evaluation at all nodes you have a better foundation for doing
move ordering and prune according to that compared to me that take big risks by
just relying on statistical observations in the search tree!



This page took 0.23 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.