Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Deep Search Extension

Author: Robert Hyatt

Date: 05:42:06 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
>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).

Yep... Forgot.  For me, I couldn't do the above... because I don't use
fail-soft and most scores (excepting mate and draw) are always inside
the alpha/beta window.  But shifting the null-move window down does
exactly the same thing, ie searching alpha-piece, beta-piece produces
the same information.

I thought my idea of first noting that this was a PV move, and then
trying the null-move threat extension only after that was from the
paper.  Perhaps not.  This approach worked better than the original
idea in his paper.  But neither improved my results.

In any case, I played about 5,000 games with, 5,000 games without, and
my result was without was better by a significant game score.  This was
done on ICC, so there was variability in the quality of opponents.  But
after 5,000 games for each, and looking at a sample of who played, the
opponent pool was pretty constant with lots of GM players in the
mix.

I do plan on trying it again...  when I have some time where I have no
planned changes, so I can adequately measure it again.
>
>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=



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