Author: Jason
Date: 11:26:28 08/17/99
I'm kinda new to chess programming, but not programming in general. Anyway, I
found the below description of alpha-beta searching on Paul Verhulst's chess
page (http://www.xs4all.nl/~verhelst/chess/search.html). Abandoning a branch b/c
of a cutoff that's HIGHER in value, but somehow a worse move, doesn't seem to
make sense to me.
Thanks in advance for explanations,
Jason
------------------------------------------------
The AlphaBeta search procedure gets two additional arguments which indicate the
bounds between which we are interested in exact values for a position:
int AlphaBeta (pos, depth, alpha, beta)
{
if (depth == 0) return Evaluate(pos);
best = -INFINITY;
succ = Successors(pos);
while (not Empty(succ) && best < beta)
{
pos = RemoveOne(succ);
if (best > alpha) alpha = best;
value = -AlphaBeta(pos, depth-1, -beta, -alpha);
if (value > best) best = value;
}
return best;
}
The gain from AlphaBeta will come form the earlier exit from the while loop; a
value of best that equals or exceeds beta is called a cutoff. These cutoffs are
completely safe because they mean that this branch of the tree is worse than the
prinicpal variation. The largest gain is reached when at each level of the tree
the best
successor position is searched first, because this position will either be part
of the principal variation (which we want to establish as early as possible) or
it will cause
a cutoff to be as early as possible.
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.