Chess - Programming - Search - Alpha-Beta

The Alpha-Beta algorithm (Alpha-Beta Pruning, Alpha-Beta Heuristic) is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of the game tree applying a branch-and-bound technique.

• Remarkably, it does this without any potential of overlooking a better move.
• If one already has found a quite good move and search for alternatives, one refutation is enough to avoid it.
• No need to look for even stronger refutations.
• The algorithm maintains two values, alpha and beta.
  • They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively.

The savings of alpha beta can be considerable.

• If a standard Minimax search tree has x nodes, an alpha beta tree in a well-written program can have a node count close to the square-root of x.
• How many nodes can actually be cut depends on how well ordered the game tree is.
  • If the best possible move is always searched first, most of the nodes are eliminated.
  • Of course, what the best move is not always known, or a search would not be needed in the first place.
• Conversely, if the worse moves is always searched before the better moves, no part of the tree would be able to be cut at all!
  • For this reason, good move ordering is very important, and is the focus of a lot of the effort of writing a good chess program.

The minimum number of leaves with depth n and b = 40

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;
}

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;
}

http://web.archive.org/web/20120421170110/http://chessprogramming.wikispaces.com/Alpha-Beta

http://web.archive.org/web/20120222165548/http://chessprogramming.wikispaces.com/Odd-Even+Effect