Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Deep Search Extension

Author: Robert Hyatt

Date: 18:56:27 01/21/98

Go up one level in this thread


On January 21, 1998 at 18:52:44, Heiko Mikala wrote:

>
>On January 19, 1998 at 04:21:26, Ernst A. Heinz wrote:
>
>>On January 18, 1998 at 18:53:15, Bruce Moreland wrote:
>>>On January 18, 1998 at 10:37:59, Robert Hyatt wrote:
>>>
>>>>(...) The idea was to shift the null-move window downward, and
>>>>then notice whether the null-move search fails high or low.  If it fails low,
>>>>(...) you extend by 1 ply.
>>>
>>>The only place I've read about this recently is on the Dark Thought
>>>page.  Are you guys still doing this, or am I confused?
>>
>>Yes, I have modified and fine-tuned the original deep-search rules quite
>>a bit in order to make the extension usable. I still like it (...)
>
>Could you or Bob or someone else maybe try to explain this extension
>in a bit more detail? I don't understand what is meant by "shift the
>null-
>move window downward". Also, someone wrote, that this extension
>should only be used near the leaves of the tree? Is it possible to use a
>zero-width window for the null-move in conjunction with the deep search
>extension and does one extend on all fail-lows?
>
>I tried Bruce's mate threat extension (everyone did, I guess...), and it
>works fine.
>


Imagine this:  when you do a null move search, if it fails high we exit
the current node with no more searching.  If it fails low, we only know
that standing pat leaves us in a bad position.

Imagine then, searching a move and when you find that the score is going
to be backed up in the tree (this is a PV node) before you back up the
score you make a quick test.  Do a null-move search, but lower alpha and
beta significantly.  If the null move search fails low here, you know
that doing nothing is *really* bad.  Because with the lowered window the
null-move search should fail high here easily.  Since it still fails
low,
but this move we are backing up doesn't fail low (it is getting backed
up, remember) this move is either really good, or else it is simply
holding
off some threat that the opponent has.  If playing this move is really
good
(good enough to back up) and doing nothing is really bad (because we
searched
a null with alpha-X, beta-X where X is substantial) then we can become
suspicious that this move might be a "horizon" move.  We then re-search
just this PV move, but to 1 ply deeper, and use that result as the
score.

It will produce some interestingly long PV's, but I decided to toss it
out a long while back.  I kept the code (I have a module threat.c that
does this) so that I can test it again somewhere down the line.


>After that I tried the deep search extension in the way I understood it,
>but the only effect was an exploding search tree, so I guess I'm missing
>an important point...

that is one effect.  :)



>
>
>Thank you very much, and, wow, this is a fantastic newsgroup!
>It is very impressive and very very interesting to listen to all you
>experts
>out there!
>I've been working on my own chess-program for some years, read
>some books and many articles about chess programming, but this
>group motivated me to start again (or go on) to work on my old
>sources.
>
>Thank you all,
>
>   Heiko.



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.