1

在 alpha beta 算法中随机选择一个节点的子节点会比按顺序选择它们更有可能被截断吗？

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

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

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

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

4

1 回答 1

1

在 alpha beta 算法中随机选择一个节点的子节点会比按顺序选择它们更有可能被截断吗？

这取决于。如果没有明确随机化，孩子的顺序是什么？

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

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

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

于 2016-04-30T12:44:21.710 回答