对弈程序基本技术---最小-最大搜索
生活随笔
收集整理的這篇文章主要介紹了
对弈程序基本技术---最小-最大搜索
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
最小-最大搜索 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)類型:全譯
所有雙向搜索算法的最基本的思想都是“最小-最大”(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) 這個函數的工作原理跟第一個一樣,只是如果當前局面要走子的一方優勢,那么它返回正數,反之是負數。最小-最大搜索是如何運作的最小-最大搜索是一對幾乎一樣的函數,或者說兩個邏輯上重復的函數。我寫了很少的代碼,用一個更好的函數來完成同一件事,但是寫出來時卻收到一些意見,因此我首先寫出純粹的(不完美的)最小-最大函數,代碼如下:
總結
以上是生活随笔為你收集整理的对弈程序基本技术---最小-最大搜索的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 对弈程序基本技术----Alpha-Be
- 下一篇: Web安全实践(14)嗅探,arp欺骗,