Differences

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

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