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