在α-β剪枝算法中，随机选择节点的子节点是否比按顺序选择更有可能导致剪枝？

以下是我的修改用***标记的伪代码。

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

我在一个四子棋游戏中进行了小样本测试，确实运行速度似乎有所提升，但当我实际统计有无随机性时的剪枝次数时，没有随机性的情况剪枝次数更多。这有点奇怪。

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

回答：

在α-β剪枝算法中，随机选择节点的子节点是否比按顺序选择更有可能导致剪枝？

这取决于情况。当没有明确随机化时，子节点的顺序是什么？

最佳剪枝（最高程度的α-β剪枝）发生在移动列表已经按分数排序的情况下——也就是说，最佳移动首先出现，然后是第二好的移动，依此类推。

当然，如果我们已经知道最佳移动是什么，我们一开始就不需要搜索它了。

因此，许多游戏引擎所做的是，它们缓存特定位置的先前评估，并根据先前的分数排序移动表（假设该位置之前已被评估）。这样的缓存分数通常不再准确，因为事件视界现在更远，但使用它们作为搜索的良好指导方针。