Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Move Extensions

Author: Robert Hyatt

Date: 05:45:11 05/05/98

Go up one level in this thread


On May 04, 1998 at 16:38:43, Roberto Waldteufel wrote:

>I have read about the singular move extension heuristic as used by
>Deeper Blue, and indeed about extension heuristics in general. I have
>also experimented with some variable depth schemes in my search trees.
>One quite promising idea is to set the depth to some arbitrary value at
>the start of each iteration (this value being increased a little prior
>to each successive iteration), and then decrease the depth at each odd
>level by an amount proportional to the logarithm of the number of legal
>moves for the opponent at that level, and calling a quiescence search
>when this depth drops below zero. The depth remains unchanged at even
>levels. This has the effect of pusuing forcing lines for the machine
>much deeper, even if some quiet moves are interspersed between the
>checks. It works very well for some tactical positions where the machine
>can mate or win material through a long sequence of moves, most, but not
>all of which are checks.
>
>I understand that in the singular move extension scheme, the node is
>extended if its evaluation is significantly higher than that of its
>next-best sibling, but I do not understand exactly how this condition
>can be tested when a beta-cutoff occurs, since the evaluation scores for
>some of the sibling nodes is then not known to the algorithm. Can
>anybody enlighten me?
>
>Robeto Waldteufel


If you read the Deep Thought team paper on singular extensions, what you
find is that on a "fail high" node, when you get a fail high condition
you
can *not* return(beta) at that point.  Rather, you *still* have to
search
the remainder of the nodes.  But if you search them to normal depth,
this
turns into a minimax tree that is unaccaptable, so what has to be done
is
to search the remainder of the moves to a reduced depth (ie depth-2 is a
good starting point).  This controls overhead, at the cost of some
accuracy.
The remainder of the moves are searched with an offset alpha/beta
window,
alpha-X, beta-X, where X is found by testing.  If *all* moves fail low
with
that window, then the move that failed high is "singular".  It is
researched
with depth+1...



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.