周恒（zhouheng1212 ）的窝！(粗体字文章别删)

zhouheng1212

标  题: 概率剪枝法
发信站: 逸仙时空 Yat-sen Channel (Sun Dec  2 21:48:40 2001), 转信

My fault!

Multi-ProbCut——一种新的剪枝算法
一、ProbCut的基本思想
在解决博弈问题时，被广泛采用的是 剪枝算法和其有严格剪枝条件的改进（如NegaSco
ut）。一个典型的 剪枝如算法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 < pos.movenum; i ++) { //对所有可能的招法
Move(&pos, pos.move[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能够对不太可能影响结果最小－最大值的子树进行剪枝，这种算法的思想基于以
下事实:当使用一个较好的局面评价函数（这是一个必要的条件）和使用静态搜索（Qu
iescence Search）时，在同一局面下用不同深度搜索得到的最小－最大值是高度
图1
相关的。
如图1所示，我们希望在搜索深度 上，能够通过一个较浅的搜索深度 上返回的最小－最
大值 对真正的最小－最大值 很好地进行估算（这个浅层的搜索称为检查搜索）。利用
这个估算，可以用概率来描述 是否在当前的 窗口之外。若估计 在当前的 窗口之外，
则此（根）局面不需要进行更深的搜索，否则就应进行更深的搜索以得到真正的最小－
最大值。而利用浅层搜索对深层搜索进行估算所产生的开销相比深层搜索的开销而言可
以忽略不计。
一种利用 来描述 的自然的想法是利用线性表达式: ，这里 ，  ， 为服从正态分布
的误差变量。若局面评价函数是高度稳定的，则 的期望值为1， 的期望值为0且 极小，
也就是说使用 对 进行估算的精度是非常高的。那么可以使用以下关系式来估算 的概率
:
  ，由于 服从 上的正态分布（分布函数为 ），所以可引出 的概率至少为 ，当且仅当
  。这个条件等价于 。类似的，可以得到 的概率至少为 ，当且仅当 。因而，我们只
需要关心 是否大于或小于一个由 、 以及常量 、 、 和 构成的简单关系式的值。根据
以上分析可以得到如下的ProbCut算法:
#define PERCENTILE 1.5
#define DP     4   //浅层搜索深度
#define D    8   //检查深度
int AlphaBeta(int height, int alpha, int beta)
{
  ...
  if (height == D) {
int bound;
  /*v >= beta 的概率至少为p？是，则进行剪枝*/
bound = round((+PERCENTILE * sigma + beta –b)/a);
if (AlphaBeta(DP, bound – 1, bound) >= bound) return beta;
  /*v <= alpha 的概率至少为p？是，则进行剪枝*/
bound = round((-PERCENTILE * sigma + alpha – b)/a);
if (AlphaBeta(DP, bound, bound + 1) <= bound) return alpha;
  }
  ...
}
算法 2:使用ProbCut扩展的 剪枝算法
在算法2中，对于高度为 的节点，首先使用深度为 的零窗口搜索来判断 或者 的概率是
否至少为 。
二、参数的选择
若使用搜索深度  进行搜索，那么使用算法2时要进行的蛮力搜索的深度为 。从另一方
面来说，在使用普通的 算法进行深度为 的搜索的相同时间内，使用算法2的最大搜索深
度不会超过 ，这是因为 的深度总会被完全搜索。选择一个较大的PERCENTILE会导致花
费大量时间进行浅层的搜索，因为这样只会有很少的向前的剪枝发生。而在另一种极端
的情况下，会有许多（错误的）剪枝发生──这时深度为 的搜索退化成了深度为 的搜
索。在使用线性回归法来估计参数 、 和 前，必须选择搜索深度 和 。若 太大，误差
变量的变化范围将会增大并且因此减少了剪枝的数量。而从另一方面来说， 也不能够太
小，否则测试搜索所带来的开销可能会抵消掉浅层搜索所节约的时间。此外，在选择 时
必须考虑到这个深度在对弈时应会达到并且大量的局面评价应该在合理的时间内完成。
和 往往是靠经验来选择的。
在选择了 和 后，就要通过大量的蛮力搜索的实例使用线性回归法来获得参数 、 和 ，
在选取这些实例时应涵盖各种典型的局面，以减小参数的偏差。而PERCENTILE参数（即
）的选择常通过与使用普通的 算法的程序对弈来获得（Logistello的这个值为1.5）。

三、Multi-ProbCut
仔细考察ProbCut算法，可以发现可能对其进行如下改进:
1、 ProbCut算法仅仅在一个特定的深度上进行检测，若未满足概率剪枝条件，那么在其
后的搜索中仅仅进行蛮力搜索而不会对其进行更多的概率剪枝，然而ProbCut算法仍然能
够在这些蛮力搜索中被使用。故而，可以在各个搜索深度上递归地使用概率剪枝的判断
，以进行更多的剪枝（图2）。
图2:在不同的深度上向前剪枝
2、 在极端不平衡的局面下（指一方占有极大优势），通常只要通过很浅的检查搜索就
能够进行剪枝了。因而，使用逐渐加深的检查搜索直到发生剪枝可能会节省额外的时间
（图3）。
图3:逐渐加深的检查搜索
3、 ProbCut采用的是单一的剪枝条件（算法中2的PERCENTILE），若能够分别对不同的
局面采用不同的参数进行判断，则性能可能有所改进。
4、 将简单的线性函数替换为更加精确的使用战术和局面特性来估计的函数可能会得到
更好的性能。不过在实践中，至少在Othello和国际象棋的程序中是很难找到这样的函数
的，因为在静态搜索时已经充分考虑到了这些战术因素。
考虑以上1至3点，可以对ProbCut算法作出改进，新的算法称为Multi-ProbCut（简称为
MPC），如算法3所示:
#define MAX_STAGE  64 //不同类型的局面数，例如局//面上的棋子数
#define MAX_HEIGHT 13 //最大检查深度
#define NUM_TRY   2 //最大检查次数
//对于不同局面和深度的ProbCut参数
struct Param {
  int d; //检查深度
  float p; //剪枝条件
  float a, b, sigma； //参数
} param[MAX_STAGE + 1][MAX_HEIGHT + 1][NUM_TRY]；
Position pos;
int MPC(int height, int alpha, int beta)
{
  int i, max, val;
  POSDELTA delta; //记录局面的变化
  if (Leaf(&pos, height))  //是否叶节点？
return Eval(&pos); //是，则计算其评价值
  //检查部分:
  if (height <= MAX_HEIGHT) {
    for (i = 0; i <= NUM_TRY; i++) {
     int bound;
    Param &pa = param[pos.stage][height][i];
    if (pa.d < 0) break;   //检查终止？
    bound=round((pa.p*pa.sigma+beta–pa.b)/pa.a);
     if (AlphaBeta(pa.d, bound – 1, bound) >= bound)
    return beta;
bound=round((-pa.p*pa.sigma+alpha-pa.b)/pa.a);
if (AlphaBeta(pa.d, bound, bound + 1) <= bound)
  return alpha;
    }
  }
  //Alpha-Beta剪枝算法的剩余部分
  max = alpha;
  for (i = 0; i < pos.movenum; i++) {
    Move(&pos, pos.move[i], &delta);
    val = -MPC(height – 1, -beta, -max);
    Undo(&pos, &delta);
if (val > max) {
  if (val >= beta) return val;
  max = val;
}
  }
   return max;
}
算法3:MPC算法
在算法3中，数组param存贮在每个对弈阶段的参数和检查深度。第一个for循环对若干搜
索深度使用零窗口的 算法进行搜索，直到发生剪枝或在该局面和搜索深度下没有再要进
行的检查搜索为止。在检查部分MPC并不递归地调用自身以避免搜索深度退化（在ProbC
ut中不用担心这一点，因为只会在特定的深度上进行检查）。
参考资料:
Michael Buro. ProbCut: An Effective Selective Extension of the Algorithm
Michael Buro. Experiments with Multi-ProbCut and a New High-Quality Evaluati
on Function for Othello

--

rita850101

这是什么东东,看不懂哦

带眼镜的能猫

：）有偶的名字呢

笑指天南

好象是c语言的精髓啊！！~~
hoho 、``

rita850101

猫猫~~~~~~~

小小背包

看不懂.........

周恒最近好不?????

rita850101

周恒这两天哪里去了

zhouheng1212

在背诵单词呢。


可惜背的不顺利。

zhouheng1212

江南的雨  


  对于江南的雨，我有种说不清道不明的情愫。其中包含着喜爱、厌倦以及由它而引起的欢娱和惆怅。
  对于一个来自多风少雨的华北的人来讲，无疑，这江南的雨带给我的是欣喜和享受。它们仿佛是天地间无数的精灵，欢快地宛如晶莹的天使从天而降，落到地面上轻快地翻几个跟头，接着便调皮地四散逃开、无影无踪了，留下的是那一个个深深浅浅、大大小小的水洼微微荡着细小的涟漪。
  我撑着伞走在雨里，天地间微微氤氲着一层朦胧的雾，宛如清晨湖面上腾起的一层轻薄的水汽。透过这层水雾，我看见粉红色的花，新绿的树和鲜嫩的草，它们被雨细心地拭去身上的纤尘，犹如娇小的妻子被体贴的爱人细致入微的呵护着。我欣赏着江南的雨，细细聆听着“淅淅沥沥”的协奏曲，感受着扑面而来的清新和江南缠绵悱恻的情意。
  雨一直下，似乎超市里永远抛售不完的打折商品，那么廉价。直到道路满是泥泞，鞋子沾满泥巴，长久地没完没了的雨是我感到厌倦。走在雨中，会情不自禁地想起忧伤的往事，不自觉地重温思乡之苦。感觉这雨犹如一根绵长的线，把江南独有的忧郁诗人的气质一直引入你的心间。江南惆怅的雨啊，把人们的心都打湿了，让他们莫名地寒冷，莫名地落寞，莫名地像软弱的泥人一般融化在这无尽氤氲地惆怅里……
  于是，后来的我常常倚窗眺望，并不在于欣赏这水墨般浅灰色的江南雨景，而是想透过这层浅灰望见我等候多时的暖暖的阳光。
  我想，人生大多时候都会像雨中期盼阳光一样满怀希望地期待着什么，遥远的亦或熟稔的。而当它真的被我们盼星星盼月亮盼出来的时候，又出于它过多或主观认为过轻易地满足我们时，就被丢在一边了。好象小孩子觉得自己的玩具永远都不会比邻居小孩那里抢来的好玩一样。而玩了一阵子后，便失去了起初的新鲜和刺激，就被当成废铁堆在角落里了。
  人们往往对身边的幸福视而不见，对现在熟视无睹，从不知道珍惜或不够足够的珍惜，总是沉溺于无法回转的过往或虚无缥缈的未来。正如在雨中厌倦了潮湿而期盼阳光，天晴无几日后又嫌紫外线过强而怀念起下雨时的清凉；酷暑难耐的夏日憧憬冬天的银装素裹，而真正冰天雪地的隆冬来临时又怀念夏日渡假的惬意与悠闲。
  也许，平和的心态对我们更有益处，珍惜现在对我们更加实际。飘雨了，不妨倚窗眺望、雨中漫步；天晴了，不妨拥抱阳光、自由呼吸！

zhouheng1212

秋意. 秋景. 秋情  


送走了夏夜
迎来了秋晨
告别了盛夏的骄阳
带来了那属于秋季的
丝丝凉意

秋天
丝一般的季节
漫天的红叶飞舞
就像转动的舞裙
属于秋仙子的舞裙

秋天
梦一般的季节
瑟瑟的飞絮飘落
就如跳动的彩蝶
陪伴秋仙子的彩蝶

我爱秋
爱这令人充满幻想的季节
悄悄地
随我入梦