Author: Don Dailey
Date: 08:00:31 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"?
>
>
>
>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...
Hi John,
Your program should return a score of the best move found which may
or may not be greater than alpha. But if the search returns
a score less than or equal to alpha you have a case of a fail low.
This is not a problem unless it propogates to the root node, if you
are doing a classic pvs search even this is not a problem unless
you also search the first root move with a window (aspiration stuff.)
-- Don
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.