Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vasik Rajlich

Date: 03:07:06 04/27/04

Go up one level in this thread


On April 26, 2004 at 13:51:03, Robert Hyatt wrote:

>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. :)
>

Jose's explanation from the other thread makes the most sense to me.

The more selective the engine, the more selective it can be with null move.

An engine whose only selectivity at depth > [small number] is null move had
better not be missing too many chances to do a null move.

Also, Tord's experiment involved an extremely low nodes per position counts.
Null move gains strength with more depth.

Vas

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