《對弈程序基本技術》專題
 
策略和技巧
 
Martin Fierz */
* 瑞士Windisch應用科學學院(Aargau學院)
 
  我通過以下問題的討論來結束這個棋類游戲程序設計的講座。這些問題大都沒有非常明確的答案,因此我作了比較深入的研究。我覺得這些問題非常有趣,希望你們也這么認為。
 
速度的需求
 
  棋類程序設計師們都對程序的速度非常關注,有些人會不顧孩子的出生而讓程序再提高10%的速度,這是何苦呢?原因是速度提高了幾個百分點,棋就會下得不一樣,事實上這個不一樣的程度會超出你的想象。Ken Thompson對他的國際象棋程序“尤物”(Belle)做了很多試驗后發現,搜索每多一層棋力就增加200ELO等級分,換句話說當你的對手比你低200分的時候,平均有75%的棋局是你贏下的。很多人都在做這個試驗,并且得到同樣的結果。因此人們就開始預測搜索多少層才能成為世界冠軍,并且預測“消亡轉折”,即你在搜索到一定深度時,再多搜索一層時棋力不再有原先預計的增長。人們試圖找過這個轉折,但是找到它要比預期的困難得多。我用自己早期設計的西洋跳棋程序Cake++來尋找這個轉折點,指定固定的搜索深度,如5層、7層、9層等等,和少搜索兩層的程序比賽。以下就是試驗結果,很明顯可以看到消亡轉折。我用Chinook做了類似的試驗來作比較,由于對局數太少,數字不太確切。一些在國際象棋中很難找到的規律,在西洋跳棋里就很容易找到,因為西洋跳棋的搜索深度要多得多。
  【譯注:消亡轉折有著重大的理論和實際意義,它可以用來估計電腦程序能夠到達的極限。因為隨著計算機速度的不斷提高(目前仍舊以每一年半翻一番的速度在提高),電腦可以計算的深度也越來越深(估計每兩年就可多搜索一層)。而隨著消亡轉折的到來,即使電腦搜索得再深,棋力也不會有太大的長進,這就可能是電腦棋力的極限了。】
搜索深度 ::(Cake++) 勝率 偏差 勝率(Chinook)
5:3 196:53:33 78.9% 2.1% -
7:5 153:100:29 72.0% 2.0% 77.5%
9:7 181:75:26 77.5% 2.0% 65.0%
11:9 130:111:41 65.8% 2.1% 72.5%
13:11 134:116:32 68.1% 2.0% 58.8%
15:13 119:136:27 66.3% 1.9% 58.8%
17:15 89:165:28 60.8% 1.8% 61.3%
19:17 78:176:28 58.9% 1.8% 57.5%
21:19 60:189:33 54.8% 1.7% 57.5%
又笨又快還是又好又慢?
 
  跟消亡轉折類似的問題是:程序能否通過速度來補償知識的不足?對于這個問題,Hans Berliner做過一個很有名的試驗,用他的國際象棋程序Hitech很好地回答了這個問題。他去掉了程序中大量的局面評價函數,由此產生了另一個程序,命名為Lotech。然后他用Lotech對陣Hitech,并且給Lotech多搜索一層的優勢。一個令人驚奇的結果是:Lotech總是能贏Hitech。因此,有人認為一定存在一個轉折點,使得Hitech能打敗Lotech。在國際象棋中,這個轉折點很難找到。我曾經用自己的西洋跳棋程序來找這個轉折點,但是當時我發現Lotech-Cake總是能贏Hitech-Cake
  【如果計算同樣深度,Hitech棋力比Lotech100分的話,但由于多搜索一層使得Lotech增加了200分,所以棋力反而比Hitech強。根據消亡轉折來推斷的,超過某個深度以后,多搜索一層使得程序的棋力沒有太大長進,只要長進低于100分,那么這個時候Hitech就能擊敗Lotech了。如今電腦思考得越來越深,導致的結果就是:程序設計師們對知識的重視程度增加了。】
 
機器學習
 
  機器學習是一個很吸引人的主題。計算機程序利用前人經驗的方法有很多,其中很多方法被程序作者稱為“學習”(Learning),我將在這里總體介紹一下。最普遍的學習是機械學習,當你的程序輸掉一局棋時,它就把這局棋記住了。這個方法可以在開局庫的學習中實現,你的程序會把一個開局庫著法標記為劣著,如果這個著法會輸棋,那么下一盤棋它就選擇別的著法。這個方法也可以用一個小的置換表來實現,輸掉的棋局里的局面都以輸的局面存儲起來,這樣,程序就不會走到這些局面里去。但是,這種學習的形式實在是太具體了,你的西洋跳棋程序會認為某個具體的局面是壞的,類似典型的局面也是壞的,你的程序卻視而不見。在西洋跳棋中“牽制”(Holds)非常重要,例如你的3個兵被對手的2個兵牽制住,如果不考慮棋盤上的其他棋子,那么對手將要獲勝(至少獲勝的機會很大),因為它很有可能要升變了。你用最基本的機械學習會知道這種牽制的其中一種局面會輸,但是還有成千上萬種類似的局面呢,遇到跟這個局面有微小差別的其他局面,再下一盤還是會輸。這種類型的學習不是真正意義上的學習,把這些程序稱為“智能”(Intelligent)或“吃一塹長一智”(Learning from Mistakes)純粹是糊弄人的。
  另一種類型的機器學習用來自動調整評價函數的權重,這屬于遺傳算法(Genetic Algorithms)的范疇,把遺傳算法作用在評價理論上,就自然地得到了最適合的程序。以下就是這種算法的工作原理,你產生一個評價函數(典型的評價函數是線性的),每一項都有一個權重,因此有:
 
eval = w_1 * f_1 + w_2 * f_2 + ... + w_n * f_n
 
  fi就是局面的各個因素,例如在西洋跳棋中,你可以把f1定義為黑方有強大的底線,因此w1越大,你的程序就越會試圖讓底線留下棋子。因此當你選擇這些因素時,就必須順便優化相應的權重。遺傳算法在一開始時使用一些隨機產生的程序,然后通過它們之間的對陣來找出哪些是好的哪些是壞的。一些壞的程序被篩選掉了,合適的程序幸存下來并得到繁衍——或者是在兩個好的程序之間作交換(隨機地在兩個好的程序中選擇wi),或者隨機改變一個好的程序。現在你只管繼續這樣的工作,指望最終能得到一個好的權重的組合。這就是上世紀50年代Arthur Samuel在他著名的西洋跳棋程序里用的方法。另外還有其他調節權重的方法,深藍(Deep Blue)的小組用了大量特級大師的對局,然后讓程序吻合這些局面。他們對程序和特級大師走出一樣著法的頻率作出統計,然后修改了權重再作嘗試。如果程序能解決更多的局面,那么他們就保留這個修改,否則就重新修改。最近我知道的調整權重的辦法,是Michael Buro在他的黑白棋(Othello)世界冠軍程序Logistello中用到的。他建立了一個巨大的局面數據庫,用來儲存對局結果,然后他把評價函數作用在每個局面上,通過優化評價函數使得產生的分數盡可能地準確。
  所有這些方法都比機械學習更有效。如果某個程序有對西洋跳棋中類似牽制戰術的評價,那么你在評價函數中提高這項的權重,會讓程序認為所有類似情形的局面都是壞的,并且會避免這些局面。那么這樣說來,我們是否已經學到了知識了?我認為還沒有。如果你的程序本身就不包括這個評價呢?即便再怎樣調節權重,也是不會有效果的。因此我們將涉及到下面的學習:
  神經網絡(Neural Networks)能夠發明一些評價模式,而不需要有人告訴它,它能對局面作出評價,并且結合到棋類程序中。神經網絡由很多輸入口,一些隱含的層次結構,以及一個出口組成。這些連接著入口和出口的層次,實際上由很多結點組成,結點有連接上一層的入口和連接下一層的出口。每個結點都可以和其他層有連接,每個連接是有強有弱的。如果同時改變連接及其強度,你就能得到一些評價模式,并確定他們的權重。
  把有評分的局面告訴神經網絡,它就會得到訓練,而在結合了遺傳算法后,神經網絡也會自我學習。有個西洋跳棋程序Blondie24,就是用這種方法實現了自我學習的,并且下得還不錯。我認為這才是真正的學習,它和人類的思考很接近。Blondie的作者把他們的程序吹噓得很過分,但對于目前大多數研究者來說,事實上就是如此,你必須大造聲勢來獲得資金。
 
改進你的程序
 
  你花了無數時間來寫你的程序,它現在下得是否還像初學者?這是很正常的現象,但是請不要失望,我會告訴你一些技巧。首先并且最重要的是,很多問題來源于代碼中的錯誤。Alpha-Beta算法是最容易藏匿錯誤的,你的程序評價了成千上萬個局面,而你只得到一個著法,即使10%的局面是隨機評價的,你的程序仍然在大多數時間內可以走得正確。因此,你需要你需要做一些額外檢查,以確認程序的每個部分都正常工作。一個最典型的技巧就是檢驗評價的對稱性,如果同樣的局面黑白交換后,你的評價函數沒有返回同樣的值,那么肯定有什么地方錯了。如果棋盤有其他的對稱性(在國際象棋的中局里你可以按d列和e列作左右鏡像操作),你也可以利用這樣的對稱性。代碼要盡可能地寫得清晰,優化不要操之過急,否則就得不償失了。在程序用Alpha-Beta算法走第一盤棋之前,不要加任何錦上添花的代碼。只有當你根除了錯誤,才可以著手對程序進行調整。它是否太慢了?你可以用AMD CodeAnalyst這樣的分析測試軟件來考察程序的關鍵部分,并加以改進。讓程序和別的程序下棋,這是個改進程序的非常有效的辦法。程序下了幾百盤棋以后,所有的統計數字就都有了,對你的代碼修改一些地方(搜索算法,評價函數等等),然后再打很多比賽來確認你改得是否有效。如果你改變的只是著法順序,就可以用一組對比測試來代替長時間的比賽,看看花的時間是否減少了,就知道著法順序是否改進了。
 
  原文:http://www.fierz.ch/strategy5.htm
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 其他策略——開局庫
  • 下一篇 結語——國際象棋程序剖析
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果