关于带有 alpha beta 修剪的随机性和 minmax 算法

Question

在 alpha beta 算法中运行domly 选择一个节点的子节点是否比按顺序选择它们更有机会获得截断？

这是我添加的带有 *** 标记的伪代码。

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

我运行在连接四人游戏中用这个做了一个小样本，它似乎运行快了一点，但是当我实际计算有和没有运行的截止点时domness，没有运行domness 的截止值更多。有点奇怪。

是否可以证明它更快（或更慢）？

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?

视情况而定。 children 未明确随机化时的顺序是什么？

当移动列表已经按分数排序时，最佳截断（最大数量的 alpha-beta 修剪）出现 - 也就是说，最佳移动首先出现，然后是第二好的，依此类推。

当然，如果我们已经知道最好的着法是什么，我们就不需要一开始就搜索它。

然后，许多游戏引擎所做的是，它们会缓存特定位置的先前评估，并根据先前的分数对移动 table 进行排序（假设该位置先前已被评估）。此类缓存分数通常不再准确，因为事件视界现在更远了，但使用它们可以作为搜索的良好指南。

关于带有 alpha beta 修剪的随机性和 minmax 算法

About randomness and minmax algorithm with alpha beta pruning

algorithm

random

artificial-intelligence

alpha-beta-pruning

minmax