Author: Ricardo Gibert
Date: 18:22:47 08/17/99
Go up one level in this thread
On August 17, 1999 at 14:26:28, Jason wrote:
>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.
AlphaBeta is an improvement on MiniMax. Break out a deck of playing cards and do
a walk through using the deck of cards where each card is an eval of a node. Red
for negative evals, Black for positive. You'll will notice that AlhaBeta will
produce the same result as MiniMax. That's all that AlphaBeta does, but it does
it faster. There is no better substitute for doing a walkthrough in order to
understand what is going on. It is an hour well spent.
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.