Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: When to do a null move search - an experiment

Author: Robert Hyatt

Date: 10:51:03 04/26/04

Go up one level in this thread


On April 26, 2004 at 11:50:18, Vincent Diepeveen wrote:

>On April 26, 2004 at 06:31:58, Tord Romstad wrote:
>
>I wonder how you came to your conclusion.
>
>I did more experiments and concluded that always nullmoving saves most time.
>Double nullmove is just performing slightly worse (less than a percent in search
>time) and not missing zugzwangs, so i use it for that reason.


This is one of those rare occasions where I agree with Vincent.

Several years ago Bruce Moreland and I were talking, about this very subject.  I
was explaining how I did it in Cray Blitz (and also in Crafty).  I classified a
node as "ALL", "CUT" or "PV" according to Marsland/Schaeffer terminology, and if
the node was classified as PV I avoided doing the null-search at all.

Bruce did some testing and doing this restriction actually slowed him down a
bit.  So we both set about testing this stuff extensively and we came to the
conclusion that null-move is best used _everywhere_ because we don't have
perfect ordering and node classification is not that accurate as a result.  The
only reason for avoiding a null is:

(1) you are in some sort of zugzwang position where a null-move will fail high
for the wrong reason and wreck the search.  Classic examples here are positions
with very few pieces.  IE pawns vs a knight where the knight can be zugged.
Most require some minimal amount of material on the board to avoid this problem.

(2) there is a tactical issue that is hidden with the R reduction.  IE the
classic position with white pawns at f2, g3 and h2, black queen at h3 and black
pawn or bishop at f3, threatening mate on the move.  If the R reduction prevents
you from seeing the mate, you can have problems.

(3) The hash table proves that the null-move search will not fail high, meaning
that the search will be wasted effort.

(4) Obvious positions such as when the side on move is in check.  Not moving
can't fail high here as the king is lost.

(5) I don't allow two consecutive nulls.  It is a potentially cute way of
eliminating zugzwang problems, but it is only good for that, and it is not free
in positions where no zugzwang is possible.  I choose to not deal with it
although I have this on my "to do" list to test with (say) pawn-only endings.

In short, try null everywhere.  But, as always, test, test, test.  Theory says
that doing null on a PV node is a waste.  Practice says that not all PV nodes
are really PV nodes after the search has started...  Go with practice. :)





>
>Your results give IMHO only the indication that your qsearch needs to be fixed
>and/or that you did your experiments at a too fast time control where tactics
>dominate.
>
>>Last week, there was an interesting discussion on this forum about which
>>criterions should be used to decide whether or not to do a null move search.
>>In an attempt to find out what works best for my engine, I played a self-play
>>tournament between four slightly different versions of my engine.  The
>>following pseudo-code explains the null-move criterions used by each of
>>the four versions:
>>
>>/* Gothmog A: */
>>int ok_to_do_nullmove() {
>>  if(in_check(SideToMove)) return 0;
>>  if(static_eval - value_of_biggest_hanging_piece(SideToMove) >= beta)
>>    return 1;
>>  return 0;
>>}
>>
>>/* Gothmog B: */
>>int ok_to_do_nullmove() {
>>  if(in_check(SideToMove)) return 0;
>>  if(static_eval - value_of_biggest_hanging_piece(SideToMove)
>>                 + value_of_biggest_hanging_piece(Opponent) >= beta)
>>    return 1;
>>  return 0;
>>}
>>
>>/* Gothmog C: */
>>int ok_to_do_nullmove() {
>>  if(in_check(SideToMove)) return 0;
>>  else return 1;
>>}
>>
>>Gothmog D is similar to Gothmog C, except that when the remaining depth
>>is 4 plies or more, a null move search with the depth reduced to zero
>>is done before the real null move search, and the real null move search
>>is avoided if the zero-depth search fails low.
>>
>>The criterion in Gothmog A is the one I have always used in the public
>>versions of Gothmog.  Our discussion last week seemed to indicate that
>>most others use the simpler criterion in Gothmog C.
>>
>>In my tournament, I all four versions face each other 50 times.  The
>>results:
>>
>>           Gothmog A   Gothmog B   Gothmog C   Gothmog D       Sum
>>Gothmog A    XXXX        26.5        31.0        29.5         87.0/150
>>Gothmog B    23.5        XXXX        30.5        26.0         80.0/150
>>Gothmog C    19.0        19.5        XXXX        31.5         70.0/150
>>Gothmog D    20.5        24.0        18.5        XXXX         63.0/150
>>
>>It is interesting that the version with the most restrictive criterion
>>achieves the highest score.  This confirms my growing suspicion that
>>recursive null move pruning doesn't work nearly as well as most people
>>believe, and that it might be a good idea to make an effort to reduce
>>its use as much as possible.  I will try to experiment with even more
>>restrictive criterions (perhaps static_eval-biggest_hanging >= beta+margin)
>>and see whether that improves the strength further.
>>
>>The number of games is of course still not sufficiently big to make any
>>definitive conclusions.  If I find the time, I will add more games and
>>more versions to the tournament.
>>
>>Tord



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