Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 16:40:53 06/10/98

Go up one level in this thread


On June 10, 1998 at 16:33:26, Don Dailey wrote:

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

I try it everywhere...  and I use the normal alpha/beta bound, but
reduce
the depth by 2 plies above the normal 1 ply you would use.



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

99.9999% of my searches are with alpha,alpha+1 anyway, so there is no
narrower window I can use, since I am using classic PVS already...  and
I can't tighten alpha as a result...



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

recursive is faster... and doesn't seem to hurt more than it helps...
Null move misses some things, which is why CB is still tactically
stronger
than Crafty, giving it a huge hardware advantage to work, because CB
uses
R=1 non-recursive, so it has few null-move failures.  But Crafty can go
deeper overall, so this might well balance out and be better as it is
now
being done...  so far I like it...



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

Bruce and I played some games last year with ferret using r=2 and then
r=3
and we could tell no difference strength-wise...



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

yes, although I found that as I refined things in Crafty, to get to the
speed level where I am now, the null-move related losses generally have
disappeared...  at 4-5 plies, they will kill you.. but I generally do
7-9 in blitz, and simply don't get burned by this, at least to the point
where I notice it..



>
>- Don



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