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