《對弈程序基本技術》專題
 
評價函數
 
David Eppstein */
* 加州愛爾文大學(UC Irvine)信息與計算機科學系
 
整體考慮
 
  在你的程序中,評價函數綜合了大量跟具體棋類有關的知識。我們從以下兩個基本假設開始:
  (1) 我們能把局面的性質量化成一個數字。例如,這個數字可以是對取勝的概率作出的估計;但是大多數程序不給這個數字以如此確定的含義,因此這僅僅是一個數子而已。
  (2) 我們衡量的這個性質應該跟對手衡量的性質是一樣的(如果我們認為我們處于優勢,那么反過來對手認為他處于劣勢)。真實情況并非如此,但是這個假設可以讓我們的搜索算法正常工作,而且在實戰中它跟真實情況非常接近。
  評價可以是簡單的或復雜的,這取決于你在程序中加了多少知識。評價越復雜,包含知識的代碼就越多,程序就越慢。通常,程序的質量(它棋下得怎樣)可以通過知識和速度的乘積來估計:
 
 
 
  因此,如果你有一個快速而笨拙的程序,你通常可以加一些知識讓它慢下來,使它工作得更好。但是同樣是增加知識讓程序慢下來,對一個比較聰明但很慢的程序來說,可能會更糟;知識對棋力的增長作用會減少的。類似地,你增加程序的速度,到一定程度后,速度對棋力的提高作用也會減少,你最好在速度和知識上尋求平衡,達到圖表中間的位置。平衡點也會隨著你面對的對手而改變;對于擊敗其他電腦,速度的表現更好,而人類對手則善于尋找你的程序中對于知識的漏洞,從而輕松擊敗基于知識的程序。【譯注:如果你的程序要和人類棋手比,那么最好給程序加上足夠多的知識。】
 
實現方法
 
  就評價方法而言主要有兩個類型。第一個是“終點評價”(End-Point Evaluation),即用你擅長的評價算法,簡單地評價每個局面,而不受其他局面的影響。這通常會給出好的結果,但是非常慢。因此一些程序設計師用了下面的訣竅,稱為預先計算(Pre-Computation),一階評價(First-Order Evaluation),或棋子-格子數組(Piece-Square Tables)
  在我們對一個局面搜索最佳著法之前,我們認真檢查棋局本身,在數組T[格子,棋子類型]中保存計算值。在搜索過程中評價任何局面,只要簡單地把棋子在數組中的值加起來就行了。我們不必每一步都重新計算它們的和,在把棋子從一個格子移到另一個格子時,可以用下面的公式更新評價值:
 
score += T[新的格子,棋子] - T[舊的格子,棋子]
 
  下面就舉一個例子說明國際象棋中的棋子-格子數組:當王被易位到棋盤的角落時,王前面的幾個兵對防御來說是非常有用的。它們前進后防御能力就變差。因此,如果搜索的開始局面王在角落里,我們就應該為這些兵建立一個棋子-格子數組,其值如下:
 
... ... ... ... ...
... 1 1 1 1
... 1 1.1 1.1 1.1
... 1 1.2 1.2 1.2
... - - - -
 
  在王前的三列中,為了使兵盡量離王近些,就在距離近的時候給它們更高的值。
  不幸的是棋子-格子數組會很快失效,如果你要通過棋子-格子數組來增加一些知識,那么這種方法會顯得非常愚蠢。在棋子-格子數組建立之初,這些聯系就根據棋子的原始位置粗略計算好了,因此它們不能建立起幾個移動過的棋子之間的聯系。因此,如果我們搜索很長的一系列著法,例如王走到了棋盤的另半邊,那么原來的棋子-格子數組的值就會非常不準確,因為它只是讓兵防御王原來待的地方,而不是防御王本身。
  用棋子-格子數組的程序通常需要結合終點評價。另一個建立棋子-格子數組的策略,就是把數組的建立延遲到后面的搜索中。例如,你要搜索9步后續著法,那么可以在5步的后續著法下建立數組,為剩下的4步搜索作準備。如果你想這么做,就應該使一個5步著法產生的數組和其他著法產生的數組保持一致,使得所有的評價值都有可比性。在我的課上O. Dave提出另一個改進的建議:用增量的辦法修改棋子-格子數組,例如當王走掉時,對王前幾個兵的獎勵值也去掉了。這看上去是個不錯的思想,但是我不知道如何來實現,也不知道如果實現了,效果會是怎樣。
 
如何組合評價要素
 
  把評價要素組合起來,通常就和上面所說的一階評價一樣,評價函數是很多項的和,每一項是一個函數,它負責找到局面中的某個特定因素。為什么要用加法呢?因為這種簡單的組合信息的方法在實踐中非常好用。
  我自己感覺,棋類程序應該充分嘗試各種可能的評價函數:把各種勝利的可能性結合起來,包括很快獲勝(考慮進攻手段),很多回合以后能獲勝,以及在殘局中獲勝(國際象棋中就必須考慮通路兵的優勢)的可能性,然后把這些可能性以適當的方式結合起來。如果黑方很快獲勝的可能性用bs表示而白方用ws,在很多回合以后獲勝(即不是很快獲勝)的可能性是bmwm,而在殘局中獲勝的可能性是bewe,那么整個獲勝的可能性就是:
 
bs + (1 - bs - ws) * bm + (1 - bs - ws - bm - wm) * be,或者
ws + (1 - bs - ws) * wm + (1 - bs - ws - bm - wm) * we
 
  我想,通過和類似上面的公式把若干單獨概率結合起來,在評價函數中或許是個很好的估計概率的思路。每種概率是否估計得好,這就需要用程序的估計來和數據庫中棋局的真實結果來作比較,這就需要讓程序具有基本判斷的能力(判斷某種攻擊是否能起到效果)。但是這純粹是我的假想,并沒有在程序中測試過,如果你只用加法將不會犯多大的錯。
 
評價函數中要加入哪些信息?
 
  典型的評價函數,要把下列不同類型的知識整理成代碼,并組合起來:
 
  (1) 子力(Material)在國際象棋中,它是子力價值的和,在圍棋或黑白棋中,它是雙方棋盤上棋子的數量。這種評價通常是有效的,但是黑白棋有個有趣的反例:棋局只由最后的子數決定,而在中局里,根據子力來評價卻是很差的思路,因為好的局勢下子數通常很少。其他像五子棋一樣的游戲,子力是沒有作用的,因為好壞僅僅取決于棋子在棋盤上的位置,看它是否能發揮作用。
 
  (2) 空間(Space)在某些棋類中,棋盤可以分為一方控制的區域,另一方控制的區域,以及有爭議的區域。例如在圍棋中,這個思想被充分體現。而包括國際象棋在內的一些棋類也具有這種概念,某一方的區域包括一些格子,這些格子被那一方的棋子所攻擊或保護,并且不被對方棋子所攻擊或保護。在黑白棋中,如果一塊相連的棋子占居一個角,那么這些棋子就不吃不掉了,成為該棋手的領地。空間的評價就是簡單地把這些區域加起來,如果有說法表明某個格子比其他格子重要的話,那么就用稍復雜點的辦法,增加區域重要性的因素。
 
  (3) 機動(Mobility)每個棋手有多少不同的著法?有一個思想,即你有越多可以選擇的著法,越有可能至少有一個著法能取得好的局勢。這個思想在黑白棋中非常有效,國際象棋中并不那么有用。(它也曾被使用,但現在國際象棋程序設計師們把它從程序中去掉了,因為它看起來對整個局面的評價質量沒什么提高。)
 
  (4) 著法(Tempo)這和機動性有著密切的聯系,它指的是在黑白棋或連四子棋中(以及某些國際象棋殘局中),某方被迫作出使局面變得不利的著法。和機動性不同的是,起決定作用的是著法數的奇偶而不是數量。
  例如,考慮下面的連四子棋局面:
 
 
  【連四子棋的規則是:每個著子都必須位于某列的最底下一個空格,獲勝條件是直線、橫線或斜線有四個子相連。可以把連四子棋想象成帶重力的五子棋。】
  1347列已經填滿,因此只能在256列落子。第6列的著子是中立的,哪方都不能利用該列得勝或失利。黑方控制第2列,即紅方不能在這里落子,因為這樣可以讓黑連成四子【注意第3列到第5列,已經有3個黑子形成斜線】。任何一方都不能在第5列著子,因為對方可以馬上勝利【注意該列倒數第3行的空格,任何一方走到該格,都會在第4列到第7(紅方斜線,黑方橫線)連成四子】。如果接下來是紅先走,那么在第6列走了3步之后,黑方被迫走第2列放棄對該列的控制,又是3步后只能走第5列讓紅方取得勝利。但是如果下一步是黑走,那么3步之后會迫使紅方輸棋。
  像這種連四子棋的殘局中,偶數空格的列是無關緊要的,重要的是計算只有一方可以走的奇數列。如果一方控制更多的奇數列,那么他就可能贏。如果雙方控制的奇數列一樣多,如上面的棋盤所示(沒有一列受紅方控制,而黑方只控制一個偶數列),那么中立列的數量就非常重要了——如果它是奇數那么先走的一方會贏,如果它是偶數那么先走的一方會輸。當然,這個簡單的分析是建立在掌握復雜局勢的基礎上的,需要知道一方是如何控制某列上方的格子的。
  像圍棋這樣的游戲,并不存在這樣嚴格的奇偶規則,但是哪方有“主動權”【即“先手”】仍然很重要,一方能選擇走哪里,而另一方只能在同一個地方被迫應對。走一系列著子,每步都贏得一塊小的地盤并讓對手被迫應著,然后再來走棋以取得大地盤并讓對手獲得主動權,這通常是個好的思路。【這里指的是在收官階段,先走先手的小官子,然后再走后手的大官子。】
  【這里有一個中國象棋的排局,也包括類似奇偶性的主動權問題:
 
 
  在這個局面中,雙方的兵()都不能離開原位,否則對方平帥()即可造成鐵門栓殺。雙方的中炮不能離開中線,而三七路炮也不能離開該線,否則對方就會有悶宮殺。這樣的棋型只能有一種取勝方法——用自己的兩個炮頂住對方的兩個炮,迫使對方讓開兵()或三七路炮。
  這就衍生出一個數學游戲:有兩堆石子,雙方輪流從石子中拿去幾顆,每次只能從一堆石子中拿走至少一顆石子,先拿完最后一堆者獲勝。這個游戲的訣竅是:始終讓對方面臨兩堆石子一樣多的窘境。上面這個象棋局面中,兩路炮之間的空格就好比兩堆石子的數量,現在先走一方占有主動,因為兩堆石子數量不一樣多,他只要走一步讓兩堆石子數目一樣就可以了。以紅方先走為例,紅方殺法及其黑方最頑強的抵抗如下:
 
1. 炮七進四 炮3進1
2. 炮五進一 炮3進1
3. 炮五進一 炮3進1
4. 炮五進一 炮3進1
5. 炮五進一 炮3退1
  若黑走炮3平5,則仕五進六、前炮平2、炮七平五做殺無解(若黑走炮2平5解殺則構成長將)
6. 炮七進一 炮3退1
7. 炮七進一 炮3退1
8. 炮七進一 炮3退1
9. 炮七進一 卒6平7
10. 帥五平四 卒7進1
11. 帥四進一 卒7平8
12. 兵四進一
 
  紅方第一步若不走炮七進四,不管進哪個炮,主動權都讓給了黑方,走炮七進八可以守和,其他著法都會讓黑取勝。可見,主動權這一問題在很多棋類中都是存在的,然而這個知識寫入棋類程序中很有難度。】
 
  (5) 威脅(Threat)對手是否會有很惡劣的手段?你有什么很好的著法?例如在國際象棋或圍棋中,有什么子可能要被吃掉?在五子棋或連四子棋中,某一方是否有可以連起來的子?在國際象棋或西洋棋中,有沒有子將會變后或變王?在黑白棋中,一方是否要占角?這個因素必須根據威脅的遠近和強度來考慮。
 
  (6) 形狀(Shape)在圍棋中,如果連起來的一串子圍成兩個獨立的區域(稱為“眼”),那么它們就是安全的。在國際象棋中,并排的兵通常要比同一列的疊兵強大。形狀因素是非常重要,因為局面的長遠價值在幾步內不會改變,也不會因為搜索而變化,這正是形狀因素需要衡量的。(搜索可以找到短期的手段來改進局面,所以評價本身需要包括更多的長遠眼光,使得搜索可以察覺到。)【在中國象棋中,空頭炮(指被對手擺空頭炮)和窩心馬是不好的形狀,不太深的搜索不會察覺到它們的壞處,但是長遠來看是這些形狀會存在嚴重弊端,大多數程序的評價函數會直接對空頭炮和窩心馬進行罰分。】
 
  (7) 圖案(Motif)一些常見的具有鮮明特點的圖案,蘊涵著特殊的意義。例如在國際象棋中,象往往可以吃掉邊兵,卻會被邊上的兵困住。當象被困住時,對手可能還需要很多步才會吃掉它,因此被困的情形不容易被計算機的搜索程序所發現。有些程序通過特殊的評價因素來警告電腦,吃掉那個邊兵可能會犯錯誤。在黑白棋中,在角落的鄰近格子上放一個子來犧牲一個角,往往是非常有用的,這樣當對手占領這個角時,就可以在這個子的邊上放一個提不掉的子,從而在另一個角上取得優勢。
 
 
  上圖中,白方犧牲了右下角。
  當黑方走右下角時,白方在邊上走子,然后贏得了左下角。【黑方只得到一個角,而白方得到了一個角連同邊線上的6子,白大優。】
  對這種犧牲做特別的評價也許是很有必要的,它可以決定是否需要做犧牲,或者來衡量邊線上的子是否能抵擋這種犧牲手段。
 
  原文:http://www.ics.uci.edu/~eppstein/180a/990114.html
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 高級搜索方法——搜索的不穩定性
  • 下一篇 局面評估函數——簡介()
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果