Computer Chess Club Archives


Search

Terms

Messages

Subject: A better type of adaptive null move pruning

Author: Tord Romstad

Date: 00:48:51 11/29/03


I apologise for the provocative subject line.  With all those endless List
threads going on, I
have to do something drastic in order to get attention. :-)

I don't really have any idea whether the following idea will work at all for
other engines, but
so far it seems quite effective in Gothmog.

One of the well-known problems with null move pruning is that it sometimes hides
horizon
problems.  The classic case is when white has a pawn on f6 and a queen on h6
attacking
the undefended square g7 in front of the black king, it's black's move, and the
remaining
depth is less than R.  Unless the engine does checks in the qsearch, there is a
risk that
the null move will fail high even though there is no defence against mate.
Similar problems
may occur when the side to move has a pinned piece or when the other side has an
unstoppable passed pawn.

Checks in the qsearch helps to reduce this kind of problems, but they are still
there.  For
instance, in the above scenario with a mate on g7, it could happen that the
white queen
is not yet on h6, but that black cannot prevent it from reaching that square.

The point of classic adaptive nullmove pruning is to use a smaller value of R
when the
remaining depth is low.  My idea is to instead use the evaluation function as
well as the
remaining depth when deciding what value of R to use.  The idea will work only
for engines
which call the evaluation function at all interior nodes.

Here is what I do:

1. If the side to move is in check or has a big hanging piece, or if the side
not to move
threatens to give mate or promote a pawn, avoid the null move search.

2. If the side to move has an insecure king position or a pinned piece, if the
last move
of the opponent increased the pressure on the king, or if the opponent has at
least one
unblocked advanced pawn, there is a serious danger that the opponent has some
kind
of serious threat.  Choose R=1 or R=2 depending on how serious it looks.

3. In all "normal" positions, use R=3.

4. If the side to move has a clear advantage, no hanging, pinned or overloaded
pieces and
good king safety, and the opponent has no advanced passed pawns, it is probably
safe to
use an even bigger value of R.  I simply return the score of the static eval
(and hence do
static forward pruning) if the remaining depth is less than or equal to 5.  If
the remaining
depth is bigger than 5, I set R=max(remaining_depth/2, 4).

For me, this works better than all other schemes I have tried (plain R=3, plain
R=2,
classic adaptive null move pruning, and verified null move).

Tord



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