《对弈程序基本技术》专题
 
什么样的结点需要搜索?全部还是选择性的?
 
David Eppstein */
* 加州爱尔文大学(UC Irvine)信息与计算机科学系
 
  Alpha-Beta告诉我们怎样搜索,但是我们仍然需要知道,何时需要展开结点(搜索它的子结点),以及何时停下来从而调用评价函数。
 
水平线效应
 
  在前面我给你们看的伪代码中,每一步棋都搜索到一个固定的深度,这个深度被称为“水平线”(Horizon)。对于看到水平线以内会发生的威胁,这个方法非常有效,但是它显然不能检查到水平线以后的威胁。例如在8层的搜索中(即搜索4个回合),就可能得不到在5步内有杀棋的任何信息。它不知道的事情,就无法作出防御,而且只是简单地忽略那些遥远的威胁。然而当局势面临中等深度的威胁而丢子不可避免时,固定深度的搜索有时会走出更糟的棋,因为某些丢子会在搜索水平线以内,而有些却不在。在这种情况下,程序会走出糟糕的并且无意义的棋,试图来延缓丢子的发生,使得它出现在程序看不到的未来。这种现象称为“水平线效应”(Horizon Effect)
  这里有个例子。在下面的局势中,黑象被白兵包围,不管黑的怎么走,象总是会在几步内被吃掉;例如白车可以沿着h2-h1-a1-a2吃掉象。这是一个8层深的变化,那么假设黑方的程序也搜索8层。可能当前局面对黑方来说,最好的走法就是用象换兵,即象吃掉兵,兵吃掉象。在后面的残局里,黑方的三个连兵足以战胜或守和白车。【译注:其实守和的希望也不大,译者认为黑方还是会输掉的,因为白王的位置非常好,可以独挡三黑兵,使得白车有时间拔掉b线的黑兵。】但是程序搜索8层,很有可能会挺黑兵将军白王。白必须应对(例如自己来吃掉兵),这个应对使得丢象被暂时避免,拖延到程序看不到的步数内,并且程序认为象是安全的。实际上在这个局面里,固定深度的程序可能会连续地送吃兵,把象被吃的结果延缓几步,但是最终可能输掉整盘棋。
 
 
  对付水平线效应的一个方法,就是在你的程序里增加一些知识:如果从评价中知道象被包围,那么搜索程序就不会通过弃兵来延缓丢象。另一个方法是让搜索更快更深:你的程序搜索的层数越多,因超过水平线而延缓丢象的做法,发生的可能性就越小。但是对于普通局面来说,最有效的做法就是让搜索深度更灵活,使得程序在丢兵的路线上搜索得更深,而在其它路线上不必要搜索得很深。
 
蛮力和选择性
 
  在Shannon【申朗,参阅译文《电脑国际bck体育官网手机版简史》】最早关于电脑国际bck体育官网手机版的文章中,提到程序调整搜索深度的两种策略。
  最明显的就是我给你们看的伪代码:全部范围,固定深度的蛮力搜索。只要把“深度”这个参数输入到你的程序中,每搜索一层就减一,到达零时停下来。这样做的好处在于,只要在搜索水平线以内,一些甚至很怪异的线路也看得到。但是高的分枝因子就意味着任何线路都不可能很深(即学士程度,对任何事物都只知道个皮毛【原文是“Bachelor's degree: knows nothing about everything”】)。更遭的是,程序可能会栽倒在水平线效应下。
  Shannon提到的另外一个方法就是选择性裁剪:不是搜索固定的深度,而是通过搜索每个结点的部分着法来减少分枝因子(避免那些“明显是坏棋”的着法)。因此这样可以搜索得很深,但是有些线路完全看不见(即博士程度,只对某个狭窄方面的懂得很多【原文是“Ph.D.: knows everything about nothing”,源于一句用来讽刺博士的笑话:“A PhD knows more and more about less and less until he knows everything about nothing”】)Shannon认为这个思想非常好,因为它更接近人类的思考方式。Turing【图灵,参阅译文《电脑国际bck体育官网手机版简史》】的思想有所不同,只搜索吃子的着法。更典型的做法是,对所有的子结点作评价,而只对最好的k个作展开,这里k是小于实际分枝因子的一个参数。
  不幸的是,“明显是坏棋”的着法往往根本不坏,而是取得胜利的精彩弃子。如果你没有找到你应该走的那步着法,你就必须更努力地去找其他可以获胜的方法。更糟的是,对手可能会在后面几步作出有力的反击,如果你没有看出来,那么你会掉入陷阱从而输掉棋局。
  如今没有哪个思想会被单纯地使用的。我们把两者结合起来:选择性地延伸。每条路线都搜索固定的深度,但是某些路线要搜索得比水平线深。有时我们也会做裁剪(不是像Alpha-Beta那样的安全裁剪),这通常也是非常保守的,因为只挑出好的着法实在太困难了,但是有时对于确实很坏的着法,我们可以挑出并且忽略它们。除了国际bck体育官网手机版以外,有些棋类有更高的分枝因子,这就有必要使用更冒进的裁剪技术了。【例如五子棋,每个局面都有100种以上的合理着法,但是我们只会挑有意义的着法,要么有进攻作用(己方棋子周围的一些着点),要么有防守作用(敌方棋子邻近的着点),除此以外一概不予考虑。】
 
什么时候需要延伸?
 
  延伸的目标是什么呢?是获得更好(更准确)的评价。所以下面的结点必须延伸:
  (1) 目前的评价可能不准确时;
  (2) 目前的着棋路线在整个博弈搜索树中是非常重要的;
  或者以上两个情况的组合。
 
静态搜索
 
  在国际bck体育官网手机版或其他棋类中,有吃子和不吃子的着法(西洋跳棋、围棋、Fanorano),如果有吃子的情况,那么每次吃子时评价都会改变。
  “静态搜索”(Quiescence Search)的思想是,到达主搜索的水平线后,用一个图灵型的搜索只展开吃子(有时是吃子加将军)的着法。其他棋类不同于国际bck体育官网手机版,可能只包括一些会很大程度上改变评价的着法。静态搜索还必须包括放弃的着法,来决定停止吃子。因此,主Alpha-Beta搜索中每个调用评价函数的地方,都会被一个类似Alpha-Beta的但只搜索吃子着法的函数代替,如果当前结点的评价函数足以高出边界,那么就让搜索停下来。代码如下:
 
// 静态搜索
// 主Alpha-Beta搜索中,原来出现“eval()”的地方现在调用这个函数
quiesce(int alpha, int beta) {
 int score = eval();
 if (score >= beta) {
  return score;
 }
 for (每个吃子着法 m) {
  执行着法 m;
  score = -quiesce(-beta,-alpha);
  撤消着法 m;
  if (score >= alpha) {
   alpha = score;
   if (score >= beta) {
    break;
   }
  }
 }
 return score;
}
 
  有人还把将军加入到静态搜索中,但是你要当心,由于没有深度参数,静态搜索会有巨大的结点数。吃子通常是有限的(在棋子全部吃完以前你只能有16次子),而将军可以一直进行下去并导致无限制递归。【对于是否展开将军着法的问题,可以尝试一种做法,如果局面被将军,就展开全部着法,即做应将处理,而不对当前局面作评价,参阅“静态搜索”一文。】
 
选择性延伸
 
  如果局面在前面的路线中非常活跃,那么这就证明后面会有进一步的手段,或者前面的着法使得这些手段推迟了,从而在很深的地方会有好的局面。因此如果搜索到一个“感兴趣”的着法例如吃子或将军,就要增加搜索深度。在Alpha-Beta的伪代码中,调用搜索过程时参数“depth - 1”可以用“depth - 1 + extension”来代替。你必须小心不要经常做这些事,否则最终会把搜索树延伸得特别庞大(甚至可能无限大)
  有一个技巧可以使这样的延伸终止,即延伸一个分数的层数。比较好的做法是,“深度”参数记录的是你想要搜索的层数乘上一个因子,比如说“深度 = 层数 x 24”。在递归调用Alpha-Beta搜索的时候,就传递参数“Depth - 24 + Extension”。如果延伸值总是小于24,那么这个方法能保证终止,这个方法还可以有选择地多延伸些或少延伸些。
  在评价函数里加上“局面如何难以评价”这个知识,也是有用的,这样就可以在局面太难评价的时候延伸搜索。我的程序就做到了这点,程序对当前结点调用评价函数。如果局面十分复杂,而且深度接近零,那么评价会返回一个特殊的值【表示评价失败,这个值不能在“-Infinity”和“Infinity”之间,否则会和正常值混淆】,通知搜索继续进行下去。如果深度达到一个负得很大的数【原作者的意思是评价连续失败导致延很长】,那么评价函数总是成功的,这样搜索将会终止。
 
如何把准确性和重要性结合起来?
 
  到目前为止,我们都在讨论并试图找到评价局面可能不准确的原因。但是对于搜索树的一些不重要的部分,或许我们不在乎它不准确,而我们真正关心的是主要变例上的结点。我们如何来关注选择性延伸的重要性呢?
  (1) Alpha-Beta搜索时,不要只根据准确性作延伸,而忽视了重要性;
  (2) 对主要变例部分(或附近)的线路作延伸,例如单步延伸(Singular Extension),深蓝(Deep Blue)及其前身就用这个方法,如果一个局面的某个着法远比其他着法好,就延伸这个着法。
  (3) 把视线从Alpha-Beta上移开。有一个称为“对策数搜索”(Conspiracy Number Search)的策略,即某些局面会使得能应对的好的着法很少【根据原文,译者也无法了解这个策略的确切含义】,这些局面要搜索得深一些。
  【选择性延伸通常运用在强制着法上,强制着法的界定在各个程序中有所不同,但主要有以下几种判断方法:
  (1) 将军:此时必须应将,显然属于强制着法;
  (2) 单一应着:走子的一方只有一种合理着法时,显然属于强制着法;
  (3) 杀棋威胁:当一方不走子时就会被对方在几步内杀掉,那么解除杀棋威胁也属于强制着法,这种判断比较困难,通常利用下面所介绍的“空着搜索”来做判断。
  (4) 吃回被吃棋子:这很有可能是兑子过程,因此大多数情况下为强制着法;
  (5) 通路兵挺进:在王兵残局中,最简单的处理就是搜索到兵升变时的局面,从而绕开正方型法则、关键格理论等知识,这就需要对通路兵的挺进作延伸。(如果兵挺5格才能到达升变格,那么原来搜索8层还看不到升变,作了延伸以后搜索5层就能看到了,因为在连续挺兵的这条线路上已经延伸到了10层。)
  大多数程序都结合以上若干种判断,以决定是否进行延伸。】
 
空着搜索
 
  这个思想符合本文的整个主题,即在适当时机调整搜索层数,但是它是通过相反的方式来表现的。这个思想不是在复杂的局面上延伸,而是在简单的局面上减少搜索。
  这个思想是建立在国际bck体育官网手机版知识的基础上的:有害的着子是非常罕见的(除了残局以外)。通常如果轮到你走,你一定能让局面更好些。所有可能的着法都使局面变得更糟,这样的局面称为“无等着”(Zugzwang)(德语,意思为强迫着子),通常只发生在残局中。像其他棋类,例如五子棋,无等着根本不会发生。因此,如果你改变国际bck体育官网手机版的规则,允许有“弃权”的着法,那么弃权通常是错误的,它不会使棋局有进展。
  因此,假设你搜索一个希望高出边界的结点(Alpha-Beta搜索的返回值至少是Beta),空着搜索就是先搜索“弃权”着法【即“空着”(Null-Move),即使它通常不是最好的。如果弃权着法高出边界,那么真正最好的着法也可能高出边界,你就可以直接返回Beta而不要再去搜索了。要把搜索做得更快,弃权着法搜索的深度通常比常规着法浅。
  你必须小心,这种启发会改变搜索结果,也可能使你忽略棋局中的一些重要的线路。不要连续两次用空着(因为这样你的搜索会退化,结果只返回评价函数),而且要小心,只能在不会出现无等着的情况下使用。在国际bck体育官网手机版中,这就意味着当局面还有很多子的时候才能使用。
 
// 带空着启发的Alpha-Beta搜索
alphabeta(int depth, int alpha, int beta) {
 if (赢棋 || depth <= 0) {
  return score;
 }
 放弃着子;
 if (上一步不是空着 && 局面不是无等着局面 &&
   alphabeta(depth - 3, beta, beta + 1) >= beta) {
  // 【深度参数如果是 depth - 1,那就是纯粹的“启发”算法,而现在搜索浅了(depth - 3),因此称为“空着裁剪”更为恰当。】
  return beta;
 }
 /* 【“放弃着子”蕴涵着交换着子方的操作,空着启发做完后还必须交换回来。这样,上面用醒目颜色标出的代码(是由译者标出的)就存在一些问题,应该改为:
 
 if (上一步不是空着 && 局面不是无等着局面) {
  放弃着子;
  int val = alphabeta(depth - 3, beta, beta + 1);
  撤消放弃着子; // 如果只作简单处理,放弃着子和撤消放弃着子都只交换着子方。
  if (val >= beta) {
   return beta;
  }
 }
*/
 for (每个可能的着法 m) {
  执行着法 m;
  alpha = max(alpha, -alphabeta(depth - 1, -beta, -alpha);
  撤消着法 m;
  if (alpha >= beta) {
   break;
  }
 }
 return alpha;
}
 
  原文:http://www.ics.uci.edu/~eppstein/180a/990204.html
  译者:bck体育官网手机版百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 基本搜索方法——置换表
  • 下一篇 高级搜索方法——简介()
  • 返 回 bck体育官网手机版百科全书——电脑bck体育官网手机版
  • www.xqbase.com