國際象棋程序設計(六):局面評估函數
 
François Dominic Laramée/
 
  已經六個月了,我知道你們有人覺得我不會閉嘴,但是你們錯了,這是我的國際象棋程序設計連載的最后一篇。還有,我的Java象棋程序(看上去很爛)已經做好了,和這篇文章一起上傳給了GameDev網站,這個程序還是可以驗證這些連載內容的。
  這個月的話題——局面評估函數——確實很特別,搜索技術大同小異,著法產生可以只根據規則來處理,而局面的評估則需要很深入徹底的分析。可以想象,如果我們不知道某個局面會導致哪方獲勝,那么評價這個局面的相對強弱將是不可能的。因此,很多要討論概念對于其他游戲來說就不是這么回事了,有的則根本不能用。對于你自己的游戲,考慮用什么樣的評估方法,這是你作為程序員應該知道的。【譯注:對于中國象棋要特別注意,很多概念不能從國際象棋照般,我寫過《中國象棋和國際象棋比較研究》一文,詳細闡述過這個問題。】
  抓緊時間,讓我們來看一些局面評價的尺度,并且需要了解它們有什么作用。
 
子力平衡
 
  簡單地說,子力平衡(Material Balance)就是指雙方各有哪些棋子。根據象棋文獻,后的價值是900分,車500,象325,馬300,兵100,王是無價的。計算子力平衡是非常簡單的,每方的子力價值就是:
 
MB = Sum (Np x Vp)
 
  這里Np是棋盤上這種類型的子的數目,Vp是子的價值。如果你在棋盤上的子力價值比對手多,那么你的形勢好。【說句提外話,外國人把“吃”說成“抓獲”(Capture),意思是棋子并非消失了,而是暫時退出戰場了,所以說子力價值時一定要強調“棋盤上”。】
  看上去非常簡單是不是?但是這和象棋的局面評價還差很大距離呢。CHESS 4.5的作者估計了很多位置上的因素,例如機動性和安全性差不多接近1.5個兵。實際上,用不著考慮別的,這就足夠可以下出好棋了。【注意,在把“兵值”這個概念運用到中國象棋的時候,最好也把車設成500,這時機動性和安全性的因素就可以參考國際象棋,也不超過150分。具體的子力價值可參考《中國象棋和國際象棋比較研究()——子力價值》一文。】
  的確,有些情況下為了通過子力交換讓局面得到進展,你必須犧牲某些棋子(甚至是后)。然而最好是通過搜索來發現,例如棄后可以導致3步殺,你的搜索函數不需要額外的代碼就會找到殺棋(前提是它看得足夠深遠)。如果你硬是要在評價函數里寫特別的代碼,來確定是否應該棄子,這種事情將是噩夢。
  很少有程序會用像我開始所說的那個評價函數。由于計算過于簡單,人們會在上面增加點東西,都是這么做的。舉一個眾所周知的例子,當你子力上處于領先時,交換相等的子力是有利的。交換一個兵是不錯的選擇,因為它為你的車開放棋盤,但是你必須在棋盤上保存一些兵直到殘局,以構筑防御屏障或者升變成后。最后,如果開局庫里走出棄子的開局,你不用為程序擔心,因此你要把“藐視因子”(Contempt Factor)加到子力平衡的評價中。例如當子力落后150分甚至更多時,你仍然讓程序覺得是領先的。
  要注意,子力平衡在象棋和西洋棋里具有很高的地位,但是在黑白棋里卻是欺騙性的。的確,棋局最后你必須控制更多的格子才能贏,但是你最好在中局階段控制子的個數。在其他游戲像五子棋Go-Moku確實應該是五子棋,我想不出還有什么不吃子的黑白棋類了】及其變種N子棋(Connect-N)【具體怎么下我也不知道】,子力平衡是不會變化的,因為始終沒有被吃的子。
 
機動性和對棋盤的控制
 
  將死的特征之一是沒有合理的著法。直覺上,好像選擇余地越大約好,比如選手在30種著法內找出一步好棋,這種可能總要比限定在3步內高。
  在象棋中,機動性是很好評估的 計算同一局面下每方的合理著法,你已經能做到了【還要復習一下《著法的產生》嗎?】。然而這個數字僅僅占一小部分。為什么呢?就因為很多著法是漫無目的的。例如你每次讓車向后退一格,著法是合理的,但不產生作用。另外,不惜代價試圖限制對手的機動性,會讓程序進行一系列漫無目的的將軍,同時摧毀自己的防線。由于解除將軍通常只有34種合理著法,所以基于機動性的程序會走出劣著去將軍對方,過會兒就會發現什么事也沒干成,并且自己的兵力也成一盤散沙了。【我認為這種結果的根源在于沒有把將軍著法考慮進“靜態搜索”中,如果考慮進去了,那么將軍的時候不做局面評價,根本不存在對手機動性很低的假象。】
  但是,有些明智的機動性評估方法,會起點作用。我的程序就“壞象”給予罰分,即象的行動路線被一系列同色格的兵阻擋的情況,當馬太靠近棋盤邊緣時也同樣處理。另一個例子是車,在開放或半開放線(即沒有兵或只有一個兵的縱線)上價值更高。
  和機動性有密切聯系的是棋盤的控制能力。在象棋中,如果一方對某個格子產生攻擊的棋子數量超過對方,那么這一方就控制了這個格子。走到受控制的格子通常是安全的,走到被對方控制的格子則是危險的。(有一些例外,把后走到被敵方兵攻擊的格子里,不管你有多少子可以吃他的兵,這無論如何不是好主意。還有,你故意把子送到對方嘴里,但是對方有更重要的格子需要保護。)在象棋中,控制中心是開局的基本目標。但是,控制能力在某種程度上是很難計算的,它需要在任何時候都更新數據庫,來記錄棋盤上所有被攻擊的格子。很多程序都這么做,但我的沒有。
  機動性對于象棋程序來說并不是非常重要的,但在黑白棋里卻非常重要(在殘局中有很少子可走的一方會陷入很深的困境)。而對圍棋而言,對棋盤的控制則是勝利的標致。
 
局勢發展
 
  有個教條,下象棋時輕子(象和馬)要盡早投入戰斗,王要盡早易位,車和后盡量少動,直到關鍵時刻作出決定性的攻擊。這是有很多原因的,馬和象(還有兵)能控制中心,來支持后的火力,把它們調動出去能為底線疏通車的路線。隨著棋局的進行,車就可以跑到第七行(即開始對對方的兵動手),形成巨大的破壞力。
  我的程序用了一些因子來衡量局勢的發展。首先,任何王和后前沒有動過的兵都要扣分,阻擋車的馬和象也要扣分,這樣可以讓后在其他子力出動后才開始動,如果對手還有后,那么王易位到安全位置時則給予很大的加分(有易位權但是沒有易位的也給予少量加分)
  你可以看到,局勢發展的因素在開局階段很重要,但是馬上將失去意義。在大約10回合以后,要衡量的因素基本上都發生過了【即能加分的都加了,要扣分的都扣了】
  注意,在西洋棋之類的游戲中,傾向于局勢發展可能很不好。事實上,先走的一方要空出后面一行的空位,這就已經吃虧了,而在這些地方避免局勢發展,通常是不錯的選擇。
 
兵形
 
  象棋大師門常說,兵是象棋的靈魂。因此新手很難體會的是,強手在對局時會因為一個兵的損失而早早認輸。
  象棋書籍中提到很多兵的類型,有些是有利的,有些是有害的。我的程序考慮了以下幾點。
  1. 疊兵或三疊兵,一方兩個或多個兵在同一列上是很壞的,因為它們的移動相互阻礙了;
  2. 對兵,雙方兩個兵“頭碰頭”互相阻擋去路,會造成很大的障礙;
  3. 通路兵,當兵進展到不會有對方兵攻擊或阻礙時【即同一列和相鄰列里都不能有對方的兵】,就會變得非常強大,因為它們更容易到達底線實現升變;
  4. 孤兵,兩邊都沒有同伴兵保護的兵,最容易受到攻擊,最需要尋求保護;
  5. 滿兵,棋盤上有太多的兵會影響機動性,為車開放一條縱線才是好主意。
  最后兵形上要注意的是:后面跟了車的通路兵是非常危險的,因為任何吃掉它的子都會成為車的盤中餐。如果有一個車在通路兵的后面(同一列),那么我的程序給予極高的加分。
 
王的安全和取向
 
  我們很早就談到過王的安全了,在開局和中局里,保護王是最重要的,易位是最好的辦法。
  但是在殘局里,王身邊的很多子都沒了,他轉眼間變成了攻擊性子力!把它留在兵陣的后面簡直是浪費資源。
  “取向”(Tropism)在這里衡量的是一個子攻擊對方王的難易程度,通常用距離來衡量。取向的計算規則跟兵種有關,不過通用的規則是,你越靠近對方的王,你對他的壓力就越大。
 
確定權重
 
  現在我們確定了有那些因素是需要衡量的,但是我們怎么決定它們的權重呢?
  這是個非常有價值的問題,可以花幾年時間(也確實有人在做)用線性組合的辦法來調整評估函數,有時把機動性設得多一些,有時更強調安全性,等等。我當然希望有一個絕對的答案,可惜沒有,因為再好的評價函數都會碰到麻煩和失誤。如果你的程序足夠強,那很好。如果不是,那么試試別的方案,讓它和你原來的程序下,如果能贏下大多數,那么新的方案就是一個進步。
  有三種方法可以試試:
  1. 通過優化評估函數取得的成績,要達到加深一層搜索所達到的同樣效果,這是非常困難的。如果你很疑惑,那么寧可把評估函數設得簡單些,把更多的處理器資源留給Alpha-Beta搜索。【有關資料表明,加深一層搜索大約可以使棋力提高200(ELO),這是相當可觀的。】
  2. 除非你想和世界冠軍去比,否則你的局面評價函數不必要特別有效。
  3. 如果你的程序確實很快,你可以花些時間用適當的算法來改進評估方法。但是對象棋來說,花上幾千年時間都是有可能的。【這里指用適當的算法來調整權重,例如線性回歸分析、神經網絡算法等,每做一步調整,都需要用大量的對局來試驗,所以工作量非常大。】
  【最后想注明我的觀點,即局面評估函數是整個象棋程序的核心。人們越來越把注意力集中到局面評估函數上,好的象棋程序往往用上萬行的程序來分析局面,但它們的作者很少會透露出其中的細節。一個最簡單的辦法就是去看一些公開了的象棋程序,例如:Crafty的評估函數有4000多行,主要包括以下四方面的內容:
  (1) 子力價值,僅僅是簡單地把每個子的價值加在一起;
  (2) 兵的價值,不僅考慮兵的相對位置,也考慮通路兵(特別在殘局中)
  (3) 跟每個子位置有關的子力價值,即子力的靈活性、協調性等因素;
  (4) 王的安全性,既考慮王周圍的兵陣,也考慮可以攻擊王的其他棋子。
  以上譯自Crafty源程序的第一段,其中的細節可以參考這個程序的其他片段。】
 
下一個月
 
  好了,沒有下一個月了,就這些了。
  如果我要把這個連載拖得長一些,我可以寫一些關于開局庫(Opening Book)、殘局庫(Endgame Library)、特別針對象棋的硬件,以及很多很多其他的內容。我當然寫得出來,但是我才不寫呢。我打算把一部分內容保留到我今年秋天要寫的書里,其他內容我也不知道到底有沒有用。還有一個原因,我也懶得寫下去了。
  我希望你們喜歡看我的東西,希望你們能學到兩三個有用的技巧。如果真的學到了,那么明年看我寫的別的東西吧(GDCE3)【我也不知道是什么學科,GDC好像是圖形顯示控制芯片,反正和象棋沒任何關系】,并且在你公司里的工程師或程序員面前好好夸我,好嗎?
  太高興了!
 
  François Dominic Laramée200010
 
  【譯后注:總的來說Laramée寫的東西還是比較淺顯的,沒有代碼和過于專業的知識(即便是有,我也已經在譯注中說明了)。但是或許是我英語水平的問題,他的某些表述并不能理解,因此即便很別扭地翻譯出來了,還是要在譯注中加上自己的理解,這讓我非常吃力。不過總算一切都結束了。
  與此同時,我還收集了很多專題方面的文章,大概有三十來篇,本來是想翻譯的,以展示我在程序設計方面的造詣,但是沒有時間了(況且在Laramée的文章里我也發揮過癮了)。我相信讀者看了這六篇連載后一定覺得還不夠,至少對于想設計象棋引擎的讀者來說,僅僅看這么點東西是遠遠不夠的,因此我把這些原文放在我的網站上,相信對于學過程序設計的讀者來說,看這些文章應該是沒有問題的。
  如果你讀到有疑問的地方,不妨和我交流,或許你的疑問是很就價值的。如果你找到文中明顯的錯誤(包括錯別字),一定要寫信給我,我的工作是無償為象棋愛好者和程序設計師做的,所以也需要你們的幫助。】
 
  原文:http://www.gamedev.net/reference/programming/features/chess6/
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 國際象棋程序設計():高級搜索方法
  • 下一篇 概述
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果