Author: Bruce Moreland
Date: 09:28:20 05/13/00
Go up one level in this thread
On May 12, 2000 at 17:40:06, Bruce Moreland wrote:
>On May 12, 2000 at 13:34:39, John Coffey wrote:
>
>>My evaluation function is partially complete.
>>I have move generation done, so now it is time to add the
>>alpha beta search.
>>
>>I have seen pseudo code for alpha beta before but can no longer
>>find it. Could someone please direct me to a source.
>>
>>I have been confused by the terms "fail high" and "fail low"
>>although I think that I understand the principles behind it.
>>
>>I would also like to see pseudo code for null move pruning.
>>
>>Thanks in advance,
>>
>>John Coffey
>
>int search(int alpha, int beta, int depth)
>{
> if (depth <= 0)
> return eval();
> while (more_moves()) {
> int cur;
>
> make_next_move();
> cur = -search(-beta, -alpha, depth - 1);
> unmake_move();
> if (cur >= beta)
> return beta; // Fail high.
> if (cur > alpha)
> alpha = cur; // PV.
> }
> return alpha; // Fail-low, if "alpha = cur" never was
>} // executed, otherwise PV.
>
>You call this with "search(-32767, 32767, 8)" to do an 8-ply search. It returns
>the value of the position, but doesn't return the best move or the PV. That's a
>pretty minor enhancement.
>
>If you want a normal min-max search, just take out the two lines that do
>fail-high.
>
>bruce
Here's the search with null-move. It's important that the added call to search
results in another move being made by the opponent.
Something I left out of this search and the other search is detecting mates and
stalemates, but that's not a general alpha-beta thing, and it's not very hard.
You just check to see if no legal moves were found, and react accordingly based
upon whether the side to move is in check.
int search(int alpha, int beta, int depth, int fAllowNull)
{
if (depth <= 0)
return eval();
if ((fAllowNull) && (-search(-beta, -alpha, depth - 3, FALSE) >= beta))
return beta;
while (more_moves()) {
int cur;
make_next_move();
cur = -search(-beta, -alpha, depth - 1, TRUE);
unmake_move();
if (cur >= beta)
return beta; // Fail high.
if (cur > alpha)
alpha = cur; // PV.
}
return alpha; // Fail-low, if "alpha = cur" never was
} // executed, otherwise PV.
Here is a quiescent search. You can replace "eval" in the other searches with
this. The idea here is that you search through captures you will allow, and see
if any of them are good. You also allow the side to move to return the value of
"eval", if that's > alpha. Otherwise, captures will seem to be forced, which is
right in checkers but not in chess.
int qsearch(int alpha, int beta)
{
int quies = eval();
if (quies >= beta)
return beta; // Fail-high on static eval.
if (quies > alpha)
alpha = quies;
while (more_good_captures()) {
int cur;
make_next_move();
cur = -qsearch(-beta, -alpha);
unmake_move();
if (cur >= beta)
return beta;
if (cur > alpha)
alpha = cur;
}
return alpha; // This can be the value returned by eval, it can be a
} // fail-low, or it can be a PV capture move.
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.