Differences

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

--- chess:programming:search:alpha-beta [2021/10/11 23:23] – peter
+++ chess:programming:search:alpha-beta [2021/10/11 23:28] (current) – peter
@@ Line 23: / Line 23: @@
-**number of leaves with depth n and b = 40**
+**The minimum number of leaves with depth n and b = 40**
 ^Depth^Worst case^Best case^
-|n|b^n|<nowiki>b^{\lceil n / 2 \rceil} + b^{\lfloor n / 2 \rfloor} - 1</nowiki>|
+|n|<nowiki>b^n</nowiki>|<nowiki>b^ceil(n/2) + b^floor(n/2) - 1</nowiki>|
 |1|40|40|
 |2|1,600|79|
@@ Line 36: / Line 36: @@
 |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 99: / 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