《對弈程序基本技術》專題
 
主要變例搜索
 
Bruce Moreland /
 
Alpha-Beta的改進
 
  主要變例搜索(PVS, Principal Variation Search)是提高“Alpha-Beta”算法效率的一種方法。
  在Alpha-Beta搜索中,任何結點都屬于以下三種類型:
  1. Alpha結點。每個搜索都會得到一個小于或等于Alpha的值,這就意味著這里沒有一個著法是好的,可能是因為這個局面對于要走的一方太壞了。
  2. Beta結點。至少一個著法會返回大于或等于Beta的值。
  3. 主要變例(PV)結點。有一個或多個著法會返回大于或等于Alpha的值(PV著法),但是沒有著法會返回大于或等于Beta的值。
  有些時候你可以很早地判斷出你要處理的是哪類結點。如果你搜索的第一個著法高出邊界(返回一個大于或等于Beta的值),那么很明顯你得到Beta結點。如果低出邊界(返回一個小于或等于Alpha的值),假設你的著法順序非常好,那么你有可能得到Alpha結點。如果返回值在AlphaBeta之間,你可能得到PV結點。
  當然,有兩種情況你可能會判斷錯誤。當你高出邊界時,你返回Beta,因此你不會犯錯誤,但是如果第一個著法低出邊界或者是PV著法時,仍然有可能在下一個著法得到更高的值。
  主要變例搜索作了假設,如果你在搜索一個結點時找到一個PV著法,那么你就得到PV結點。也就是說假設你的著法排序已經足夠好了,使得你不必在其余的著法中找更好的PV著法或者高出邊界的著法(這就會使結點變成Beta結點)
  你找到一個著法其值在AlphaBeta之間,那么對其余的著法,搜索的目標就是證明他們都是壞的。跟要搜索出更好的著法相比,這種搜索也許要快一些。
  如果這個算法發現判斷是錯的,即其中一個后續著法比第一個PV著法好,那么它會被再一次搜索,這次使用正常的Alpha-Beta搜索方法。這種情況有時會發生,這樣就浪費時間了,但是這些時間通常不會超過面所說的“證明是壞著法”所節約下來的時間。
  算法如下,是從Alpha-Beta算法改過來的,改過的地方用醒目的字標出:
 
int AlphaBeta(int depth, int alpha, int beta) {
 BOOL fFoundPv = FALSE;
 if (depth == 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  if (fFoundPv) {
   val = -AlphaBeta(depth - 1, -alpha - 1, -alpha);
   if ((val > alpha) && (val < beta)) { // 檢查失敗
    val = -AlphaBeta(depth - 1, -beta, -alpha);
   }
  } else
   val = -AlphaBeta(depth - 1, -beta, -alpha);
  }
  UnmakeMove();
  if (val >= beta) {
   return beta;
  }
  if (val > alpha) {
   alpha = val;
   fFoundPv = TRUE;
  }
 }
 return alpha;
}
 
  算法的核心部分就是函數中間醒目的“if”塊中的內容。如果沒有找到PV結點,“AlphaBeta()”函數就正常調用,如果找到了一個,那么情況就變了。不是用常規的窗口(Alpha, Beta),而是用(Alpha, Alpha + 1)來搜索。這樣做的前提是,搜索必須返回小于或等于Alpha的值,如果確實這樣,那么把窗口的上面部分去掉就會導致更多的截斷。當然,如果前提是錯的,返回值是Alpha + 1或更高,那么搜索必須用寬的窗口重做。
  據報道PVS可以提高10%的效率。我沒有試圖檢測PVS用在我的程序里到底提高了多少,但是確實提高了,所以我用了這個算法。
 
搜索不穩定性的問題
 
  如果你用(Alpha, Alpha + 1)這個窗口去做搜索,返回值超過了窗口(但是沒有超過Beta),你就必須重新搜索。你認為重新搜索的值必定在AlphaBeta之間,但是恐怕不一定是。這很有可能是由“搜索的不穩定性”引起的,我會在別的章節中討論這個問題。
  上面寫的那個程序對這個情況作了防御,并對這種情況的發生作了正確的處理。如果你要使用這個程序并且作一些改動,就要特別當心你的搜索是否總是穩定的。如果你得到不期望得到的返回值,就必須采取措施避免讓程序陷入故障。
 
  原文:http://www.seanet.com/~brucemo/topics/pvs.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 高級搜索方法——期望窗口
  • 下一篇 高級搜索方法——搜索的不穩定性
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果