Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Aspiration search, PVS

Author: Robert Hyatt

Date: 18:21:56 12/28/02

Go up one level in this thread


On December 28, 2002 at 12:12:01, Russell Reagan wrote:

>I am a little confused about how to determine when to re-search after you have
>tried an aspiration search. I was looking at Bruce's PVS example on his website,
>and it seems counter-intuitive (not saying it's wrong, just confusing to me).
>
>if (fFoundPv) {
>            val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);
>            if ((val > alpha) && (val < beta)) // Check for failure.
>                val = -AlphaBeta(depth - 1, -beta, -alpha);
>        } else
>            val = -AlphaBeta(depth - 1, -beta, -alpha);
>}
>
>What this says to me is that if the aspiration search returns a score that lies
>within the bounds of (alpha,beta), the asipration search failed, and we need to
>re-search. As I understand it, you only need to re-search when you discover that
>the node is not a PV node (as you assumed). If the score is within the bounds of
>(alpha,beta), doesn't mean that it's a PV node? So why the re-search? It seems
>more natural to me that you would research if the aspiration search returned a
>score less than alpha (which means we have an alpha node, and need to re-search)
>or a score greater than beta (which means we have a beta node, and we're done).
>
>Where is the mistake in my thinking?


It is very subtle.  But there are two cases.

case 1:  you enter the current search with a normal (non-null) alpha/beta
boundary condition.  That is, alpha != beta-1...  You search the first move,
and get a score, then you search the remaining moves with alpha=best, beta=
best+1.  If, at any time, you return with a score > alpha, then it is obviously
a "fail high".  Since it will be > alpha, but also less than the original beta
value, you need to re-search it with the original bounds to get a true score.

case 2:  you enter the current search with a null alpha/beta boundary condition,
that is alpha=beta-1.  If you get a score > alpha, then it obviously must
be >= beta, but you can't increase beta since the original beta value was so
restricted.  You do _not_ re-search here since it is impossible.

That is why that strange-looking test works.  :)




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.