Author: Don Dailey
Date: 08:12:43 06/14/98
Go up one level in this thread
Hi Vincent,
I think the ICCA journal is a good magazine. Like you, I usually
find very little in it that I can immediately use to benefit the
program but I read it for that occasional article. Also, I find
reading the articles often helps me to brainstorm. I get ideas
from them even when I don't believe much in the approach they
use. And finally, it's often fun to read them anyway. It enables
you to get a feel for some of the ideas people are batting around!
I agree most of them are not too relevant. But for every 20 things
I experiment with only a very few succeed. I learn from the
failures too, it makes me smarter for the next success. So I feel
like a get something, even if very little, from even the lesser
articles.
I usually can't wait to read the next issue.
- Don
On June 13, 1998 at 21:47:50, Vincent Diepeveen wrote:
>
>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.