The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm
The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm
复制标题
DOI：
10.1007/3-540-10843-2_41
复制
发表时间：
1981-07
期刊：
影响因子：
--
通讯作者：
J. Pearl
中科院分区：
文献类型：
--
作者：
J. Pearl
本文分析了阶数为n、深度为d的均匀对策树中随机抽取终端值的α-β剪枝算法所检验的终端节点的平均数目Nn，d。结果表明，n，包含分支因子，即∈α−β(n)=ξn/l-ξ，其中，ξ为xn+x-l的正根。数量ξn/1-ξn之前已被确定为所有定向算法的下界。因此，等式∈α−β(n)=ξn/1-ξ使得α-β在定向博弈搜索算法类上渐近最优。
This paper analyzes Nn,d, the average number of terminal nodes examined by the α-β pruning algorithm in a uniform game-tree of degree n and depth d for which the terminal values are drawn at random from a continuous distribution. It is shown that Nn,dattains the branching factor ℝα−β(n)=ξn/l-ξnwhere ξnis the positive root of xn+x-l=0. The quantity ξn/1-ξnhas previously been identified as a lower bound for all directional algorithms. Thus, the equality ℝα−β(n)=ξn/1-ξnrenders α-β asymptotically optimal over the class of directional, game-searching algorithms.