Computer Chess Club Archives


Search

Terms

Messages

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

Author: Don Dailey

Date: 15:18:14 06/11/98

Go up one level in this thread


On June 11, 1998 at 08:04:04, Ernst A. Heinz wrote:

>On June 10, 1998 at 16:33:26, Don Dailey wrote:
>
>>Is my understanding correct that you are always trying a null move,
>>regardless of the static score?
>
>Yes, I suspect many/most people do it this way -- "DarkThought" incl.
>
>>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.
>
>Up to which depth to you use the static scores for deciding about
>null-move trials?

All depths where I do null move.  Is there an improvement here?
I will experiment more with this since others seem to find it
more workable.

>>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.
>
>Again I think many/most people only do the zero-window test ...


No surprise, since it seems faster.



>>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.
>
>Yep, same for "DarkThought".

Independant verification!   Bob and Bruce do not notice it, but
each program is different.


>>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 must admit that I do not quite understand how you actually prune.
>Could you please elaborate on this?
>
>=Ernst=


Ok, here is more detail.  I do several plies of null move selectivity,
and 2 plys of static selectivity.  Here is how the static selectivity
works:

If the current STATIC score (same as stand pat in quies) is less than
BETA, then I go full width.

Otherwise, I execute a static analysis of the board looking to see
what is attacked for the side who just moved (similar to null move
but static.)   The analysis is not terribly sophisticated, it does
not need to be since you can take conservative assumptions.  Refining
them even more runs into a serious point of diminishing returns so
it doesn't seem to be worthwhile.    Here is how the attack testing
works.

Start with highest valued piece and work your way down to lowest
valued piece.  So for each piece:

  If 2/3 of the pieces value is not enough to prevent a beta cutoff,
  then quit, and BE SELECTIVE.

  Otherwise, Is piece up-attacked?  If yes, then  go FULL WIDTH.

  Is piece down attacked but defended by a pawn?  If so, then no
  problem, move on to next attacked piece.

  If piece is attacked at all, then count attackers and defenders,
  if it's defended more than or equal to the number of times it's
  attacked then everything is cool, move on to next attacked piece.

  If there are no attacked pieces, then take the static score as
  your beta cutoff.


I'm not positive I got every single detail correct.  But the idea
is simply to notice what is attacked and statically make a decision
about whether the threat is serious or not.   If any piece is
seriously attacked we still assume (since it's the attacked guy's
turn to move) that we will get 1/3 of the loss back.   All these
assumptions and our static analysis is subject to error, but it
turns out it is quite reliable overall and buy's a lot more speed
than normal null move close to leaf nodes.

Since null move is simple I've tried to take the static stuff out
of the program, but each time I get a noticable strength loss.
I would actually prefer to keep pure null move for its simplicity.
I will always do what seems to work best like most of us.

There are a couple other refinements I should mention.  We do some
simple static mate threat stuff and also consider pawns on the 7th
as big threats.   My old program REX used 4 ply of this kind of
selectivity and also looked at other advanced pawns.  Once you are
more than 2 or 3 ply from quies, it becomes difficult to pick up
deep threats.

The current program reverts to static selectivity in pure king and
pawn endgames.  This routine is cool.  I can do several ply of this
because I essentially count the distance of the king to each enemy
pawn.  For instance if the white king is 4 squares away from ANY
black pawn, there can be no threat (except positional which we also
take into consideration) for 7 or 8 ply.  Of course we
also count distance from queening and other considerations but you
can make nice assumptions with a little thought.  Null move loses
many ply in some of these endings but this static stuff is actually
faster while losing less depth on problem solution.

My thinking (as I already mentioned) is that this kind of stuff
might make a better program than null move.  Null move is nothing
more than estimating a lower bound on the score.  How you do it
is irrelevant, it's HOW WELL you do it.

- Don




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.