Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vincent Diepeveen

Date: 17:26:41 04/27/04

Go up one level in this thread


On April 27, 2004 at 03:33:26, Bas Hamstra wrote:

>About double nullmove: I tested this in some pawnendgames to see if it could
>handle zuzwang problems, but I don't see it perform any better than normal
>nullmove. Can Vincent or you post a position where double null outperforms
>normal null? I agree the idea is elegant, but I just don't see it work.
>
>Bas.

Never nullmove in pawn endgames of course. The reduction factor kills you there.
I posted that already a 1000 times here.

Any non-pawn endgame with a zugzwang double nullmove will find if you correctly
implemented it.

Most important feature of double nullmove is that you can use it detecting
zugzwang without problems and still using nullmove.

Many used to have rules like turning off nullmove when there is 1 piece left on
the board. Now you simply can use nullmove there and therefore search deeper in
the endgames before that.

Plenty examples of zugzwang positions have been posted already.

I'm not going to waste my time onto you, you just like agressive discussions.
F you there.

>
>
>
>On April 26, 2004 at 15:04:32, Robert Hyatt wrote:
>
>>On April 26, 2004 at 14:05:14, Vincent Diepeveen wrote:
>>
>>>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.
>>>
>>>Not allowing 2 consecutive nulls will for sure not find zugzwang problems.
>>>
>>>Not allowing 3 consecutive nulls will however find many zugzwang problems. As
>>>pointed out hashtable could do difficult, but that very seldom happens.
>>>
>>>Double nullmove does allow 2 consecutive nulls but not a 3d. So for a correct
>>>implementation you just need 1 'if then else' to also not allow null in a
>>>transposition table cutoff. This is very trivial to do.
>>
>>That is exactly what I was talking about.  More than 2 can't ever be good.  In
>>middlegame positions, I believe that 2 in a row introduces unnecessary overhead.
>> In endgame it might be worthwhile.
>>
>>
>>>
>>>>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. :)
>>>
>>>I'm using PVS in its pure implementation, so i start with window [-inf;inf]
>>>i also disallow nullmove when beta == inf.
>>>
>>>That's trivial stuff however.
>>>
>>>All other 'pv nodes' doing a nullmove is very good for different reasons. Even
>>>when it gets a nullmove. double nullmove has a bit of a IID effect.
>>>
>>>>>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.01 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.