Author: Robert Hyatt
Date: 05:18:18 01/06/98
Go up one level in this thread
On January 06, 1998 at 02:42:07, John Scalo wrote:
>I have a search algorithm that looks something like this (with lots of
>stuff
>
>omitted) -
>
>
>
>Search(alpha, beta, depth, *bestPath, ...)
>
>{
>
> if (...deep enough...)
>
> {
>
> return Eval();
>
> }
>
> GenerateMoves(successors, &succIndex);
>
> for (i=0; i<succIndex; i++)
>
> {
>
> newMove = SelectMove();
>
> MakeMove(newMove);
>
> if (KingInCheck())
>
> {
>
> UnmakeMove();
>
> goto end;
>
> }
>
> //null move stuff omitted
>
> score = -Search(-beta, -alpha, depth+1, movePath, ...);
>
> UnmakeMove(newMove);
>
> if (score > alpha)
>
> {
>
> alpha = score;
>
> *bestPath = movePath;
>
> }
>
> if (alpha >= beta)
>
> {
>
> AddKiller();
>
> AddHistoryMove();
>
> AddToHash(...);
>
> return alpha;
>
> }
>
> end:;
>
> }
>
> AddHistoryMove();
>
> AddToHash(...);
>
> return alpha;
>
>}
>
>
>
>The question is, if the search goes through every move and never gets a
>score >
>
>alpha, what's the appropriate action? Is this what is referred to as a
>"fail low"?
yes. What you have is a problem where alpha (lower bound) is too high.
You
need to re-search the position with a lower alpha value. If this
happens
at positions other than the root, you simply return alpha. If this gets
backed up to the root, relax alpha and re-search...
>
>
>
>The problem of course is that a best move (or path in my case) hasn't
>been
>
>established and the alpha that's getting returned isn't accurate. I
>assume that
>
>the search needs to be redone with an infinite alpha-beta window but I'm
>
>wondering if there's a preferred way of "notifying" the calling Search()
>that the
>
>window was inadequate.
>
>
>
>Thanks,
>
>John
>
>
>
>P.S. Apologies in advance if Internet Explorer contorts the text as it's
>done in the past when posting to this board...
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.