关于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
我在一个连接四个游戏上运行了一个小样本,它似乎运行得更快一些,但是当我实际计算有无随机性时的截止点时,没有任何随机性的截止点更多。 这有点奇怪。
是否有可能证明它更快(或更慢)?
在αβ算法中随机选择一个节点的孩子比选择它们更有机会得到一个截断点?
这取决于。 在没有明确随机化的情况下,儿童的顺序是什么?
当移动列表已经按照分数排序时,出现最佳截断(alpha-beta修剪的最高数量) - 也就是说,最佳移动先发生,然后再次发生,依此类推。
当然,如果我们已经知道最好的举措是什么,我们不需要首先搜索它。
然后,许多游戏引擎所做的就是缓存先前对特定位置的评估,并根据以前的评分对移动表进行排序(假设位置已经被评估过)。 这种缓存的分数通常不会再准确,因为事件视界现在是更进一步的方式,但将它们用作检索的良好指导方针。
链接地址: http://www.djcxy.com/p/56385.html上一篇: About randomness and minmax algorithm with alpha beta pruning