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)?