Author: Ernst A. Heinz
Date: 08:31:24 06/13/98
Go up one level in this thread
On June 13, 1998 at 10:29:49, Robert Hyatt wrote:
>On June 13, 1998 at 05:55:44, Vincent Diepeveen wrote:
>
>>
>>On June 12, 1998 at 12:38:12, Don Dailey wrote:
>>
>>>On June 12, 1998 at 03:49:36, Vincent Diepeveen wrote:
>>>
>>>>Hello,
>>>>
>>>>Some time ago someone mentionned Deep Search extensions.
>>>>I looked in archives but could not find anything about it.
>>>>
>>>>What exactly are deep search extensions,
>>>>is it extending after the n-th extension more and more?
>>>>
>>>>Greetings,
>>>>Vincent
>>>
>>>Hi Vincent,
>>>
>>>Deep search extensions are a by-product of the null move search.
>>>Essentially they are extensions given when the program fails a
>>>null move search. The assumption (when this happens) is that
>>>something interesting must be going on (it's usually just some
>>>direct attack of something) and warrants an extension.
>>>
>>>The typical implementation is to only grant this on 1 or 2 levels
>>>near the leaf nodes of the main search.
>>
>>Doesn't this mean we extend everything, because we get again
>>leafs after we extend?
>>
>>Are there extra conditions like score of position static evaluated
>>eval >= alfa, or does the definition leave that free?
>>
>>So
>> if( nullmovefail && eval >= alfa )
>> then extend a ply.
>>
>>>- Don
>
>this isn't exactly how it works. Here's what happens: if you use PVS,
>you have a more difficult problem, if you don't use PVS (or other nega-
>scout like algorithms) it is easier. You don't just extend if the null
>move search fails low, you extend if it fails low by a significant
>margin. In my case, when I did this a couple of years ago, I had to do
>a second null-move search, with the window lowered by 1/2 pawn. The
>idea
>is this... you find what appears to be a good move (one that fails
>high,
>or one that just became part of the PV) but before you accept the score,
>you do the null-move test. If the offset null-move fails low, that
>means
>that doing nothing gets you killed, which might mean that the current
>move
>is a move that just barely holds off this threat. And you extend. It
>can
>find some things pretty well, it fails on others, and the cost is non-
>trivial. If you are going to try that, you might as well try full
>singular
>extensions, as this is just a very weak subset of that...
Bob,
I am sorry to say that what you describe are *not* the deep-search
extensions as suggested by Donninger in his 1993 article "Null move
and deep search" (ICCA Journal, Sep. '93, pp. 137-143). The costs of
your second null-move search should be surely prohibitive.
You actually do the extension if at a node near the search horizon
your static evaluation score is >= beta but the null-move score drops
below your static score by a sizeable margin (e.g. value of a knight).
Thence, the null-move score signals a severe dynamic threat in a
position that looks very good statically.
Although I have already answered the questions before it seems that the
"deep-search topic" pops up again and again after half a year or so and
nobody remembers exactly what it is ... :-(
Vincent, why have you still not bought the ICCA Journal back issues?
Then you could read Donninger's article yourself.
Anyway, below I copy the pseudo-code 1:1 from the article for all
interested readers:
//////////////////////////////////////////////////////////////////////
#define EXTDEPTH 3
#define EXTVALUE 350 /* value of a Knight */
#define MAXGAIN 150
...
/* Evaluation is also done at the interior of the tree */
score = Evaluate(p, side);
...
/* This is the start of the null-move part */
if ((nullmove) && (depth > 1) && (!InCheck(p, side)) &&
(score > alpha - MAXGAIN))
{
nullmovescore = -PVS(p, -beta, -alpha, depth-R-1, FALSE, !side);
if (nullmovescore >= beta)
{ /* Cutoff */
return nullmovescore;
}
alpha = MAX(nullmovescore,alpha);
/* deepsearch extension part */
if ((depth <= EXTDEPTH) && (score >= beta) &&
(nullmovescore < score - EXTVALUE))
{
depth++;
}
}
////////////////////////////////////////////////////////////////////////
=Ernst=
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.