# About randomness and minmax algorithm with alpha beta pruning

Will choosing the child of a node randomly in the alpha beta algorithm have a better chance to get a cut off than choosing them in order?

Here's the pseudocode with my addition marked with ***.

function alphabeta(node, depth, α, β, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
arrange childs of node randomly ***
if maximizingPlayer
v := -∞
for each child of node
v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
α := max(α, v)
if β ≤ α
break (* β cut-off*)
return v
else
v := ∞
for each child of node
v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
β := min(β, v)
if β ≤ α
break (* α cut-off*)
return v


I ran a small sample with this on a connect four game and it does seem to run a little faster, but when I actually count the cutoffs with and without randomness, there are more cutoffs without randomness. That's a little odd.

Is it possible to prove that it's faster (or slower)?

Adding on Yuval Filmus' answer, when testing the time performance of a program, you have to consider that a shallow search with a complex, optimal move ordering heuristics applied everywhere can take more time than a fast, random order search.

This is the for the same reason under which a $O(n)$ algorithm can be faster than a $O(log(n))$ for small inputs.

Usually, for games, the "crosspoint" isn't very large. Anyway many well crafted implementations take advantage of this using different move ordering logic depending on search depth.

As the number of positions searched decreases exponentially each move nearer the current position, it is worth spending considerable effort on sorting early moves. In practice, the move ordering is often determined by the results of earlier, smaller searches.

Many aspects of this tradeoff are better understood studying the Iterative Deepening technique (initially adopted for time management, it has proved surprisingly beneficial as far as move ordering is concerned in alpha-beta).

It's neither faster nor slower, since it depends on your order. Your order might be the best possible order, in which case randomness hurts; or it might be the worst possible order, in which case randomness helps.

If you want to guarantee not hitting a worst case behavior, you can use randomness. But it might be better to choose the order heuristically using less than full randomness.