4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

Citing Wikipedia:

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.