StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>O(b^(d/2)) correspond to the best case time complexity of alpha-beta pruning. <a href="http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning" rel="noreferrer">Explanation</a>:</p> <blockquote> <p>With an (average or constant) branching factor of b, and a search depth of d plies, the maximum number of leaf node positions evaluated (when the move ordering is pessimal) is O(b<em>b</em>...*b) = O(b^d) – the same as a simple minimax search. If the move ordering for the search is optimal (meaning the best moves are always searched first), the number of leaf node positions evaluated is about O(b*1*b*1*...*b) for odd depth and O(b*1*b*1*...*1) for even depth, or O(b^(d/2)). In the latter case, where the ply of a search is even, the effective branching factor is reduced to its square root, or, equivalently, the search can go twice as deep with the same amount of computation.</p> <p>The explanation of b*1*b*1*... is that all the first player's moves must be studied to find the best one, but for each, only the best second player's move is needed to refute all but the first (and best) first player move – alpha–beta ensures no other second player moves need be considered.</p> </blockquote> <p>Put simply, you "skip" every two level:</p> <p><img src="https://i.stack.imgur.com/kuAI1.png" alt="enter image description here"></p> <p>O describes the limiting behavior of a function when the argument tends towards a particular value or infinity, so in your case comparing precisely O(b^(d/2)) with small values of b and d doesn't really make sense.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload