國際象棋程序設計(四):基本搜索方法
 
François Dominic Laramée/
 
  這個煩瑣、沒有代碼、像膠水一樣的連載,已經進入第四部分了,你們還在看下去嗎?如果是的,就寫eMail給我,我就可以找到寫這些東西的理由了。
  無論如何,這個月的主題是策略類游戲的敵對搜索(Two-Agent Search)【譯注:意思是站在兩個立場上的搜索,我也不知道該用什么比較確切的術語】,要了解它們有什么作用,如何來做,對電腦的程序意味著什么。我們要討論的技術在所有的游戲中都很重要,但是僅僅靠它們是不足以下象棋的。下個月,我會介紹一些高級的技術,它們能顯著增強棋力,同時提高搜索效率。
 
為什么要搜索?
 
  簡單地說,因為我們還沒有聰明到可以拋棄搜索的地步。
  一個真正聰明的程序可以只依靠棋盤局面來確定,哪一方處于領先以及領先多少,并且制定作戰計劃讓這個優勢變為勝果。不幸的是,需要考慮的局面類型太多了,再加上那么多的規則和特例,就是再聰明的程序也不擅長做此類事情。而它們擅長的則是計算。因此對象棋程序來說,與其只根據棋盤的局面來決定好的著法,不如使用它們的蠻力——考慮每一種著法,然后為對手考慮這些著法的所有應對著法,循環下去,直到處理器吃不消為止。
  比起掌握復雜的策略,深入的搜索是教電腦下棋的比較簡單的方法。例如,考慮馬的捉雙問題,走一步棋就可以同時攻擊兩種棋子(例如一個車和一個后)。掌握這種類型的走法是需要花一些時間的,更復雜些,我們還要判斷這個格子有沒有保護。然而,一個愚鈍的3步的搜索就可以學會捉雙了,程序最終會嘗試讓馬走到捉雙的格子,并探索對手對于捉雙的回應,然后吃掉沒有逃跑的那個棋子,從而改變了子力平衡。由于全面搜索可以看到每一步,所以不會錯過任何機會。如果經過5步棋后可以產生殺棋或捉死后(無論怎樣不容易看到),只要電腦的搜索得足夠深,就會看到這個著法。因此,搜索得越深,電腦就會施展越復雜的作戰計劃。
 
爺爺時代的“最小-最大”原理
 
  所有雙向搜索算法的最基本的思想都是“最小-最大”(Minimax)原理。它可以追溯到中世紀(Dark Ages),但我相信它最早是由馮-諾依曼(Von Neumann)【應該是John von Nuoma1903-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億!【原作者這里寫的是8150萬、95000萬、1018億,不知為何多算了4層。】
  幸運的是,有辦法能在精確度不打折扣的情況下大幅度削減工作量。
 
Alpha-Beta搜索——讓“最小-最大”法成為現實(也只是有一點點現實)
 
  設想你在迷擬游戲中已經搜索了著法B,結果你知道最大者在整個游戲中最高得分是5
  現在假設你開始搜索著法A了,并且一開始尋找的路線是A-D,這條線路的得分是-2。對于最大者來說,這是非常糟糕的,如果他走了A,那么結果肯定會是-2,因為最小者總是走得最好的。這是因為,如果A-CA-D更好,那么最小者會選擇A-D,如果A-C更壞(比如說-20),那么最小者就會選擇這條路線。所以,沒有必要再去看A-C以及其他由A產生的路線了——最大者必須走B,因為到此位置的搜索已經能證明,無論如何A是個更糟的選擇。
  這就是Alpha-Beta算法的基本思想——只要你有一步好的著法,你就能淘汰其他可能導致災難的變化,而這樣的變化是很多的。如果再跟前面介紹的置換表結合起來,當不同路線的局面發生重復時可以節省下分析局面的時間,那么Alpha-Beta就能產生無限的能量——在最好的情況下,它處理的結點數是純粹的“最小-最大”搜索的平方根的兩倍,從1500萬可以減少到2500
  【要說明Alpha-Beta搜索的結點數是死辦法(即不用Alpha-Beta搜索的辦法)的平方根的兩倍那么多,可以分別計算搜索樹中兩種類型的結點——Alpha結點和Beta結點。
  Alpha-Beta搜索是完全搜索,如果某個結點是完全搜索的,那么這個結點稱為Alpha結點,顯然根結點是Alpha結點。那么Alpha結點的分枝又是什么呢?至少有一個Alpha結點,這是肯定的,最好的情況下,剩余的結點都可以產生截斷,這些結點稱為Beta結點。Beta結點有個特點,只要它的分枝中有一個Alpha結點產生作用,那么剩下的結點就沒有搜索的必要了,我們還是取最好的情況,分枝中只有一個Alpha結點。
  那么如何計算Alpha結點的個數呢?一個Alpha結點下面有b - 1Beta結點,每個Beta結點下面又有1Alpha結點,這樣深度每增加了兩層結點數才擴大b倍,因此總的Alpha結點數就是bn/2。同樣道理,Beta結點也這么計算,得到的結果也是bn/2,因此總結點數就是2bn/2。】
 
對著法排序來優化Alpha-Beta搜索
 
  可是,我們如何才能達到預期的效果呢?我們是否還需要做其他事情?
  的確是的。只要Alpha-Beta搜索可以找到比其他著法好的著法,它就能對搜索樹作出非常有效的裁減,這就意味著,關鍵在于首先搜索好的著法。當我們在搜索其他著法以前先搜索到最好的著法,那么最好的情況就發生了。然而最壞的情況,搜索著法的順序是按評分遞增的,即每次搜索到的著法都比曾經搜索的著法要好,那么這種情況下的Alpha-Beta搜索就無法作出任何裁減,這種搜索將退化為極其浪費的“最小-最大”搜索。【這就是前一章的標題中寫道“也只是有一點點現實”的原因。】
  對搜索進行排序是相當重要的。讓著法隨便排列肯定不行,我們必須找到更聰明的辦法。不幸的是,如果有簡單的辦法知道最好的著法,那還有搜索的必要嗎?因此我們必須用“猜最好的著法”來對付。
  有很多技術可以讓著法的順序排列成盡可能好的順序:
 
  1. 用評估函數對著法打分,然后排序。直覺上這會起到作用,評估函數越好,這個方法就越有效。不幸的是在象棋中它一點也不起作用,因為下個月我們將了解到,很多局面是不能準確評估的。
  2. 找到在置換表中已經存在的局面,如果它的數值足夠好,就會產生截斷,這樣就不必再進行其他搜索了。
  3. 嘗試特定類型的著法。例如,后被吃掉肯定是最壞的想法,所以先檢查吃子的著法是行之有效的。
  4. 把這個思路進行拓展,關注已經在同一層深度產生過截斷的著法。“殺手啟發”(Killer Heuristic)是建立在很多著法是次序無關的基礎上的。如果你的后被攻擊了,不管你把H2兵挺一格還是兩格,對手都會吃掉你的后。因此,如果在搜索H2-H3著法時,“象吃掉后”的著法會產生截斷,那么在搜索H2-H4著法時,“象吃掉后”很有可能也產生截斷,當然應該首先考慮“象吃掉后”這一步。
  5. 再把殺手啟發拓展到歷史表上。如果在前面幾回合的搜索中,發現G2-E4的著法很有效,那么很有可能現在仍然很有用(即便原來的格子是象而現在變成了后),因為棋盤其他位置的情況不太可能有多少變化。歷史啟發的的實現非常簡單,只需要一個64x64的整數數組,它可以起到很可觀的效果。
  現在已經談了所有寶貴的思想,然而最有效的方法卻稍稍有背于人的直覺,這個方法稱為“迭代加深”(Iterative Deepening)
 
迭代加深的Alpha-Beta搜索
 
  如果你正在搜索6層的局面,那么理想的著法順序應該由同樣層數搜索的結果來產生。既然這明顯是不可能做到的,那么能否用稍淺的搜索(比如說5)來代替呢?
  這就是迭代加深方法背后的思想——一開始搜索2層,用這樣種搜索產生的著法順序來搜索3層,反復如此,直到到達規定的深度。
  這個技術會受到一般人的質疑——大量的努力是重復的(810次乃至更多),不是嗎?
  那么考慮一下搜索樹的深度n和分枝因子b好了。搜索樹在第1層的結點數為b,第2層是b2,第三層是b3,等等。如果b很大(記住中局時在35左右),那么絕大多數工作量取決于最后一層。重復搜索(n - 1)的深度其實是小事一樁,即便迭代加深一點也不起作用,它也只會多花4%的時間(在通常的局面上)
  但是,它的優勢是非常可觀的——由淺一層搜索的結果排列得到的順序,在層數加深時可以大幅度增加截斷率。因此,迭代加深的Alpha-Beta搜索實際上找的結點數,會比直接的Alpha-Beta搜索的少很多。在使用置換表后,它的收效就更可觀了——重復搜索淺的部分就幾乎不需要時間了,因為這些結果在置換表里都有,沒有必要重新計算了。
  【需要指出的是,實際運用中通常只對根結點進行迭代加深,這樣搜索的結點數是1 + b + + bn,比bn大不了多少。如果每個結點都用迭代加深,則需要搜索的結點數就是(1 + b)n,剛才提到在最好的情況下分枝因子為合理著法數的平方根,即b6左右,而6n7n是有很大區別的。
  事實上,要在每個結點上都使用迭代加深,只要檢查置換表就可以了,因為從根結點處做深一層的搜索時,除了新增加的一層結點以外,其他各層結點上都有最好的著法存儲在置換表中了,這些著法應該優先考慮,絕大多數著法能產生裁剪,而不需要檢查殺手表或者做產生產生。
  另外,迭代加深可以大幅度提高歷史表的效率,在前一次N層的搜索中歷史表已經有相當豐富的歷史著法信息了,在做N + 1層搜索時,這些歷史信息可以讓著法有更好的順序。】
 
電腦下棋的風格
 
  迭代加深的Alpha-Beta搜索和置換表(并且在歷史表的推動下)能讓計算機對局面搜索到相當的深度,并且可以下國際象棋了。應該這么說,它的祖先“最小-最大”算法決定了那臺電腦(曾經在世界上有驚人之舉的那臺電腦【即馮-諾依曼的ENIAC)下棋的風格。
  例如,設想電腦能對一個局面搜索8層,通常在考慮某一步時,這種讓人不解的模式會讓讓它戰勝對手。只有少數一些看不清的、復雜的、迷惑人、超出直覺局面,才能讓對手抓住一線機會取得勝利,而對于人類棋手(甚至大師)來說,這樣的局面陷阱已經可以寫到書里去了。
  然而,如果電腦找到了一個導致和棋的無聊著法,它就會繞過陷阱,因為它假設對手會作出正確的應對,無論那種可能性有多小,只要電腦認為平局是最高的期望。
  結果你可能會說,電腦下棋會極端謹慎,就像對手都是世界冠軍一樣。如果考慮到電腦算不到出人類棋手布置的陷阱那個深度,人類就會絞盡腦汁布設陷阱,讓電腦犯錯誤。(人類棋手會研究對手的下棋風格,如果卡斯帕羅夫有機會和深藍下一百盤棋,他可能會找到深藍的弱點并且打敗它。但是我們不知道有沒有這種可能性。【現在看來,卡斯帕羅夫戰勝深藍是不在話下的,因為近幾年他一直在和水平更高的電腦較量。】)
 
下一個月
 
  在第五部分,我們會討論直接或改變深度的Alpha-Beta搜索的局限。我們還會討論如何利用一些技術,諸如空著啟發(Null-Move Heuristic)、靜態搜索(Quiescence Search)、期望搜索(Aspiration Search)MTD(f)搜索,以及讓深藍名聲顯赫的“單步延伸”(Singular Extensions)技術,它們會提高下棋水平。堅持住,我們快要結束了!
 
  François Dominic Laramée20008
 
  原文:http://www.gamedev.net/reference/programming/features/chess4/
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 國際象棋程序設計():著法的產生
  • 下一篇 國際象棋程序設計():高級搜索方法
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果