《棋战顺序基本手艺》专题
 
Alpha-Beta搜索
 
David Eppstein */
* 加州爱尔文大学(UC Irvine)信息与盘算机迷信系
 
浅的裁剪
 
  假定你用最小-最大搜索(前面讲到的)来搜索下面的树:
 
 
  你搜索到F,发现子结点的评定离别是111279,在这层是棋手甲走,咱们希冀他选择最好的值,即12。以是,F的最小-最大值是12
  现在你最先搜索G,而且第一个子结点就前往15。一旦这样,你就知道G的值最少是15,能够更高(若是其余一个子结点比G更好)。这就意味着咱们不希冀棋手乙走G这步了,由于就棋手乙看来,F的评定12要比G15(或更高)好,因而咱们知道G不在主要变例上。咱们能够裁剪(Prune)结点G下面的其他子结点,而不要对它们作出评定,而且马上从G前往,由于对G作更好的评定只是虚耗时刻。
  一样寻常来说,像G一样只需有一个子结点前往比G的兄弟结点更好的值(关于结点G要走棋的一方而言),就能够够停止裁剪。
 
深的裁剪
 
  咱们来议论更庞大的能够裁剪的状况。譬喻在统一棵搜索树中,咱们评定的GHI都比12好,因而12就是结点B的评定。现在咱们来搜索结点C,不才面两层咱们找到了评定为10的结点N
 
 
  咱们能用越发庞大的线路来作裁剪。咱们知道N会前往10或更小(轮到棋手乙走棋,要求挑最小的)。咱们不知道J是否能前往10或更小,也不知道J的哪一个子结点会更好。若是从J前往到C的是10也许更小的值,那末咱们能够在结点C上作裁剪,由于它有更好的兄弟结点B。因而在这类状况下,连续找N的子结点就毫有意义。斟酌其他状况,J的其他子结点前往比10更好的值,这时候搜索N也是毫有意义的。以是咱们只需发现10,就能够够宁神地从N前往。
 
Alpha-Beta的伪代码
 
  一样寻常来说,若是前往值比偶数层的兄弟结点好,咱们就能够够马上前往。若是咱们在搜索历程当中,把这些兄弟结点的最小值Beta作为参数来通报,咱们就能够够停止异常有用的裁剪。咱们还用其余一个参数Alpha来生存奇数层的结点。用这两个参数来停止裁剪长短常有用的,代码就写不才边。像上次一样,咱们用负值最大(Negamax)的形式,即搜索树的层数改动时取负值。
 
double alphabeta(int depth, double alpha, double beta) {
 if (depth <= 0 || 棋局完毕) {
  return evaluation();
 }
 就以后局势,天生并排序一系列着法;
 for (每一个着法 m) {
  执行着法 m;
  double val = -alphabeta(depth - 1, -beta, -alpha);
  吊销着法 m;
  if (val >= beta) {
   return val;
  }
  if (val > alpha) {
   alpha = val;
  }
 }
 return alpha;
}
 
  下次咱们会注释为甚么排序这一步是很主要的。
 
希冀搜索
 
  在根结点上咱们怎样为AlphaBeta设定初值?
  AlphaBeta界说了一个评定的实数区间(Alpha, Beta),这个区间是咱们“感兴味的”。若是某值比Beta大咱们就会做裁剪并马上前往,由于咱们知道它不是主要变例的一局部,咱们对它的准确值不感兴味,只要求知道它比Beta大。若是某值比Alpha小,咱们不作裁剪,然则依然对它不感兴味,由于咱们知道搜索树里一定有一个着法会更好。
  然则在搜索树的根结点,咱们不知道感兴味的评定是在哪一个局限内,若是咱们要确保不会由于意外而裁剪掉主要的局部,咱们就设Alpha = -InfinityBeta = Infinity(无限大)
  然则,若是咱们运用迭代加深,就能够够有设施知道主要变例是怎样的。假定咱们猜其值为x(譬喻x就是前一次搜索到D -1深度时的值),并设Epsilon为一个很小的值,它象征从D -1深度到D深度搜索评定的希冀转变局限。咱们能够实验调用alphabeta(D, x - Epsilon, x + Epsilon),那末能够发作三种状况:
  (1) 搜索的前往值会落在区间(x - Epsilon, x + Epsilon)内。这类状况下,咱们知道它前往的是准确止墁咱们就能够宁神地选择这个着法,在搜索树中这个着法指向具有前往值的谁人结点。
  (2) 搜索会前往一个值v > x + Epsilon。这类状况下,咱们知道搜索效果也最少是 x + Epsilon,然则咱们不知道它究竟是几(准确的主要变例能够被裁剪掉了,由于咱们发现有其余着法的值大于Beta)。咱们必需把咱们所猜的值x调整得更高,然后再试一次(能够还要用更大的Epsilon)。这类状况称为“凌驾界限”(Fail High)
  (3) 搜索会前往一个值v < x - Epsilon。这类状况下,咱们知道搜索效果也最多是 x + Epsilon,然则咱们不知道它究竟是几。咱们必需把咱们所猜的值x调整得更低,然后再试一次(能够还要用更大的Epsilon)。这类状况称为“低出界限”(Fail Low)
  纵使有两种能够失利的状况,运用希冀搜索(用一个比(-Infinity, Infinity)更小的区间(Alpha, Beta))整体来说效能会有所提升,由于它作了更多的裁剪。
 
剖析
 
  让咱们对Alpha-Beta搜索作一下剖析,来知道它为甚么是个很有用的算法。跟一般的算法分歧,咱们使用“Beta状况的剖析”,即假定任何能够的状况下都邑发作Alpha-Beta裁剪。下一次咱们会知道怎样让Alpha-Beta搜索靠近咱们的所剖析的状况。在这里我只斟酌浅的裁剪,由于它会让剖析变得越发简朴。
  在最好的状况下,除了主要变例上的结点不会裁剪外(若是这个结点也被裁剪了,那末悉数算法会凌驾界限或低出界限,这固然不是最好的状况),在裁剪前,深D -1层的每一个结点只会搜索一个深D层的子结点。
  然则在深D -2层时,谁也没有被裁剪,由于一切的子结点都前往大于或即是Beta的值,而D -2层是要取正数,因而它们都小于或即是Alpha
  连续朝树根走,D -3层的每一个结点(除了主要变破例)都被裁剪,而D -4层谁也没被裁剪,等等。
  因而,若是搜索树的分枝因子是B,那末在搜索树一半的深度上,结点以因子B作增长,而在其余一半的深度上则连结稳定(咱们疏忽了主要变例)。以是这个搜索树一切要搜索的结点数,大略地写成BD/2 = sqrt(B)D。因而Alpha-Beta搜索一直能够将分枝因子增加为正本的平方根那末多,因而它可以让咱们搜索正本两倍的深度。正由于这个缘由,它是一切基于最小-最大战略的棋类棋战顺序的最主要的算法。
  【译注:原作者一最先说到的“浅的裁剪”和“深的裁剪”这两个观点,现实上包罗了Alpha-Beta搜索的两个条理,前者只是用过通报参数Beta对搜索树作了局部裁剪,能够称为Beta搜索,然后者增长一个通报参数Alpha,使得裁剪越发充裕,这就组成了Alpha-Beta搜索。
  Beta搜索的伪代码是:
 
double alphabeta(int depth, double beta) {
 if (depth <= 0 || 棋局完毕) {
  return evaluation();
 }
 就以后局势,天生并排序一系列着法;
 double alpha = -infty;
 for (每一个着法 m) {
  执行着法 m;
  double val = -alphabeta(depth - 1, -alpha);
  吊销着法 m;
  if (val >= beta) {
   return val;
  }
  if (val > alpha) {
   alpha = val;
  }
 }
 return alpha;
}
 
对红色局部加一些革新,就酿成Alpha-Beta搜索的伪代码了。】
 
  原文:http://www.ics.uci.edu/~eppstein/180a/970422.html
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 基本搜索要领——简介()
  • 下一篇 基本搜索要领——简介()
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com