《棋战顺序基本手艺》专题
 
Alpha-Beta搜索的诸多变种
 
David Eppstein */
* 加州爱尔文大学(UC Irvine)信息与盘算机迷信系
 
  只管咱们以前议论过Alpha-Beta搜索简朴有用,照样有许多要领试图更有用地对博弈树停止搜索。它们中的大局部头脑就是,若是以为介于AlphaBeta间的评定是感兴味的,而其他评建都是不感兴味的,那末对不感兴味的评定作截断会让Alpha-Beta更有用。若是咱们把AlphaBeta的间距增加,那末感兴味的评定会更少,截断会更多。
  首先让咱们回忆一下原始的Alpha-Beta搜索,疏忽散列表和“用以后层数调整胜利值”的细节。
 
// 基本的Alpha-Beta搜索
int alphabeta(int depth, int alpha, int beta) {
 move bestmove;
 if (棋局完毕 || depth <= 0) {
  return eval();
 }
 for (每一个恰当着法 m) {
  执行着法 m;
  score = -alphabeta(depth - 1, -beta, -alpha);
  if (score >= alpha) {
   alpha = score;
   bestmove = m;
  }
  吊销着法 m;
  if (alpha >= beta) {
   break;
  }
 }
 return alpha;
}
 
超越界限(Fail-Soft)Alpha-Beta
 
  上述代码总是前往AlphaBeta或在AlphaBeta之间的数。换句话说,当某个值不感兴味时,早年往值没有设施失掉任何信息。缘由就是以后值被变量Alpha所生存,它从感兴味的值的窗口下沿最先一直增长的,没有能够前往比Alpha更小的值。一个对Alpha-Beta的简朴革新就是把以后评定和Alpha离开生存。下面的伪代码用常数“WIN”透露表现最大评定,它能够在Alpha-Beta搜索中前往任何评定。
 
// 超越界限的Alpha-Beta搜索
int alphabeta(int depth, int alpha, int beta) {
 move bestmove;
 int current = -WIN;
 if (棋局完毕 || depth <= 0) {
  return eval();
 }
 for (每一个能够的着法 m) {
  执行着法 m;
  score = -alphabeta(depth - 1, -beta, -alpha);
  吊销着法 m;
  if (score >= current) {
   current = score;
   bestmove = m;
   if (score >= alpha) {
    alpha = score;
   }
   if (score >= beta) {
    break; // 【译注:这里能够直接前往score、current或alpha,若是前往beta,则是不会凌驾界限的Alpha-Beta搜索。】
   }
  }
 }
 return current;
}
 
  这样改动以后,就能够够知道比之前稍多一点的信息。若是前往值x即是或小于Alpha,咱们依然不知道局势的实在值(由于咱们能够在搜索中裁剪了一些线路),然则咱们知道实在值最多是x。相似地,若是x大于或即是Beta,咱们就知道搜索值最少是x。这些细小的上界和下界转变不会滋扰搜索自身,然则它们能致使散列表掷中率的提升。超越界限的Alpha-Beta搜索对下面要引见的MTD(f)算法有主要功用。
 
希冀搜索
 
  这个要领不是替代Alpha-Beta的,只是从外部改边一个门路来调用搜索历程。一般用Alpha-Beta找最好线路时,能够调用:
 
alphabeta(depth, -WIN, WIN)
 
  这里 -WIN WIN 之间的局限很大,注解咱们不知道搜索值是若干,因而任何能够的值都必需斟酌。随后,要走的那步生存在搜索函数外部的变量中。
  希冀搜索的分歧的中央在于,咱们能够人为地指定一个狭窄窗口(用前一个搜索值为中央),对搜索一般是有资助的。若是你搜索失利,必需加宽窗口重新搜索:
 
// 希冀搜索
int alpha = previous - WINDOW;
int beta = previous + WINDOW;
for ( ; ; ) {
 score = alphabeta(depth, alpha, beta);
 if (score <= alpha) {
  alpha = -WIN;
 } else if (score >= beta) {
  beta = WIN;
 } else {
  break;
 }
}
 
  权衡狭窄搜索所勤俭的时刻,和由于失利而重新搜索的时刻,能够注定常数 WINDOW 的巨细。在国际象棋中,模范的值多是半个兵。希冀搜索的变体有,搜索失利时适当增长窗口宽度,也许用初始窗口而没需要之前一次搜索效果为中央,等等。
 
MTD(f)
 
  这个手艺跟希冀搜索一样,只是在调用Alpha-Beta时对初始值停止调整。搜索窗口越窄搜索就越快,这个手艺的头脑就是让搜索窗口尽能够的窄:一直用“beta = alpha + 1”来调用Alpha-Beta。用这样一个“零宽度”搜索的功用是用Alpha和实在值作对照:若是搜索的前往值最多是Alpha,那末实在值自身最多是Alpha,相反实在值大于Alpha
  咱们能够用这个头脑对实在值作二分搜索:
 
int alpha = -WIN;
int beta = +WIN;
while (beta > alpha + 1) {
 int test = (alpha + beta) / 2;
 if (alphabeta(depth, test, test + 1) <= test) {
  beta = test;
 } else {
  alpha = test + 1;
 }
}
 
  然则,这样会致使大局限的搜索(WIN -WIN 的差的对数)。而MTD(f)的头脑则是用超越界限的Alpha-Beta对搜索停止掌握T媚课调用超越界限的Alpha-Beta就会前往一个值更靠近于一直值,若是用这个搜索值作为下次测试的最先,咱们一直会到达收敛。
 
// MTD(f)
int test = 0;
for ( ; ; ) {
 score = alphabeta(depth, test, test + 1);
 if (test == score) {
  break;
 }
 test = score;
}
 
  不幸的是,它和散列表之间的庞大功用会致使这个历程堕入有限循环,以是必需加上分外的代码,若是迭代次数太多而没有收敛,就必需中缀搜索。
  MTD(f)的一个大的优势在于咱们能够简化Alpha-Beta搜索,由于它只要求两个参数(深度和Alpha)而不是三个。【听说这样做能够提升并行盘算的效能,没有设施的是译者对并行盘算一无所知。】
  【为了对MTD(f)有更详细的相识,译者查阅了该算法的发现者Plaat的网站,他供应的MTD(f)代码中用了两个界限,能够预防迭代历程当中显现振荡而不收敛的状况,代码以下(正本是Pascal言语,现被译者转写为C言语)
 
int MTDF(int test, int depth) {
 int score, beta, upperbound, lowerbound;
 score = test;
 upperbound = +INFINITY;
 lowerbound = -INFINITY;
 do {
  beta = (score == lowerbound ? score + 1 : score);
  score = alphabeta(depth, beta - 1, beta);
  (score < beta ? upperbound : lowerbound) = score;
 } while (lowerbound < upperbound);
 return score;
}
 
  而关于MTD(f)的运用尚有以下几点窍门:
  (1) 一般探索值并纷歧定设成零,而是用迭代加深的形式由浅一层的MTD(f)搜索给出;
  (2) 局势评定得越粗拙,MTD(f)的效能越高,譬喻国际象棋中可以使一个兵的价值由100下降为10,其他子力也响应比重下降,以提升MTD(f)的效能(但粗拙的局势评定函数却晦气于迭代加深启示,因而要求追求一个平衡点)
  (3) 零宽度窗口的搜索要求置换表的有力支持,因而称为“用存储器增强的探索驱动器”(Memory-enhanced Test Driver,即MTD),它只要求通报两个参数(深度n和探索值f),故得名为MTD(n,f),缩写为MTD(f)。】
 
PVS
 
  也许最好的Alpha-Beta变体,要算是这些称呼了:负值侦探(NegaScout)和主要变例搜索(Principal Variation Search,简称PVS)。这个头脑就是当第一次迭代搜索时找到最好的值,那末Alpha-Beta搜索的效能最高。对着法列表停止排序,也许把最好的着法生存到散列表中,这些手艺能够让第一个着法成为最好着法。若是真是这样,咱们就能够够假定其他着法不多是好的着法,从而对它们快速地搜索已往。
  因而PVS对第一个搜索运用一样寻常的窗口,然后续搜索运用零宽度的窗口,来对每一个后续着法和第一个着法作对照。只需当零窗口搜索失利后才去做一样寻常的搜索。
 
// 主要变例搜索(超越界限的版本)
int alphabeta(int depth, int alpha, int beta) {
 move bestmove, current;
 if (棋局完毕 || depth <= 0) {
  return eval();
 }
 move m = 第一个着法;
 执行着法 m;
 current = -alphabeta(depth - 1, -beta, -alpha);
 吊销着法 m;
 for (剩余的每一个着法 m) {
  执行着法 m;
  score = -alphabeta(depth - 1, -alpha - 1, -alpha);
  if (score > alpha && score < beta) {
   score = -alphabeta(depth - 1, -beta, -alpha);
  }
  吊销着法 m;
  if (score >= current) {
   current = score;
   bestmove = m;
   if (score >= alpha) {
    alpha = score;
   }
   if (score >= beta) {
    break;
   }
  }
 }
 return current;
}
 
  这个算法跟MTD(f)有个异样的优势,即搜索树的大少数结点都以零宽度的窗口搜索,能够用双参数的Alpha-Beta。由于“Beta > Alpha + 1”的调用异常少,因而没需要忧郁分外的事情(譬喻生存最好着法以供未来运用)会占用许多时刻。【原作者的意义是,调用零宽度窗口的搜索时,能够此制止去生存最好着法等支配,因而能够省下很多时刻。】
 
引荐
 
  我自身的顺序联系了希冀搜索(用在悉数搜索历程之外)PVS(用在搜索历程外部)。然则分歧的棋类游戏纷歧样,由于这些搜索很容易完成,以是要在这些要领中停止选择或调治参数,就必需对它们逐一完成并做一些调研。它们都必需前往异样的搜索值(若是受散列表滋扰,那末最少是相近的值【譬喻通例的Alpha-Beta搜索和超越界限的Alpha-Beta搜索,在运用散列表时能够会前往分歧的值】),但搜索的结点数会分歧。在你的棋类的模范局势中,能使搜索树最小的要领则被采用。
 
  原文:http://www.ics.uci.edu/~eppstein/180a/990202b.html
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 低级搜索要领——简介()
  • 下一篇 低级搜索要领——静态搜索
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com