《對弈程序基本技術》專題
 
最小-最大搜索
 
Bruce Moreland /
 
從淺顯的地方開始
 
  在國際象棋里,雙方棋手都知道每個棋子在哪里,他們輪流走并且可以走任何合理的著法。下棋的目的就是將死對方,或者避免被將死,或者有時爭取和棋是最好的選擇。
  國際象棋程序通過使用“搜索”函數來尋找著法。搜索函數獲得棋局信息,然后尋找對于程序一方來說最好的著法。
  一個淺顯的搜索函數用“樹狀搜索”(Tree-Searching)來實現。一個國際象棋棋局通常可以看作一個很大的n叉樹(n叉樹”意思是樹的每個結點有任意多個分枝通向其他結點),棋盤上目前的局面就是“根局面”(Root Position)或“根結點”(Root Node)。從根局面走一步棋,局面就到達根局面的“分枝”(Branch),這些局面稱為“后續局面”(Successor Position)或“后續結點”(Successor Nodes)。每個后續局面后面還有一系列分枝,每個分枝就是這個局面的一個合理的著法。
  國際象棋的樹非常龐大(通常每個局面有35個分枝),又非常深。
  每盤棋局都是一棵巨大的n叉樹,如果能通過樹狀搜索找到棋局中對雙方來說都最好的著法就好了。這個淺顯的算法在這里稱為“最小-最大搜索”(Min-max Search)
  用最小-最大搜索來解諸如井字棋的簡單棋局是可行的(即完全了解每一種變化)。井字棋的博弈樹既不煩瑣也不深,所以整個樹可以遍歷,棋局的所有變化都可以知道,任何局面都可以保證找到一步最佳著法。
  數學上用這種方法處理國際象棋也是可以的,但是目前和不久的將來用計算機去實現,卻是不可行的。即便如此,我們仍然可以用基于最小-最大搜索的程序來下國際象棋。相比最小-最大地搜索整個樹,在一個給定的局面下搜索前幾步則是可能的。由于葉子結點的局面沒能搜索出殺棋或和棋,所以要用一個稱為“評價”(Evaluate)的啟發函數給這些局面賦值。盡管程序設計師希望這些值能夠通過知識來得到,但它們確實都是猜的。
 
基于最小-最大的評價函數
 
  我不打算在這里談很多關于評價函數的細節。這里我只說明它是怎樣確定的,在以后的章節中會詳細展開。評價函數首先應該返回局面的準確值,在沒辦法得到準確值的情況下,如果可能的話啟發值也可以。它可以由兩種方法來決定:
  (1) 如果黑方被將死了,那么評價函數返回一個充分大的正數;如果白方被將死了,那么返回一個充分大的負數;如果棋局是和棋(例如某一方逼和,或者雙方都只有王),那么返回一個常數,通常是零或接近零。如果不是棋局結束局面,那么它返回一個啟發值。我將不詳細介紹這個啟發值是如何確定的,但是我有把握說子力平衡是首先要考慮的(如果白方盤面上多子的話,這個值就大),而其他位置上的考慮(兵型、王的安全性、重要的子力等等)也需要加上。如果白方是贏棋或者很有希望贏,那么啟發函數通常會返回正數;如果黑方是贏棋或者很有希望贏,那么返回負數;如果棋局是均勢或者是和棋,那么返回在零左右的數值。
  (2) 這個函數的工作原理跟第一個一樣,只是如果當前局面要走子的一方優勢,那么它返回正數,反之是負數。
 
最小-最大搜索是如何運作的
 
  最小-最大搜索是一對幾乎一樣的函數,或者說兩個邏輯上重復的函數。我寫了很少的代碼,用一個更好的函數來完成同一件事,但是寫出來時卻收到一些意見,因此我首先寫出純粹的(不完美的)最小-最大函數,代碼如下:
 
int MinMax(int depth) {
 if (SideToMove() == WHITE) { // 白方是“最大”者
  return Max(depth);
 } else {           // 黑方是“最小”者
  return Min(depth);
 }
}
 
int Max(int depth) {
 int best = -INFINITY;
 if (depth <= 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = Min(depth - 1);
  UnmakeMove();
  if (val > best) {
   best = val;
  }
 }
 return best;
}
 
int Min(int depth) {
 int best = INFINITY; // 注意這里不同于“最大”算法
 if (depth <= 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = Max(depth - 1);
  UnmakeMove();
  if (val < best) {  // 注意這里不同于“最大”算法
   best = val;
  }
 }
 return best;
}
 
  上面的代碼可以這樣調用:
 
val = MinMax(5);
 
  這樣可以返回當前局面的評價,它是向前看5步的結果。
  這里的“評價”函數用的是我上面所說第一種定義,它總是返回對于白方來說的局面。
  我簡要描述一下這個函數是如何運作的。假設根局面(棋盤上當前局面)是白方走,那么調用的是“Max”函數,它產生白方所有合理著法。在每個后續局面中,調用的是“Min”函數,它對局面作出評價并返回。由于現在是白走,因此白方需要讓評價盡可能地大,能得到最大值的那個著法被認為是最好的,因此返回這個著法的評價。
  “Min”函數正好相反,當黑方走時調用“Min”函數,而黑方需要盡可能地小,因此選擇能得到最小值的那個著法。
  這兩個函數是互相遞歸的,即它們互相調用,直到達到所需要的深度為止。當函數到達最底層時,它們就返回“Evaluate”函數的值。
  如果在深度為1時調用“MinMax”函數,那么“Evaluate”函數在走完每個合理著法之后就調用,選擇一個能達到最佳值的那個著法導致的局面。如果層數大于1,那么另一方有權選擇局面,并找一個最好的。
  以上內容應該不難理解,但是代碼很長,下面有個更好的辦法。
 
負值最大函數
 
  負值最大只是對最小-最大的優化,“評價”函數返回我所說的第二種定義,對于當前結點上要走的一方,占優的情況返回正值,其他結點也是對于要走的一方而言的。這個值返回后要加上負號,因為返回以后就是對另一方而言了。代碼如下:
 
int NegaMax(int depth) {
 int best = -INFINITY;
 if (depth <= 0) {
  return Evaluate();
 }
 GenerateLegalMoves();
 while (MovesLeft()) {
  MakeNextMove();
  val = -NegaMax(depth - 1); // 注意這里有個負號。
  UnmakeMove();
  if (val > best) {
   best = val;
  }
 }
 return best;
}
 
  在這個函數里,當走子一方改變時就要對返回值取負值,以反映當前局面評價的更改。就根結點是白先走的情況,如果沒有剩下的層數,那么“評價”返回的值是就白方而言的,如果有剩下的層數,就產生后續局面,函數對這些局面逐一做遞歸,每個次遞歸都得到就黑方而言的評價,黑方走得越好值就越大。當評價值返回時,它們被取負數,變成就白方而言的評價。
  該函數在遍歷時結點的順序同“最小-最大”搜索的函數是一樣的,產生的返回值也一樣。它的代碼更短,同時減少了移植代碼時出錯的可能,代碼維護起來也比較方便。
 
  原文:http://www.seanet.com/~brucemo/topics/minmax.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 基本搜索方法——簡介()
  • 下一篇 基本搜索方法——Alpha-Beta搜索
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果