Author: Vincent Diepeveen
Date: 18:47:50 06/13/98
Go up one level in this thread
On June 13, 1998 at 11:31:24, Ernst A. Heinz wrote:
Thanks for the writing down of the pseudo-code!
>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.
Yes I know they're red but... ...they're more expensive than a Ferrari,
and
it doesn't contain a good engine too.
Jaap offered me when i bought AICC 8 the volume 7 also for a cheap
price. i took it of course, no one can refuse offers from Jaap.
Yet most articles in it are pure trash, in contradiction to 8.
Like the only interesting thing: proof number search does not contain
pseudo code so we can test the results, and parallelism is a little
short
explained by Feldmann.
-Opponent modelling is something evident,
-Botwinnik never has booted a computer
-Nunn concluded the same i did, but he took the wrong database;
he took an even more uninteresting one.
-Gobet and jansen never programmed a gameplaying program other
than tic tac toe.
-speculative play in computer chess is also not worth reading it,
although
it's true. We need however pseudo code, and not vague thoughts a la
rgcc.
This 'speculative play thoughts' i already have years, after my program
even managing to lose simply won positions because it complicated it,
and forgot to profitting from opponents who lacked something.
The word linguistic is too difficult for me to spell, so i skipped that
section too, and long term planning i read, but also rejected as the
pseudo code is really childish.
Then schaeffer wrote something for a small audience which doesn't
include me, and Weill is doing something interesting with the wrong
approach.
... ....must i continue?
That for a book of 130 dutch guilder, the monthly salary of a student in
the Netherlands.
>Anyway, below I copy the pseudo-code 1:1 from the article for all
>interested readers:
For which i thank you.
>//////////////////////////////////////////////////////////////////////
>
>#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++;
> }
> }
Oh, now i know why it was never quoted.
This is extensions a la 1980's.
It's 1998 now, cannot use this anymore. Hurts branching factor too much.
Further i'm using PVS, so can't use this.
>////////////////////////////////////////////////////////////////////////
>
>=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.