Author: Robert Hyatt
Date: 11:28:35 06/13/98
Go up one level in this thread
On June 13, 1998 at 11:31:24, Ernst A. Heinz wrote:
>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.
>
I thought I had remembered it correctly... except that I pointed out
that
Chrilly didn't use PVS, and did his null-move search with a wider
window,
and looked at how bad it failed low to trigger the extension. I can't
do
this as PVS doesn't behave like that...
>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++;
this is as I described it I believe... except that if you use PVS you
can't make the test above, since you either get X or X+1 back from
the null-move, where X won't cut it. To make it work, I simply did a
second null-move search with a much lower window, and if it failed low,
I triggered the extension, producing the same effect as above, but
within
the PVS alpha,alpha+1 framework...
> }
> }
>
>////////////////////////////////////////////////////////////////////////
>
>=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.