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)四 炮３進(jìn)１
2.炮五進(jìn)一 炮３進(jìn)１
3.炮五進(jìn)一 炮３進(jìn)１
4.炮五進(jìn)一 炮３進(jìn)１
5.炮五進(jìn)一 炮３退１
若黑走炮３平５，則仕五進(jìn)六、前炮平２、炮七平五做殺無解(若黑走炮２平５解殺則構(gòu)成長將)。
6.炮七進(jìn)一 炮３退１
7.炮七進(jìn)一 炮３退１
8.炮七進(jìn)一 炮３退１
9.炮七進(jìn)一 卒６平７
10.帥五平四 卒７進(jìn)１
11.帥四進(jìn)一 卒７平８
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培训机构该怎么选择？