Author: Bruce Moreland
Date: 11:32:43 09/29/98
Go up one level in this thread
On September 28, 1998 at 16:48:57, John Coffey wrote:
>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;
>}
int Search(pos, depth, alpha, beta)
{
if (depth == 0)
return Eval(pos);
for (succ = Successors(pos); !Empty(succ);) {
pos = RemoveOne(succ);
value = -Search(pos, depth - 1, -beta, -alpha);
if (value >= beta) // Fail high.
return value;
if (value > alpha) // PV move.
alpha = value;
}
return alpha; // This is a fail low, unless you found >= 1 PV move, in
which
// case the caller gets a score that is > alpha and < beta
(PV).
}
>
>This code I understand, but .....
>
>my question is about the following ....
>
>"A fail low is when you search a position and return a score <= alpha. A fail
>high is when you return a score that is >= beta."
>
>What are the significance of "fail low" and "fail high" and how do they
>affect the search?
A fail low is when this position sucks. A fail high is when it is great. When
you get a fail high, you prune out the rest of the successors, so you save work.
The only difference between alpha-beta and straight min-max is that one if
statement. If you take it out, you will search the entire tree.
A fail low will result in a fail high after the "return alpha" statement, when
control is returned to the caller, so a fail low saves work, too.
bruce
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.