Computer Chess Club Archives




Subject: Re: Deep Search Extension

Author: Ernst A. Heinz

Date: 02:03:38 01/22/98

Go up one level in this thread

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


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