國際象棋程序設計(五):高級搜索方法
 
François Dominic Laramée/
 
  哇,看上去好像有很多人在看我的連載,我的臉都紅了!
  這是倒數第二篇文章,我們會介紹和搜索有關的高級技術,他們既能提高速度,又能增強棋力(或者只有一個作用)。他們中有很多,概念上(程序代碼可能不行)可以運用到任何2人游戲中,然而讓它們用到一些具體問題上,對很多讀者來說還需要加工。
 
干嗎要那么麻煩?
 
  到此為止,我們知道的所有搜索算法,都把局面推演到固定的深度。但是這未必是件好事。例如,假設你的程序最多可以用迭代加深的Alpha-Beta算法搜索到5層,那么來看下這幾個例子:
 
  1. 沿著某條路線,你發現在第3層有將死或逼和的局面。顯然你不想再搜索下去了,因為游戲的最終目的達到了。搜索5層不僅是浪費時間,而且可能會讓電腦自己把自己引入不合理的狀態。
  2. 現在假設在5層你吃到了兵。程序可能會認為這個局面稍稍有利,并且會這么走下去。然而,如果你看得更深遠些,可能會發現吃了兵以后你的后就處于被攻擊的狀態,完了!
  3. 最后,假設你的后被捉了,不管你怎么走,她會在第4層被對手吃掉,但是有一條路線可以讓她堅持到第6層。如果你的搜索深度是5,那么后在第4層被吃掉的路線會被檢測出來,這些情況會評估成災難局面,但是唯一能使后在第6(超出了搜索樹)捉到的那條路線,對于電腦來說被吃是不能被發現的,因此它會認為后很安全,從而打一個較高的分數。現在,為了讓后被吃的情況排除在搜索樹以外,唯一的辦法就是調虎離山,這樣做是很冒險的——犧牲一些局面,還是有可能讓對手犯下錯誤讓你的后溜掉的。那么如果你要通過犧牲一個車來延緩后的被吃呢?對電腦來說,在第4層丟車要比丟后損失小,所以在這個搜索水平上,它情愿丟一個那么大的子,來推遲那個可憐的后的被吃了。(當然在隨后一回合里,電腦會發現無論怎么走,它的后會在第4層被吃掉,并且車丟得莫名其妙。)很早以前Hans Berliner就把這個情況稱為“水平線效應”,這在很大程度上可以通過后面即將介紹的“靜態搜索”來改善。
 
  最后要說一句:象棋中的很多局面(其他游戲也一樣)太不可預測了,實在很難恰當地評估。評價函數只能在“安靜”的局面下起作用,即這些局面在不久的將來不可能發生很大的變化。這將是我們介紹下一個內容。
 
請安靜!
 
  有兩種評估局面的辦法——動態評估(看局面會如何發展)和靜態評估(看它像什么樣子,不去管將來怎樣)。動態評估需要深入的搜索。我們剛剛提到,局面在不久的將來不可能發生很大的變化的情況下,靜態評估才是可行的。這些相對穩定的局面稱為“安靜”(Quiet)或“寂靜”(Quiescent)的局面,它們需要通過“靜態搜索”(Quiescence Search)來達到。
  靜態搜索的最基本的概念是指:當程序搜索到固定深度時(比如6),我們選擇性地繼續各條路線,只搜索“非靜態”的著法,直到找到靜態著法為止,這樣才開始評估。
  找到靜態局面是需要游戲知識的。例如,什么樣的著法可能引起棋盤上子力平衡的巨大改變?對于象棋來說,子力平衡會導致局面的劇烈變化,所以任何改變子力的著法就是——吃(特別是吃主要棋子)、兵的升變都是,而將軍也是值得一看的(僅僅是能導致將死的將軍)【譯注:我認為任何將軍都應該考慮進去,因為它會導致抽吃、長將等決定性局面的產生】。在西洋棋里,吃子和升變【西洋棋的棋子分兵棋(Man)和王棋(King),兵棋沖到底線就變成王棋,因此我斷定它是國際象棋的前身】都是選擇。在黑白棋中,每一步都必須吃子,并且“子力平衡”【僅僅指目前棋子的多少,它和最終棋子的多少沒多大聯系】在短時間內翻覆無常,所以可以說它根本不存在“靜態局面”!
  我自己的程序用了簡單的靜態搜索,它只考慮所有帶吃子著法的線路(x層完全搜索以后)。由于通常局面下沒有太多合理的吃子著法,所以靜態搜索的分枝因子非常小(平均在4-6,雙方在吃子后會迅速下降到0)。但是,靜態搜索算法要分析大量的局面,它可能會占用整個處理器一半以上的時間。當你的程序使用這個方案以前,你要確定你是否需要用它。
  當沒有吃子發生時,我的程序才開始評價局面。其結果就是將層數固定的搜索樹作選擇性的延伸,它能克服大多數由“水平線效應”產生的后果。
 
重要的空著
 
  有個加快象棋程序速度的有效方法,就是引入空著的概念。
  簡而言之,空著就是自己不走而讓對手連走兩次。大多數局面中,什么事都不做顯然不是辦法,你總是必須做點事情來改善局面。(老實說,有一些“走也不是,不走也不是”的局面,空著確實是你的最佳選擇,但不能走,這種 “被迫移動”(Zugzwang)局面是沒有指望的,所以不必對電腦感到失望。)
  在搜索中讓電腦走空著,可以提高速度和準確性。例如:
 
  1. 假設局面對你來說是壓倒性優勢,即便你什么都不走,對手也無法挽回。(用程序的術語來說,你不走棋也可以產生Beta截斷。)假設這個局面本來準備搜索N層,而空著取代了整個搜索樹(你的所有合理著法用空著取代了),并且你的分枝因子是B,那么搜索空著就相當于只搜索了一個N-1層的分枝,而不是B個這樣的分枝。在中局階段通常B=35,所以空著搜索只消耗了完整搜索所需的3%的資源。如果空著搜索表明你已經強大到沒有必要再走棋(即會產生截斷)的地步,那么你少花了97%的力氣。如果沒有,你就必須檢查合理的著法,這只是多花了3%的力氣。平均來說,收益是巨大的。【當然,空著搜索對于處理“被迫移動”局面還是有負面作用的,特別是在殘局中,這個作用相當明顯。可以參考《對弈程序基本技術》專題之《高級搜索方法——空著裁剪》一文。】
  2. 假設在靜態搜索中,你面對一個只有車吃兵一種吃子著法的局面,然而接下來對手就會走馬吃車。你最好不去吃子而走其他不吃子的著法對嗎?你可以在靜態搜索中插入空著來模擬這種情況,如果在某個局面下空著比其他吃子著法有利,那么你繼續吃子就是壞的選擇。并且由于最佳著法是靜態著法,所以這個局面就是評估函數可以作用的局面。
 
  總的來說,空著啟發會減少20%75%的搜索時間。這當然值得,特別是當你把這個方法用在靜態搜索算法上的時候,就像改變“走子的一方”這種代碼一樣簡單,用不了十行就行了。
  【很多書上把“空著”這一技術稱為“空著啟發”(Null-Move Heuristic),本文就是這個意思,事實上在歷史表、迭代加深等啟發的作用下,空著啟發已經意義不大了。現在絕大多數程序都使用了稱為“空著的向前裁剪”(Null-Move Forward Pruning)的搜索(它跟空著啟發是有區別的),盡管是一種不完全搜索,但它卻是諸多向前裁剪的搜索中最有效的一個。】
 
期望搜索和MTD(f)
 
  普通的老式Alpha-Beta搜索對某個局面最終的“最小-最大”值沒有假設。看上去它考慮到任何情況,無論有多反常。但是,如果你有一個非常好的主意(例如由于你在做迭代加深,從而想到前一次的結果),你就會找出那些和你預期的差得遠的路線,預先把它們截斷。
  例如,假設一個局面的值接近于0,因為非常均衡。現在來假設對一個內部結點作先前的評價,它的值在+20,000【這里的單位應該是“千分兵值”, 即1000相當于一個兵的價值,那么馬和象等于3000,車5000,后9000,其他因素也折算成這個值,而UCI協議中則用“百分兵值”,因為沒有必要過于精確】,那么你可以有充分信心對它截斷。
  這就是“期望搜索”(Aspiration Search)背后的思想,一個Alpha-Beta搜索的變種,開始時用從負無窮大到正無窮大來限定搜索范圍,然后在期望值附近設置小的窗口。如果實際數值恰好落在窗口以內,那么你贏了,你會準確無誤地找到路線,并且比其他的路線快(因為很多路線都被截斷了)。如果沒有,那么算法就失敗了,但是這個錯誤是很容易被檢測的(因為“最小-最大”值就是其中一條邊界),你必須浪費一點時間,用一個更大的窗口重新搜索。如果前面的情況比后面的情況多,那么總體上你還是贏了。很明顯,你預先猜的數值越好,這個技術的收效就越大。
  在上世紀90年代中期,研究員Aske Plaat把期望搜索拓展為一個邏輯問題:如果你把帶期望的Alpha-Beta搜索的窗口大小設定成0,將會發生什么事?它當然永遠不會成功。但是如果它成功了,那速度將是驚人的,因為它把幾乎所有的路線全都截斷了。現在,如果失敗意味著實際數值低于你的估計,那么你用稍低點的寬度為零的窗口再試一次,重復下去。這樣,你就等于用Alpha-Beta搜索來做某個“最小-最大”值的拆半查找(Binary Search),直到你最終找到那個寬度為零的窗口。
  這個偉大的設想發表在一個網站上:http://theory.lcs.mit.edu/~plaat/mtdf.html,它的具體實現稱為MTD(f)搜索算法,只有十多行。加上Alpha-Beta搜索和置換表的運用,MTD(f)呈現出驚人的效率,還善于做并行計算。它在“粗糙”(簡單且快速)的局面分析中運行得更好,很明顯,如果局面評估的最小單位越大(例如從0.001個兵增加到0.1個兵),它搜索的步數就越少。
  在Alpha-Beta搜索的變種當中,還有很多具有廣泛用途的算法(例如名聲狼藉的NegaScout,我寧可給白癡講廣義相對論,也不想給你們講這些)【之所以說NegaScout名聲狼藉,是因為它的發明者Reinefeld首次發表該算法時,程序中有一個致命錯誤,導致搜索效率大幅度降低,甚至低于普通的Alpha-Beta搜索,如今這個算法更多地被PVS(主要變例搜索)取代,因為它更容易理解】,但是Plaat堅持認為MTD(f)是至今為止效率最高的算法。我就信了他的話,所以我的程序里用了MTD(f),你們可能會感嘆這個算法是多么簡短啊!
  【MTD(f)在整個過程中只使用極小窗口,并且每次都從根結點開始的,這個過程極大程度地依賴于置換表,稱為“用存儲器增強的試探驅動器”(Memory-enhanced Test Driver,簡稱MTD),它只需要傳遞兩個參數(深度n和試探值f),故得名為MTD(n,f),縮寫為MTD(f)。實際運作中MTD(f)是以迭代的形式收斂的,而不是原作者所說的拆半查找。
  在Plaat的文章中,MTD(f)的代碼有10行,而跟它異曲同工的算法PVS,則只比普通的Alpha-Beta多了5行左右,因此很奇怪原作者(Laramée)為什么如此看好MTD(f)MTD(f)在并行計算上確實比PVS有優勢,由于Plaat等人拿MTD(f)PVS算法的比較是在并行機上完成的,才得出MTD(f)優于PVS的結論,而事實上大部分的程序用的都是PVS。】
 
單步延伸
 
  在我們結束這個主題以前,這是最后一個話題。在象棋中,有些著法明顯比其他的好,這樣就可能沒必要搜索其他的變化了。
  例如,假設你在迭代加深過程中正在做深度為N - 1的搜索,發現某步的評分為+9000(即你吃了對方的后),而其他都低于0。如果像比賽一樣想節約時間,你會跳過前面的N層搜索而對這步進行N層搜索【對于這步來說,搜索加深了一層,對于優勢局面來說,優勢應該是越來越大的,所以加深一層后評分應通常要高】,如果這步額外搜索的評分不比預期的低,那么你可以假設這步棋會比其他著法都好,這樣你就可以提前結束搜索了。(記住,如果平均每層有35種合理著法,那么你就可能節省97%的時間!)
  深藍的小組發展了這個思想并提出了“單步延伸”(Singular Extension)的概念。如果在搜索中某步看上去比其他變化好很多,它就會加深這步搜索以確認里邊沒有陷阱。(實際過程遠比這里說的要復雜,當然基本思想沒變。)單步延伸是耗費時間的,對一個結點增加一層搜索會使搜索樹的大小翻一番,評估局面的計算量同時也翻一番。換句話說,只有深藍那種硬件水平才吃得消它,我那笨拙的Java代碼肯定不行。但是它的成效是不可否認的,不是嗎?【原作者的意思可能是指,單步延伸技術會明顯提高棋力,同時也會增加搜索時間。】
 
下一個月
 
  在第六部分中,我們會著重討論局面評估函數,它才真正告訴程序一個局面是好是壞。這個主題具有極其廣泛的內容,可以花幾年時間來改進評估方法(也確實有人這樣做),因此我們必須對這些內容進行徹底討論,包括它們的可行性和重要程度。【在這篇普及型的連載中,作者怎么可能給你們講那么多呢?】如果任何事情都按照計劃進行,我就該用一些Java代碼來給你們填飽肚子,但是這很難辦到,不是嗎?
 
  François Dominic Laramée20009
 
  原文:http://www.gamedev.net/reference/programming/features/chess5/
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 國際象棋程序設計():基本搜索方法
  • 下一篇 國際象棋程序設計():局面評估函數
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果