About randomness and minmax algorithm with alpha beta pruning

Question

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

Answer 1

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?

It depends. What order are the children in when not explicitly randomized?

The best cutoff (the highest amount of alpha-beta pruning) occurs when the move list is already ordered by score - that is, the best move occurs first, then the second best, and so on.

Of course, if we already knew what the best move was we wouldn't need to search for it in the first place.

What many game engines do, then, is they cache the previous evaluation of a particular position and sort the move table based on the previous score (assuming the position has been evaluated previously). Such cached scores will typically not be accurate anymore because the event horizon is now further way, but using them serves as a good guideline for searching.