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)?
Aucun commentaire:
Enregistrer un commentaire