chess:programming:search:alpha-beta
This is an old revision of the document!
Table of Contents
Chess - Programming - Search - Alpha-Beta
Alpha-Beta
int alphaBeta( int alpha, int beta, int depthleft ) {
if( depthleft == 0 ) return quiesce( alpha, beta );
for ( all moves) {
score = -alphaBeta( -beta, -alpha, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}
NOTE: This makes use of a Quiescence Search, which makes the alpha-beta search much more stable.
score = alphaBetaMax(-oo, +oo, depth);
int alphaBetaMax( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return evaluate();
for ( all moves) {
score = alphaBetaMin( alpha, beta, depthleft - 1 );
if( score >= beta )
return beta; // fail hard beta-cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}
int alphaBetaMin( int alpha, int beta, int depthleft ) {
if ( depthleft == 0 ) return -evaluate();
for ( all moves) {
score = alphaBetaMax( alpha, beta, depthleft - 1 );
if( score <= alpha )
return alpha; // fail hard alpha-cutoff
if( score < beta )
beta = score; // beta acts like min in MiniMax
}
return beta;
}
References
chess/programming/search/alpha-beta.1633992682.txt.gz · Last modified: 2021/10/11 22:51 by peter
