Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Deep Search Extension

Author: Robert Hyatt

Date: 15:50:22 01/22/98

Go up one level in this thread


On January 22, 1998 at 16:17:35, Stuart Cracraft wrote:

>On January 22, 1998 at 15:29:39, Robert Hyatt wrote:
>
>>On January 22, 1998 at 13:50:10, Stuart Cracraft wrote:
>>
>>>On January 22, 1998 at 05:03:38, Ernst A. Heinz wrote:
>>>
>>>>On January 21, 1998 at 21:56:27, Robert Hyatt wrote:
>>>>
>>>>>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.
>>>>
>>>>No, Bob, the idea as mentioned in Donninger's paper is different. Here
>>>>is
>>>>the reference for all who do not know the article.
>>>>
>>>>Donninger, C. (1993).
>>>>Null move and deep search: Selective search heuristics for obtuse chess
>>>>programs. ICCA Journal, Vol. 16, No. 3, pp. 137--143.
>>>>
>>>>Donninger's idea is to extend the search one ply if a null move near the
>>>>horizon (e.g. at depths <= 3) does not fail high and the null move score
>>>>plus a constant margin (e.g. minor piece value) is <= alpha while the
>>>>static evaluation at the node is >= beta (i.e. fails high). In order to
>>>>get meaningful results for the null move score, you need to do it with a
>>>>full alpha-beta window instead of a zero window (this is a known error
>>>>in
>>>>Donninger's original article).
>>>>
>>>>Citing from my article about how "DarkThought" plays chess:
>>>>
>>>>In order to avoid possibly explosive growth of the search tree as caused
>>>>by excessive deep search extensions in the case of repeated mutual
>>>>mating threats, "DarkThought" restricts them to null moves at depth = 2
>>>>in the
>>>>first "2 * iteration-number" plies on all paths.
>>>>
>>>>>>I tried Bruce's mate threat extension (everyone did, I guess...), and it
>>>>>>works fine.
>>>>
>>>>I just gave it a quick shot but then put it on my to-do list because the
>>>>quick implementation made our search trees *explode* ... :-(
>>>>
>>>>=Ernst=
>>>
>>>It made my search tree explode too. I will try putting in the Dark
>>>Thought
>>>limitations of depth = 2 and the first 2 * iteration-number plies.
>>>Thanks
>>>for the tip!
>>
>>
>>the 2*iteration number won't be enough by itself for sure.  You can find
>>this limit in early versions of crafty sources when I was doing the
>>threat
>>extension.  It helped, but not enough.  however I didn't limit it to
>>near
>>the tips either, because it was also useful nearer to the root where it
>>is just as profitable to extend when there is a threat.  But it is also
>>expensive...
>
>How did you get a score to use for this extension? The original article
>advocates using the evaluation function at the interior tree nodes!
>
>I think this is far more expensive than the extension.
>
>--Stuart


If you think about it, it isn't.  Searching any kind of tree, even a
very
small one is going to be *far* more expensive, because any sub-tree you
search
is going to have endpoints that need evaluation as well.  That will
drown
out the overhead of calling the evaluator at the internal nodes.

Note that I only did the test *if* a move is being backed up as best,
rather than if a node had all branches searched with no good score.
This
was rare enough to not make it expensive.  But doing the
threat-detection
null move search had a cost, and then researching this single move with
a deeper depth had a bigger cost.



This page took 0.18 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.