Differences

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

--- chess:programming:search:alpha-beta [2021/10/11 22:51] – 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 =====
@@ Line 61: / Line 106: @@
 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