Author: Dann Corbit
Date: 12:41:01 07/08/02
Go up one level in this thread
On July 08, 2002 at 15:34:39, Jon Dart wrote:
>Your original post implied to me that you were asking about the benefits of
>recursive null pruning in general (vs. non-recursive pruning). I think it's
>pretty clear that this is a big win for many programs, although some still use
>no null pruning or a more restrictive version.
>
>If you're asking if R=2 is better than R=3 or R=2/3 (adaptive), I've tried
>adaptive null pruning from time to time (it's a compile-time switch in my
>program) and I always wind up going back to R=2 (recursive). Adaptive null
>pruning does a little worse on test suites, in my experience. But it seems that
>other programmers have had different experiences.
Here is the formula that Colin came up with, and which seems to work well for
Beowulf:
int NullOK(Board * B, int depth)
{
int cwp = 0,
cbp = 0,
base_reduction = (depth > IGNORE_ZUGZWANG) ? 0 : ONEPLY;
/* If there is a risk of Zugzwang then return 0 (no Null move) */
if (B->side == WHITE && B->WPts < AVOID_NULL_MAT)
return base_reduction;
if (B->side == BLACK && B->BPts < AVOID_NULL_MAT)
return base_reduction;
cwp = Count(B->WhitePieces);
if (B->side == WHITE && cwp < AVOID_NULL_PIECES)
return base_reduction;
cbp = Count(B->BlackPieces);
if (B->side == BLACK && cbp < AVOID_NULL_PIECES)
return base_reduction;
if (Skill <= 8)
return Skill;
/* The formula below is from Ernst A. Heinz's book "Scalable Search in
* Computer Chess" It comes from pages 35-37 and is described elsewhere
* in the book. This method is called 'Adaptive Null Move Pruning' with
* R(adapt) = 3(6)~2. In English, the NULL move depth reduction is equal
* to two ply by default. However, if either (a) both sides have fewer
* than 3 pieces and the current depth is 8 ply or more or (b) at least
* one side has greater than 2 pieces and the current depth is 6 ply or
* more then increase the depth reduction to 3 full ply.
NOT USED:
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
return TWOPLY + ((depth) > ((6*ONEPLY) + (((cwp < 3 && cbp < 3) ? TWOPLY :
0))) ? ONEPLY : 0);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
NOT USED
/* This is my own formula, offering scaleable search depth reduction
* between one and 2.5 ply depending on the depth to which you are
* searching */
return ONEPLY + (depth > (ONEPLY * ONEPLY) ? (ONEPLY) : (depth / ONEPLY)) +
((depth > ONEPLY) ? (HALFPLY) : (0));
}
Vincent's double null move idea also seems to be a clear win.
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.