文档介绍：Multi-ProbCut——一种新的剪枝算法
一、ProbCut的基本思想
在解决博弈问题时,被广泛采用的是剪枝算法和其有严格剪枝条件的改进(如NegaScout)。一个典型的剪枝如算法1所示:
int AlphaBeta(int height, int alpha, int beta)
{
int i, max, val;
POSDELTA delta; //记录局面的变化
if (Leaf(&pos, height)) //是否叶节点?
return Eval(&pos); //是,则计算其评价值
max = alpha;
for (i = 0; i < ; i ++) { //对所有可能的招法
Move(&pos, [i], &delta); //走一步并在delta中保存变化
val = -AlphaBeta(height – 1, -beta, -max); //获得NegaMax值
Undo(&pos, &delta); //恢复原来局面
if (val > max) {
if (val >= beta) return val; //剪枝
max = val; //新的最大值
}
}
return max;
}
算法 1:使用剪枝的NegaMax算法
而ProbCut是近十年来出现的一种新的剪枝算法,它不同于以往的如NegaScout这样的有严格剪枝条件的剪枝算法,而是根据具体对弈问题中的概率因素来决定剪枝条件的,所以称之为ProbCut,即概率剪枝。
ProbCut能够对不太可能影响结果最小-最大值的子树进行剪枝,这种算法的思想基于以下事实:当使用一个较好的局面评价函数(这是一个必要的条件)和使用静态搜索(Quiescence Search)时,在同一局面下用不同深度搜索得到的最小-最大值是高度
图1
相关的。
如图1所示,我们希望在搜索深度上,能够通过一个较浅的搜索深度上返回的最小-最大值对真正的最小-最大值很好地进行估算(这个浅层的搜索称为检查搜索)。利用这个估算,可以用概率来描述是否在当前的窗口之外。若估计在当前的窗口之外,则此(根)局面不需要进行更深的搜索,否则就应进行更深的搜索以得到真正的最小-最大值。而利用浅层搜索对深层搜索进行估算所产生的开销相比深层搜索的开销而言可以忽略不计。
一种利用来描述的自然的想法是利用线性表达式:,这里,,为服从正态分布的误差变量。若局面评价函数是高度稳定的,则的期望值为1,的期望值为0且极小,也就是说使用对进行估算的精度是非常高的。那么可以使用以下关系式来估算的概率:
,由于服从上的正态分布(分布函数为),所以可引出的概率至少为,当且仅当。这个条件等价于。类似的,可以得到的概率至少为,当且仅当。因而,我们只需要关心是否大于或小于一个由、以及常量、、和构成的简单关系式的值。根据以上分析可以得到如下的ProbCut算法:
#define PERCENTILE
#define DP 4 //浅层搜索深度
#define D 8 //检查深度
int AlphaBeta(int height, int alpha, int beta)
{
...
if (heig