Differences

This shows you the differences between two versions of the page.

--- chess:programming:search:alpha-beta [2021/10/11 22:41] – created peter
+++ chess:programming:search:alpha-beta [2021/10/11 23:28] (current) – peter
@@ Line 1: / Line 1: @@
 ====== 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