2
$\begingroup$

I originally read that Alpha-Beta pruning has time complexity of $O(b\ ^{m/2}\ )$ with perfect ordering (where b = branching factor, m = maximum ply depth) but have recently come across claims that this can be reduced to $O(2\ ^{m/2}\ )$ with optimal ordering. Does anyone know of a proof for this claim?

$\endgroup$
  • 1
    $\begingroup$ Do you have a citation to or a source for these recent claims of $O(2^{m/2})$ time? That might help understand what's going on better. $\endgroup$ – D.W. Oct 31 '13 at 5:20
  • 1
    $\begingroup$ I might be wrong but if you had optimal ordering wouldn't you only have to evaluate two branches since the first will be your min or max and the second would satisfy the respective condition that would prune the rest of its siblings, meaning that you would always only have to evaluate two branches with optimal ordering $\endgroup$ – Francesco Gramano Apr 9 '14 at 10:06
  • $\begingroup$ Might be 4 years late, but for anyone else looking see: Alpha-Beta Search Time Complexity $\endgroup$ – Torso Apr 27 '17 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.