亞馬遜棋中評估函數(shù)的研究

陳萱華 楊玲

摘要：機器博弈是人工智能的重要領域，國內(nèi)外普遍采用棋類作為研究機器博弈技術的載體。以亞馬遜棋為載體，總結了實現(xiàn)亞馬遜棋機器博弈的幾個基本部分，并著重對亞馬遜棋對局中用于評定招法優(yōu)劣的評估函數(shù)做了初步研究。在處理評估函數(shù)時用到了領地評估特征territory、位置特征position、靈活度特征mobility三個評估特征，并提出使用關于回合數(shù)的一次函數(shù)加權的計算模型，最后通過實驗進行了調(diào)參和檢驗。

關鍵詞：亞馬遜棋；評估函數(shù)；territory；position；mobility

中圖分類號：TP312 文獻標識碼：A

文章編號：1009-3044（2019）08-0224-03

開放科學（資源服務）標識碼（OSID）：

Research on Evaluation Function for the Game of Amazons

CHEN Xuan-hua1， YANG Ling2

（1.China Coast Guard Academy， Ningbo 315801， China； 2. Special Police College of the Chinese Peoples Armed Police Force， Beijing 102211， China）

Abstract： Machine game is an important field of artificial intelligence. Chess is widely used as the carrier of machine game technology at home and abroad. Taking the computer-game of Amazons as the carrier， this paper summarizes several basic parts of the realization of Amazons computer-game， and focuses on the preliminary study of the evaluation function of Amazons game for evaluating the merits and demerits of tactics. In dealing with the evaluation function， three evaluation features which are include territory， position and mobility are used. A weighted calculation model of the first-order function about the number of rounds is proposed. Finally， the parameters are adjusted and tested by experiments.

Key words： Amazons； evaluation function； territory； position； mobility

1 背景

亞馬遜棋是由阿根廷沃爾特Zamkauskas于1988 年發(fā)明的雙人抽象策略游戲，由國際象棋中的皇后走法衍生而來，策略和思路又類似中國圍棋中的圈地，其中的機器下棋部分用到計算機博弈技術來實現(xiàn)，且屬于完全信息動態(tài)博弈。

本文總結了實現(xiàn)亞馬遜棋機器博弈的幾個基本部分，并著重對亞馬遜棋對局中用于評定招法優(yōu)劣的評估函數(shù)做了初步研究。

2 亞馬遜棋的基本內(nèi)容

2.1 游戲規(guī)則

棋盤是n*n（比賽時通常采用10*10）的方格，分為黑白兩方，雙方各有四子，黑色在上、白色在下；游戲開始后雙方輪流行棋，黑方先行，每一輪中雙方行棋都必須完成走棋、設置障礙（放箭）兩個步驟。走棋原則是雙方的八個棋子都類似國際象棋中的皇后，可以向橫、豎、斜對角八個方向移動若干個格子，但不能穿過棋子和障礙，也不能吃子。一輪中一方只能移動一個棋子，完成走棋后，由移動的棋子在落子的棋位上開始設置障礙，障礙又稱為“箭”，障礙的釋放方式和走棋方式相同。當某一方完成某次移動后，對方的四個棋子均不能移動時，系統(tǒng)判定對方輸?shù)粼摼直荣悺?/p>

2.2 實現(xiàn)亞馬遜棋機器博弈的基本部分

亞馬遜棋機器博弈的基本部分包括：棋局表示、招法生成、招法搜索、評估函數(shù)。其中對博弈樹的招法搜索以及通過評估函數(shù)計算博弈樹節(jié)點的估值是機器博弈的核心。

棋局表示包括局面上的雙方棋子走動、設置障礙等，可以用一個n*n（10*10）的二維數(shù)組表示，將黑方棋子、白方棋子、障礙、空格設定不同的表示記錄下來即可，程序通過它來獲取當前博弈的狀態(tài)。

招法生成是產(chǎn)生在當前局面下某一方落子、設置障礙的可行方法，“可行”通過下棋規(guī)則來進行描述，確保雙方博弈公平公正地進行，當行棋不符合游戲規(guī)則時系統(tǒng)將判決“非法棋步”并發(fā)出提醒或直接判輸，基于游戲規(guī)則，一個完整的招法應該至少包括三個數(shù)據(jù)：起點、終點、障礙放置點。

招法搜索用于在生成的所有可行招法中利用評估函數(shù)找到最優(yōu)招法，是實現(xiàn)亞馬遜棋中機器博弈的重要部分，體現(xiàn)了人類思考的模式，可以使用極大極小算法、alpha-beta剪枝等各種剪枝算法，并可嘗試搜兩層、搜三層統(tǒng)計搜索準確性和搜索時間[1]。

評估函數(shù)體現(xiàn)了執(zhí)棋方在模擬某個招法后棋局的優(yōu)劣，使得程序不需要一直深度模擬至游戲結束，用于在搜索到的所有可行招法中找到最優(yōu)招法，因此，評估函數(shù)是亞馬遜棋機器博弈中非常重要的部分，評估函數(shù)的好壞很大程度上決定了搜索的準確性，影響到棋局的勝敗。

3 評估函數(shù)

亞馬遜棋的規(guī)則涉及四個子、皇后的行棋方式、走棋、設置障礙（放箭）等，這使得亞馬遜棋不同局面下每一步的可行走法數(shù)量十分龐大，平均在1000多種左右，第一步有2176種可行走法，大大提高了游戲的復雜程度。因此，我們需要用評估函數(shù)對搜索到的所有可行招法進行估值，據(jù)此選出最優(yōu)招法。

在亞馬遜棋博弈中，因為最終目的是使得對方無棋可走，所以在局面對峙過程中要盡可能的較對方圈得更大的地，一般針對己方和對方考慮以下兩種策略：針對己方采取策略圈的策略，圈占領地，通過障礙設置等使己方棋子擁有較大的領地而對方無法進入該領地，即擴大己方領地；針對對方采取策略堵的策略，將對方的棋子堵在空格數(shù)很小的范圍內(nèi)，即限制對方領地。當棋局進入一定的時期（比如18個回合之后），雙方棋子都已經(jīng)被限制在各自的領地中了，此時雙方的行棋將互相無法對對方產(chǎn)生影響，雙方棋子互不干擾地各自在己方領地中行棋至游戲結束。采用上述兩種策略后，圈得領地較少的一方會先走完（放置障礙）所有的空格，輸?shù)舯荣?。這兩種策略在評估函數(shù)中具體體現(xiàn)為領地評估特征territory、位置特征position和靈活度特征mobility。

3.1 Queen走法和King走法

Queen走法是按照國際象棋中的皇后走法，可以向橫豎斜對角八個方向走直線，只要路徑上沒有障礙就可以沿直線一直走；king走法則是按照國際象棋中的國王走法，即只能向八個方向走一格。棋子的走法和放箭都采用Queen走法。[2]

3.2 Territory值

territory值分為tq和tk兩個。tq代表用queen走法圈的領地數(shù)量，相應的，tk代表用king走法圈的領地數(shù)量，結合考慮king走法的意義，tk其實就是某一方對某個格子周圍一圈（相鄰8個格子）的控制權大小。

計算某一方的territory值時，需要分兩步進行，第一步：得到棋局中雙方對每個棋子的控制權；第二步：通過控制權大小比較分析雙方領地并按照公式得到territory值。此處只對基于queen走法的tq進行分析，tk同理。

針對棋盤上的任意一個空格，用queenmove來表示某一方通過queen走法走到這個格子需要的最小步數(shù)，即某一方四個棋子走到該格需要的四個最小步數(shù)中的最小值。計算雙方的queenmove值，queenmove值小的一方獲得對該格的控制權，此時該方較另一方需要更少的步數(shù)即可到達該格。

某一格對territory值的貢獻分為五種情況：（1）雙方到達該格的步數(shù)相同（包含都走不到的情況），該格貢獻值記為equal，equal為一個定值，因為這種情況下先行方占據(jù)主動權，所以equal取正值，筆者取為+0.5，可根據(jù)實際情況進行調(diào)整；（2）雙方都可以到達，且執(zhí)棋方的queenmove值小（到達所需步數(shù)少），執(zhí)棋方對該格控制權更大，貢獻值記為1；（3）雙方都可以到達，且執(zhí)棋方的queenmove值大（到達所需步數(shù)多），對方對該格控制權更大，貢獻值記為-1；（4）執(zhí)棋方可以到達，而對方無法到達，該格直接歸屬執(zhí)棋方，貢獻值記為2；（5）對方可以到達，而執(zhí)棋方無法到達，該格直接歸屬對方，貢獻值記為-2。

3.3 Position值

position值是在territory的基礎上進一步計算對某個格子雙方控制權的差值，代表通過控制權差異反映出的雙方棋子的地理位置優(yōu)劣，同樣分為基于queen走法的p1和基于king走法的p2。此處不進行詳細分析，直接給出參考文獻[3]中公式實現(xiàn)的具體代碼。

for （int i = 0； i < n； ++i）

for （int j = 0； j < n； ++j）

//myQueenmove表示行棋方的，yourQueenmove表示對方的

if （myQueenmove [i][j] == yourQueenmove[i][j]） continue；

else if （myQueenmove [i][j] == inf） p1 += -pow（2.0， -yourQueenmove [i][j]）；

else if （yourQueenmove [i][j] == inf） p1 += pow（2.0， -myQueenmove [i][j]）；

else p1 += pow（2.0， -myQueenmove [i][j]） - pow（2.0， -yourQueenmovee[i][j]）；

p1 = 2 * p1；

for （i = 0； i < n； ++i）

for （j = 0； j < n； ++j）

p2 += min（1.0， max（-1.0， （double）（yourQueenmove[i][j] - myQueenmove[i][j]） / 6.0））；

3.4 mobility值

mobility，意為靈活度，棋子的靈活度反映了棋子在八個方向上移動的靈活性大小。棋盤上的每個空格都有自己的靈活度值，而棋子的靈活度值取決于它能到達的空格的靈活度值。

文獻[4-5]中空格靈活度的計算方式如下，針對某一空格，該空格通過queen走法走一步能到達的空格數(shù)記為它的靈活度?？崭竦撵`活度值除以該棋子按照king走法走到該空格所需的最小步數(shù)（kingmove）得到該空格對該棋子靈活度值的貢獻值，將棋子通過queen走法能走到的所有空格的靈活度貢獻值相加，就得到了該棋子的靈活度值。一方四個棋子的靈活度值之和即該方的靈活度值，將雙方靈活度值作差就得到了棋局評估所需的靈活度值。

由于在實際操作過程中，在每一局面下都要計算一遍棋盤所有空格靈活度和kingmove，花費的時間太多，于是我們將棋子靈活度的計算方式改為棋子按照queen走法走一步的所有可行招法數(shù)目，而評估函數(shù)中所需的靈活度值改為雙方靈活度值的比值，其中對方（除數(shù)方）的靈活度值加上0.00001，用意在于防止對方棋子出現(xiàn)被堵死的情況導致除數(shù)為零，同時，使用比值而非差值，可以防止開局階段靈活度值過大的情況，更能在出現(xiàn)對方被堵死的情況下使靈活度值很大，使行棋方直接選擇這一招法將對方堵死。

4 評估函數(shù)的計算公式

評估函數(shù)的計算公式為value=k1（turnID）*tq+k2（turnID）*tk+k3（turnID）*p1+k4 （turnID）*p2+k5（turnID）*mobility，其中k1～k5都是關于turnID的一次函數(shù)，用于給要素加權，需要通過對局進行調(diào)參。

4.1 要素占比變化情況

turnID代表當前進行到的回合數(shù)，隨著對局的進行，每個要素對棋局的影響會發(fā)生不同的變化。

開局階段棋盤上主要都是空格，障礙很少，走法幾乎不受限制，此時雙方對空格的控制權相差不大，所以tq占比不是很大；而此時需要開始圈地并盡可能防止對方棋子攻占我方棋子附近的格子，因此，評估我方棋子附近圈地能力的tk占比較大。但隨著棋局向中局發(fā)展，局面上的障礙越來越多，雙方對空格的控制權大小差異逐漸增大，tq在整體估值中的重要性不斷增加，占比越來越大。

當棋局行進至殘局階段，棋盤基本上已經(jīng)被完全分割為多個獨立的區(qū)域，而棋盤上的空格都直接歸屬某一方，tq的占比非常大，由于此時領地已經(jīng)不可能被對方進犯，tk的占比降到最低。

p1、p2反映的位置優(yōu)劣在開局的時候占比較大，因為這個階段需要將棋下得分布均勻，而當棋局進行到中局、殘局，棋盤已經(jīng)被分割開，不再需要考慮位置的優(yōu)劣來使棋子分布均勻了。

mobility同樣也是在開局占比大，隨著棋局進行，局面分割，所占比重越來越小。

因此，在棋局進行到一定程度（通過turnID衡量）后，為了計算方便，我們直接將tq值當作整體的value值。用于給棋局程度分界的turnID值也可以通過不斷嘗試、觀察對局并統(tǒng)計來得到。

4.2 具體實現(xiàn)

鑒于這些要素不同的變化情況，考慮使用關于turnID（回合數(shù)）的一次函數(shù)為要素進行加權，具體數(shù)值通過統(tǒng)計對局結果調(diào)參可得。筆者在棋局上調(diào)參得到的具體公式如下：

if （turnID < 17） {//在第1～16個回合內(nèi)

k1 = 2 * （32 + 2.0 * turnID/2）；

k2 = 1 * （32 - 1.8 * turnID/2）；

k3 = 1 * （32 - 1.8 * turnID/2）；

k4 = 2 * （32 - 2.0 * turnID/2）；

k5 = 0.5 * （32 - 1.8 * turnID/2）；

}

else {//在經(jīng)過了16個回合之后

k1 = 5；

k2 = k3 = k4 = k5 = 0；

}

value = k1 * tq + k2 * tk + k3 * p1 + k4 * p2 + k5 * mobility；

而在具體實現(xiàn)過程中，由于對局中出現(xiàn)了棋子在開局初期就走到邊界的情況，使得局面變得不利，因此，在開局、中局和殘局等不同的階段最好設置不同的參數(shù)。筆者通過在程序中強制設定開局幾步中棋子不得走到邊界處來解決這個問題。此外，在設計界面上還可以自行添加各種功能，如悔棋等。

5 結束語

本文完成了實現(xiàn)亞馬遜棋的基本部分，并較為深入地分析了其中非常重要的評估函數(shù)，通過策略圈和策略堵兩方面提出territory、position、mobility幾個要素，更進一步地探討了這些要素隨著棋局進行的不同變化，由此得出使用關于回合數(shù)的一次函數(shù)進行加權。同時，所有給出的參數(shù)都只是來源于一小部分實驗，需要優(yōu)化；幾個評估特征的具體確定也可以進一步完善，可以考慮加入新的評估特征。

參考文獻：

[1] 張柳. 基于極大極小搜索算法的亞馬遜棋博弈系統(tǒng)的研究[D]. 沈陽： 東北大學， 2010.

[2] 喬治， 黃鴻. 亞馬遜棋博弈技術研究[C]. 北京： 中國人工智能學會， 2013.

[3] Jens Lieberum. An evaluation function for the game of amazons[J]. Theoretical Computer Science 349， 2005： 232-234.

[4] 郭琴琴， 李淑琴， 包華. 亞馬遜棋機器博弈系統(tǒng)中評估函數(shù)的研究[J]. 計算機工程與應用， 2012， 48（34）： 51-53.

[5] 王靜文， 吳曉藝. 全國大學生計算機博弈大賽培訓教程[M]. 北京： 清華大學出版社， 2013.

【通聯(lián)編輯：謝媛媛】