文档介绍：Multi-ProbCut ——种新的剪枝算法
ProbCut 的基本思想
在解决博弈问题时，被广泛采用的是剪枝算法和其有严格剪枝条件的改进（如NegaScout ）
一个典型的:z ■ 剪枝如算法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); val = -AlphaBeta(height
Undo(&pos, & delta);
if (val > max) {
if (val >= beta) return val;
max = val;
}
}
return max;
//记录局面的变化
//是否叶节点？
//是，则计算其评价值
对所有可能的招法
//走一步并在delta 中保存变化
-1, -beta, -max）; // 获得 NegaMax 值
//恢复原来局面
//剪枝
//新的最大值
算法1 :使用沱• I-'剪枝的NegaMax算法
而ProbCut 是近十年来出现的一种新的剪枝算法，它不同于以往的如 NegaScout 这样的有严格剪
枝条件的剪枝算法，而是根据具体对弈问题中的概率因素来决定剪枝条件的，所以称之为 ProbCut ，即概
率剪枝。
ProbCut 能够对不太可能影响结果最小-最大值的子树进行剪枝，这种算法的思想基于以下事实：当使用一个较好的局面评价函数（这是一个必要的条件）和使用静态搜索（ Quiescence Search ）时,
在同一局面下用不同深度搜索得到的最小-最大值是高度
相关的。
如图1所示，我们希望在搜索深度 h上，能够通过一个较浅的搜索深度 d（d ::: h）上返回的最小-
最大值Vd对真正的最小-最大值 Vh很好地进行估算（这个浅层的搜索称为检查搜索）。利用这个估算，可以用概率来描述 Vh是否在当前的〉1窗口之外。若估计 Vh在当前的〉窗口之外，则此（根）局面不需要进行更深的搜索，否则就应进行更深的搜索以得到真正的最小-最大值。而利用浅层搜索对深层搜索进行估算所产生的开销相比深层搜索的开销而言可以忽略不计。
一种利用V来描述Vh的自然的想法是利用线性表达式： Vh =a Vd • b • e，这里a，b R，
e为服从正态分布［0,二2］的误差变量。若局面评价函数是高度稳定的，则 a的期望值为1，b的期望
值为0且er2极小，也就是说使用 V? =a Vd +b对Vh进行估算的精度是非常高的。那么可以使用以下关系式来估算Vh - B的概率：
Vh > V? +e启（Vh —B -e/①，由于一eg服从［0, 1］上的正态分布
（分布函数为 ①），所以可引出乂巴B的概率至少为p，当且仅当B）/岸 ①*（p）。这个条件等价于Vd <①° p i「亠）• b / a。类似的，可以得到 Vh乞a的概