Author: Stuart Cracraft
Date: 22:30:42 06/13/98
Go up one level in this thread
On June 13, 1998 at 14:28:35, Robert Hyatt wrote:
>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=
The reason I discarded deep search extensions was the seeming extreme
cost of doing interior-tree evaluations which it requires.
Didn't pay off for me... s'ppose having a specialized evaluator might be
a possibility. But with my full evaluator (which is not all that complex
either)
the slowdown was more than the speedup...
--Stuart
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.