Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Extend or not extend in a nullmove tree

Author: Don Dailey

Date: 13:33:26 06/10/98

Go up one level in this thread


On June 08, 1998 at 11:26:52, Robert Hyatt wrote:

>On June 08, 1998 at 03:03:37, Roland Pfister wrote:
>
>>Last week we discussed what to do and not do in a nullmove subtree.
>>My program Patzer used to not extend in such a branch. Bob argued
>>against it and it sounded ok to me.
>>
>>At the weekend I tried both versions and the result is that if Patzer
>>doesn't extend it is a little bit faster, but not much. But in some
>>positions it sees the solution one iteration later!
>>
>>So I changed my program to extend even in nullmove branches.
>>Thanks Bob.
>>
>>Roland
>
>Here's another "crazy one" to try.  In Cray Blitz, I very carefully
>chose
>where to try a null move (non-recursive, only allowing *one* in any one
>path).  I never tried it on a "PV" node for example, since such a node
>can
>not really have a null move played.  And to do so would mean that the
>null
>move search might fail high (as we hope) or it might return a score
>between
>alpha and beta, but we couldn't keep it.  So I simply disallowed it.
>
>I started off doing this in Crafty, but by accident, disabled the test,
>and
>the search ran faster overall.  That is I *always* try a null-move
>search,
>except for when the "null-move transposition table trick" says to not
>try
>one.  And surprisingly, it was/is faster.  If you aren't doing this, you
>should try it...  and let me know if it is faster or slower.  I was
>surprised,
>and it simplified the code a bit as well since I no longer have to worry
>about
>whether a node is "ALL", "CUT" or "PV" now... and that code is now
>gone...

Hi Bob,

I'm pretty interested in this stuff and have played around with
all kinds of variations.

Is my understanding correct that you are always trying a null move,
regardless of the static score?   For me it seems to work best to
have a static score very close (or above) beta.  The algorithm as
I once saw it in the ICCA journal used a half pawn margin.

Here are a couple of other ideas I would like feedback from you
and any others who have implemented null move if you are interested
in commenting.

I found it slightly faster to simply do a test search with a zero
width alpha/beta window around beta.  The idea being I only care
if we get a beta cutoff on the null move search.  I'm not using
the result of one of these searches to tighten the Alpha side of
the bound either.   With MTD this is a non issue but I found
it works find even with conventional alpha/beta.

I also tried using a "cheat margin" on the null move search to
coax a few more cutoffs from the search.  I reasoned that if the
static (stand pat) score was already above beta, I could relax
the null move search, since it normally overstates the case anyway.
An example is setting the zero width window to be (beta-8, beta-7)
and prunning if a get a fail hi.  The search must always return
the static evaluation score instead of the null move results which
is fine since I never do the search if the score is not already
above beta.

My findings on this is that it was stable (no strange effects as
long as all your lazy evaluation and margins was correctly implemented),
and was a LARGE speedup even with small margins.   The bad news
is that the speedup balanced out the benefit almost perfectly.  I
could not distinguish the difference in playing strength.

I've also experimented with the idea of not using recursion as you
seem to be doing.  This should guarantee (except in zugzwang) you
NEVER lose more than you null move depth in tactics you can see,
but testing never proved one was better than the other although the
recursive version was naturally faster.   Did you find a speed
difference?

Depth-3 selectivity does not work for me, although others report
great results.  I always get nice speedups but find the program
weakens just enough to measure.  Even when I'm very careful about
endgames and special case things.

My biggest improvement is to not use null move near leaf nodes of
the main search.  A "global" static attack test seems to be a very
nice improvement.  It must be tuned but not too strict.  It makes
the search much faster and it benefits from the speed.  I can
easily measure the improvement in testing.  It turns out that I
actually pick up a few things null move misses although visa-versa
is also true.  I can only do a couple levels of these, then null
move is superior for its ability to see longer range threats.

The basic idea of our static routine (much of it designed by Larry
Kaufman) is that we notice the highest valued piece attacked, and
then assume part of its value will be returned, so if a queen is
attacked, we assume only 2/3 of a queen is attacked.  This is a
major speedup and the assumption is very good for all the pieces.
There is a value that seems to be on the threshold of right and
wrong, and it can be found by noticing a sudden drop in problem
solution depth when you get too agressive (like 1/2 attacked value.)

I have long held that null move is not the right thing to do, and
yet I have no improvement to suggest and still use it myself.  For
the time being it seems the best at long term threats, but not
quite right for short term threats.

- Don




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