Author: John Scalo
Date: 23:42:07 01/05/98
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...
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.