《棋战顺序基本手艺》专题
 
静态搜索
 
Bruce Moreland /
 
  国际象棋中会有许多自愿的敷衍。若是一些人用马吃掉你的象,那末你最好吃还他的马。
  Alpha-Beta搜索不是稀奇重点一定这类状况的。你把深度参数通报给函数,当深度抵达零就做完了,纵然一方的后被捉。
  一个敷衍的要领称为“静态搜索”(Quiescent Search)。当Alpha-Beta用尽深度后,经由历程调用静态搜索来替代调用“Evaluate()”。这个函数也对局势作评定,只是制止了在显著有对策的状况下看错形势。
  简而言之,静态搜索就是敷衍能够的静态局势的搜索。
  模范的静态搜索只搜索吃子着法。这会引发一个问题,由于在国际象棋中吃子一般不是自愿的。若是形势很镇静,而且你面临的吃子只需QxP(后吃兵,致使丢后),你不会自愿后去吃兵的,以是静态搜索不应当自愿吃子。
  因而,走子一方能够选择是吃子照样不吃子。这就例如打扑克牌时能够只用手中的牌而不去抓牌【译注:术语“Standing Pat”】
  代码以下:
 
int Quies(int alpha, int 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;
}
 
  这看上去和“Alpha-Beta”异常相似,然则区分是很显著的。这个函数调用静态评定,若是评定好得足以截断而不要求试图吃子时,就立时截断(前往Beta)。若是评定缺乏以发生截断,然则比Alpha好,那末就更新Alpha来回响反映静态评定。
  然后实验吃子着法,若是其中任何一个发生截断,搜索就中缀。能够它们没有一个是好的,这也没问题。
  这个函数有几个能够的效果:能够评定函数会前往足够高的数值,使得函数经由历程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(兵吃后)首先斟酌(假定王的将军其余处置责罚)。接上去是NxQBxQ,然后是RxQQxQKxQ。接上去是PxRB/NxRRxRQxRKxR,等等。
  这个事情总比不做要好,然则很显著有很严重的问题。纵然车被珍爱着,RxR依旧排在PxB的前面。
  MVV/LVA 能够处置责罚静态搜索收缩的问题,然则它依然留给你对照重大的静态搜索树。
  MVV/LVA 的优势在于它完成起来异常轻易,而且能够到达很高的NPS(每秒搜索的结点数)。它的瑕玷是搜索效能低——你花少量的时刻来评价亏损的吃子,以是你的搜索不会很深。
 
SEE
 
  SEE 意义是“静态交流评定”(Static Exchange Evaluation)。它比 MVV/LVA 更庞大,然则着法排序更准确,从而许多吃子都没需要斟酌。
  在 MVV/LVA 中你没有设施去掉QxP的着法,由于很能够兵是没珍爱的,这就意味着QxP是好的着法。固然,若是兵是珍爱的,我不置信你还能在搜索这步时有甚么好的发现。用了 SEE 后,若是QxP是亏损的着法,你就能够够把它挑出来,然后在吃子的递次里把它排在最终,或简朴地把它裁剪掉。
  现在我还没有 SEE 的树模代码,你能够设想一个处置责罚吃子的历程,然后依据它看上去能失掉的价值停止排序。【当斟酌吃子着法时,要求斟酌能吃到的该子的一切进击子,也要珍爱该子的一切戍守子,因而处置责罚吃子的历程是相等庞大的。】
  SEE 能使你异常有用地裁剪掉坏的着法,许多主要的吃子不会被毛病地裁剪,而且能革新着法的递次。你能做的其余一件事是,若是着法看起来还不算充裕好,那末你能够裁剪掉这些好的着法。若是你抢先一个车,那末得一个兵的吃子也许不值得在静态搜索中实验。
  我很疑心用 SEE 的顺序能比一样的但用了 MVV/LVA 的顺序强。问题在于代码的编写上,要求异常不错地设想数据组织,才气让 SEE 变得有用。
 
静态搜索不是完善的
 
  静态搜索极有能够会出毛病。这是一个不幸的现实,然则它更多地在搜索看上去异常愚昧(譬喻一层的搜索,它基础不会长短常好的)的状况下会出毛病,因而这不是一个严重的问题。
  若是能够用更准确的静态搜索而不下降速率,那末我一定这个顺序会比之前更强。然则咱们必需晓畅的是,你在消耗时刻的条件下试图让静态搜索更准确,要求找到平衡点。若是为了让静态搜索更智慧,你破费了几层完整搜索的时刻,那末这就不值得让它更聪清楚明晰。
 
  原文:http://www.seanet.com/~brucemo/topics/quiescent.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 低级搜索要领——简介()
  • 下一篇 低级搜索要领——空着裁剪
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com