[Solved]: About randomness and minmax algorithm with alpha beta pruning

Problem Detail: 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)?

Asked By : kuhaku

Answered By : manlio

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56824 3.2K people like this

Download Related Notes/Documents