Author: Dan Homan
Date: 12:02:24 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
Alpha/Beta is just a way of keeping track of the worst/best you can
do at a given position in the search tree.
Whenever you get a cutoff, you are proving that the part of the search
tree that you are in doesn't matter because your opponent has a better
move somewhere else in the tree.
For example:
Say we are somewhere deep in the search tree with the following alpha, beta
scores:
beta = 5, alpha = -10
My opponent can guarantee that I get a score no better than 5. That is
what beta is.... If I find a move at this position with a score better
than 5, that only means that my opponent can choose a different move,
earlier in the tree to prevent this situation.
Because I am guaranteed never to get a score better than 5, when a find
a move that appears to give a higher score, I know that this move can
be prevented by my opponent and therefore doesn't matter.
alpha = -10 means that I can guarantee that I get a score of at least -10.
When I am looking at the moves for my opponent, my alpha (-10) becomes
his beta (+10) and the same rules apply.
- Dan
>
>
>
>------------------------------------------------
>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.