Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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. 

----

===== Savings =====

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**

^Depth^Worst case^Best case^
|n|<nowiki>b^n</nowiki>|<nowiki>b^ceil(n/2) + b^floor(n/2) - 1</nowiki>|
|1|40|40|
|2|1,600|79|
|3|64,000|1,639|
|4|2,560,000|3,199|
|5|102,400,000|65,569|
|6|4,096,000,000|127,999|
|7|163,840,000,000|2,623,999|
|8|6,553,600,000,000|5,119,999|

<WRAP info>
**NOTE:** Assuming constantly **b** moves for each node visited and search depth **n**, the maximal number of leaves in alpha-beta is equivalent to Minimax, b ^ n.

  * Considering always the best move first, it is **b ^ ceil(n/2) plus b ^ floor(n/2) minus one**.
  * This table which also demonstrates the odd-even effect.

</WRAP>

----

===== Alpha-Beta =====

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

<WRAP info>
**NOTE:**  This makes use of a Quiescence Search, which makes the alpha-beta search much more stable.
</WRAP>


----

<code>
score = alphaBetaMax(-oo, +oo, depth);
</code>



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

----

===== References =====

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