《對弈程序基本技術》專題
 
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
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 基本搜索方法——簡介()
  • 下一篇 基本搜索方法——簡介()
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果