关于用alpha beta修剪的随机性和最小最大值算法

Question

在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 

我跑了这个小样本上的连接四个游戏，它似乎运行快一点，但是当我真正使用和不使用随机数的临界值，有更多的截断没有随机性。这有点奇怪。

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

Answer 1

在alpha beta算法中随机选择一个节点的孩子比按顺序选择它们有更好的机会得到一个截断？

这取决于。在没有明确随机化的情况下，儿童的顺序是什么？

当移动列表已按分数排序时，出现最佳截断（alpha-beta修剪的最高数量） - 也就是说，最佳移动先发生，然后再次发生，依此类推。

当然，如果我们已经知道最好的举措是什么，我们不需要首先搜索它。

然后，许多游戏引擎会缓存先前对特定位置的评估，并根据先前评分（假设位置已经先前评估）对移动表进行排序。这种缓存的分数通常不会再准确，因为事件视界现在是更进一步的方式，但将它们用作检索的良好指导方针。