Computer Chess Club Archives




Subject: Re: Deep Search Extension

Author: Stuart Cracraft

Date: 10:50:10 01/22/98

Go up one level in this thread

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
>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
>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* ... :-(

It made my search tree explode too. I will try putting in the Dark
limitations of depth = 2 and the first 2 * iteration-number plies.
for the tip!

This page took 0.04 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.