《對弈程序基本技術》專題
 
調整評價函數
 
David Eppstein */
* 加州愛爾文大學(UC Irvine)信息與計算機科學系
 
  上次我談到了局面評價中的很多函數,把這些函數加起來就可以組合成評價函數。但是數值從哪里來?
  例如在黑白棋中,你可以說出四種函數:
  (1) f(局面) = 子力(我的子數 - 對手的子數)
  (2) g(局面) = (我控制的 - 對手控制的)
  (3) h(局面) = 機動性(我可以走的)
  你必須組合這些函數(可能還有其他項)來構成一個評價函數:eval = a·f + b·g + c·h。例如,你可以嘗試:eval = -1·f + 10·g + 1·h。但是這些數值從哪里來?哪種數值的組合可以得到最好的效果?
  下面是手工找到這些數值的一些方法:
 
  (1) 規格化(Normalize)如果你只關心評價的順序,而通常不怎么關心評價值,那么你就可以把每一項都乘以同樣的常數。這就意味著你對某個特定的項目(比如說兵的價值)可以硬性設一個值,其他值就表示成它們相當于多少個兵。這個做法可以讓你減少一個需要設定的參數。
 
  (2) 約束法(Deduce Constraints)你希望讓電腦作出什么樣的判斷,考慮這些問題就可以確定一些參數了。例如在國際象棋中,即使你賺到一個兵,用車換象或馬通常還是壞的,但是如果你賺到兩個兵那還是好的,因此子力價值要滿足R>B+P(防止換單兵)R<B+2P(鼓勵換雙兵)。這樣的不等式你給得越多,合適的權重組合就越少。在一開始設定權重值的時候,這個方法通常可以得到合適的值,但是后面你仍然需要做一些調整。
 
  (3) 交手法(Hand Tweaking)這是很常用的方法,僅僅是讓你的程序對弈足夠多的次數,來找到它的優勢和弱點,猜測哪些參數會讓程序更好,然后挑選新的參數。這個方法可以很快得到合理的結果,但是你需要對這種棋類有足夠的了解,這樣就可以根據程序的對局來做分析,知道程序的問題在哪里。(也就是說,當程序很笨但是你很聰明時,這個方法最有用。)
 
  不需要人工干預的方法有:
 
  (4) 爬山法(Hill-Climbing)類似于交手法,每次對權重作很小的改變,測試改變后的表現,僅當成績提高時才采納這個改變,需要重復很多次。這個方法看上去很慢,并且只能找到“局部最優”的組合(即評價可能很差,但是任何很小的改變都會使評價更差)
 
  (5) 模擬退火法(Simulated Annealing)類似于爬山法,也是對權重做改變來提高成績的。但是如果改變沒有提高成績,有時候(隨機地,給定一個幾率)也采納改變,試圖跳出全局最優。這個方法需要給定一些幾率,從幾率高、梯度大的條件開始,然后逐漸減小。模擬退火法比爬山法更慢,但是最終可能得到比較好的值。
 
  (6) 遺傳算法(Genetic Algorithms)爬山法和模擬退火法可以得到一組好的權重,它們是逐漸變化的。相反,遺傳算法可以得到幾組不同的好的權重,不斷增加新的組合跟原來的做比較(取用某組中的某個權重,另一組中的另一個權重,互相交換得到新的),通過淘汰壞的組合來控制種群的數量。
 
  (7) 神經網絡(Neural Networks)實際上這更多地是一種評價函數的類型,而不是用來選擇權重的:神經元是閾值(輸入權重的和)的函數,第一層神經元輸入的關于局面的性質(例如位棋盤表示中的某幾個位)就可以構造網絡,然后前一層的結果輸入到后一層。因此單輸入神經元的單層網絡就等同于我們上次討論過的一階評價函數,但是接下來就可以構造更復雜的神經網絡了,而且用這種方法作為評價函數是不難的(只要根據輸入的改變來重新計算神經元的輸出就可以了)。問題仍然像前面所說的,如何設置權重?除了前面的方法外,針對神經網絡還發展出一些方法,例如“暫時差別學習”(Temporal Difference Learning)。其基本思想是確定網絡何時會作出壞的評價,并且讓每個權重增加或減小看是否會評價得更好,這很類似于爬山法。跟其他自動學習的方法相比,神經網絡的好處就在于它不需要很多人類的智慧:你不需要懂得太多的棋類知識,就可以讓程序有個比較好的評價函數。但是根據目前我們掌握的情況,根據自己的智慧來做評價函數,要比機器學習做得好,并且做得快。
 
  這些方法都需要依靠一些自動化的技術,以便對程序的性能進行評估:
  (1) 我們可以用程序處理大量的測試局面(比如人類棋手的高質量對局中提取的局面)并且看它是否得到正確的結果。
  (2) 我們可以讓程序對陣一些著名的對手(比如其他程序)來看它能贏幾盤。或者我們可以讓程序和它自己對陣,以及和它自己的其他版本對陣,例如在爬山法中,用修改過的版本對陣沒修改過的版本。這個方法有自身的缺點,除非系統中增加一些隨機因素,否則兩個程序每次會下出一樣的棋,因此你只是看到一局棋的結果而無法代表全部比賽。一個合適的方法就是拿一組測試局面,從每個局面開始就可以下出不同的棋。
  (3) 我們可以比較兩個結果,一個用評價函數得到,另一個用評價和搜索相結合得到。如果評價是好的,那么兩者應該接近,但是反過來說行嗎?
 
  那么如何來自動掌握評價中的權重呢?可以參考Jay Scott的“博弈中的機器學習”這個網站。他列舉了兩個實驗方法,我認為比較有趣:
  (1) John Stanback(著名的商業國際象棋程序設計師)嘗試用遺傳算法來設置他的程序Zarkov中評價函數的權重組合。他只測試了2000-3000局,我認為太少,得到的值還不錯,但是仍然比手工調整的差。這個例子可以看出遺傳算法確實有效,但是需要遺傳很多代,或者有一個好的權重組合作為祖先。
  (2) Risto Miikkulainen,是得克薩斯大學里遺傳算法的研究員,他曾經針對黑白棋的實驗做了個報告。他用遺傳算法來調整神經網絡型評價函數中的權重。評價網絡通過對陣固定程序來建立,如果這個固定程序下棋是隨機的,那么神經網絡會以棋子-格子數組的形式掌握評價(棋子在角上是好的,在角的鄰近格子上是壞的,等等),直到它一直能贏了才停止學習。然后對陣一個淺的搜索結合棋子-格子數組的程序,它最終(通過幾個星期的計算)學會了基于機動性的策略。但是如果對手已經是很聰明的基于激動性的程序,那么它始終會輸并且不會學習。這個例子可以看出,要進行學習就必須對陣水平相當的程序,例如在遺傳算法的同一個種群里,讓兩個不同的評價的程序進行對陣,也可以讓某個程序對陣不同棋力的對手。
 
  原文:http://www.ics.uci.edu/~eppstein/180a/970415.html
  譯者:象棋百科全書網 ([email protected])
  類型:全譯
  • 上一篇 局面評估函數——簡介()
  • 下一篇 其他策略——勝利局面
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果