最小-最大搜索 Bruce Moreland / 文 　爺爺時代的“最小-最大”原理
　
　　所有雙向搜索算法的最基本的思想都是“最小-最大”(Minimax)原理。它可以追溯到中世紀(Dark Ages)，但我相信它最早是由馮-諾依曼(Von Neumann)【應該是John von Nuoma，1903-1957，美籍匈牙利數學家】在60年前完整描述的：
　　1. 假設有對局面評分的方法，來預測棋手甲(我們稱為最大者)會贏，或者對手(最小者)會贏，或者是和棋。評分用數字表示，正數代表最大者領先，負數代表最小者領先，零代表誰也不占便宜；
　　2. 最大者的任務是增加棋盤局面的評分(即盡量讓評分最大)。
　　3. 最小者的任務是減少棋盤局面的評分(即盡量讓評分最小)。
　　4. 假設誰也不會犯錯誤，即他們都走能讓使局面對自己最有利的著法。
　
　　那么這該怎么做呢？設想一個簡單的游戲，每方只走一步，每步只有兩種著法可供選擇。評分函數只和最后棋盤的局面有關，即評分是最大者和最小者著法綜合的結果。

最大者的著法 ?? ?最小者的著法 ?? ?評分
A ?? ?C ?? ?12
A ?? ?D ?? ?-2
B ?? ?C ?? ?5
B ?? ?D ?? ?6

　　最大者假設最小者會下出最好的棋，因此他知道，如果他選擇著法A，那么他的對手會回應D，使最終評分變成-2(即獲勝)。但是，如果最大者走的著法B，那么他就會獲勝，因為最小者的最佳著法仍然是正數(5)。所以按照“最小-最大”算法，最大者會選擇著法B，即使他選擇A并且最小者走錯時評分還會更高。
　　“最小-最大”原理有個弱點，從簡單的例子中還不能明顯地看出來——要檢查的各種路線的數量是指數形式的，這就意味者工作量會以幾何級數增長。
　
　　1. 每方有多少種可能的著法，這個數稱為分枝因子(Branch Factor)，用b表示；
　　2. 考慮的深度用n表示，通常說“n層”，n是整數，“層”(Ply)表示一個棋手走的一步棋。例如在上面介紹的迷擬游戲中，搜索深度是2層。每個棋手走1步。
　
　　例如在象棋中，通常在中局階段分枝因子大約為35種著法，在黑白棋中大約為8。由于“最小-最大”算法的復雜度是O(bn)，所以對一個局面搜索4層就需要檢查150萬條路線，這是多大的工作量！再增加上去，5層就會把搜索樹膨脹到5000萬，6層則達到18億！【原作者這里寫的是8層150萬、9層5000萬、10層18億，不知為何多算了4層。】

　　幸運的是，有辦法能在精確度不打折扣的情況下大幅度削減工作量。

從淺顯的地方開始在國際象棋里，雙方棋手都知道每個棋子在哪里，他們輪流走并且可以走任何合理的著法。下棋的目的就是將死對方，或者避免被將死，或者有時爭取和棋是最好的選擇。國際象棋程序通過使用“搜索”函數來尋找著法。搜索函數獲得棋局信息，然后尋找對于程序一方來說最好的著法。一個淺顯的搜索函數用“樹狀搜索”(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譯者：象棋百科全書網 (webmaster@xqbase.com)類型：全譯

總結

以上是生活随笔為你收集整理的对弈程序基本技术---最小-最大搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。