1 / 4
文档名称:

高级搜索方法——静态搜索.doc

格式:doc   大小:39KB   页数:4页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

高级搜索方法——静态搜索.doc

上传人:windurst 2022/4/20 文件大小:39 KB

下载得到文件列表

高级搜索方法——静态搜索.doc

相关文档

文档介绍

文档介绍:《对弈程序基本技术》专题
 
静态搜索
 
Bruce Moreland / 文
 
  国际象棋中会有很多强制的应对。如果有人用马吃掉你的象,那么你最好吃还他的马。
  Alpha-Beta搜索不是特别针对这种静态评价。
  然后尝试吃子着法,如果其中任何一个产生截断,搜索就中止。可能它们没有一个是好的,这也没问题。
  这个函数有几个可能的结果:可能评价函数会返回足够高的数值,使得函数通过Beta截断马上返回;也可能某个吃子产生Beta截断;可能静态评价比较坏,而任何吃子着法也不会更好;或者可能任何吃子都不好,但是静态评价只比Alpha高一点点。
  注意这里静态搜索中没有传递“深度”这个参数。正因为如此,如果找到好的吃子,或者有一系列连续的强制性吃子的着法,那么搜索可能会非常深。
  我的示范程序不检测将军,因此它不能找到杀棋。先询问要走的一方是否被将军,这是可以尝试的做法。如果被将军了,就不能用“Evaluate()”来尝试截断,而应该以一层的深度调用Alpha-Beta。例如:
 
int Quies(int alpha, int beta) {
 if (InCheck()) {
  return AlphaBeta(1, alpha, beta);
 }
 val = Evaluate();
 if (val >= beta) {
  return beta;
 }
 if (val > alpha) {
  alpha = val;
 }
 GenerateGoodCaptures();
 while (CapturesLeft()) {
  MakeNextCapture();
  val = -Quies(-beta, -alpha);
  UnmakeMove();
  if (val >= beta) {
   return beta;
  }
  if (val > alpha) {
   alpha = val;
  }
 }
 return alpha;
}
 
  这个版本会找到带有连续吃子的杀棋。至于用哪个版本,取决于个人喜好和测试结果。
  “好的”吃子的界定也是仁者见仁智者见智的。如果你允许任何吃子,并且以任何原始的顺序来搜索,那么你会降低搜索效率,并且导致静态搜索的膨胀,从而大幅度降低搜索深度,并使程序崩溃。
  有一些简单的做法可以避免静态搜索的膨胀。
 
MVV/LVA
 
  MVV/LVA 意思是“最有价值的受害者/最没价值的攻击者”(Most Valuable Victim/Least Valuable Attacker)。这是一个应用上非常简单的着法排序技巧,从而最先搜索最好的吃子着法。这个技术假设最好的吃子是吃到最大的子。如果不止一个棋子能吃到最大的子,那么假设用最小的子去吃是最好的。
  这就意味者PxQ(兵吃后)首先考虑(假设王的将军另外处理)。接下来是NxQ或BxQ,然后是RxQ、QxQ、KxQ。接下来是PxR、B/NxR、RxR、QxR、KxR,等等。
  这个工作总比不做要好,但是很明显有很严重的问题。