基于PVS搜索算法的亞馬遜棋博弈系統(tǒng)的設(shè)計(jì)

李卓軒 李媛 冉冠陽(yáng) 王靜文

Abstract： The game of the Amazons is a game in which the complexity stands between the game of Go and Chinese Chess. Because of the huge branching factor， it is difficult to reach higher depth in the search process.Combined with heuristic and hash technology， this paper uses the PVS algorithm， and greatly improves the pruning efficiency and the search depth. The Amazons game software developed by this technology has improved the game level effectively.

引言

亞馬遜棋是一種頗受歡迎的較新的棋盤(pán)類(lèi)游戲，其行棋規(guī)則和復(fù)雜度均介于圍棋和國(guó)際象棋之間。由于亞馬遜棋類(lèi)設(shè)計(jì)中含有較大的分支因子，使其非常適合于搜索算法的研究。亞馬遜棋的棋盤(pán)構(gòu)成則如圖1所示。

研究中，將給出亞馬遜棋的布棋規(guī)則可表述如下。

（1）在10×10的棋盤(pán)上紅方（白方）在A4、D1、 G1和 J4位置上擺放白方4個(gè)皇后，藍(lán)方（或黑方）在A7、 D10、G10和 J7位置上擺放黑方4個(gè)皇后。

（2）皇后可走棋的位置與國(guó)際象棋皇后走法的規(guī)則相同。

（3）由紅方（或白方）開(kāi)始游戲，每輪下棋由2步組成：

① 移動(dòng)擺放皇后位置，規(guī)則和國(guó)際象棋皇后走棋的規(guī)則相同。

② 落子后以當(dāng)前皇后位置為基點(diǎn)設(shè)置障礙，障礙擺放點(diǎn)的位置和皇后可擺放點(diǎn)的位置相同（兩者使用的規(guī)則相同）。

（4）皇后和障礙設(shè)置的線路上不得有其它棋子或障礙。

（5）可以完成最后一步的一方為贏家。

根據(jù)亞馬遜棋的規(guī)則計(jì)算，亞馬遜棋的平均分支因子達(dá)到17 000左右。與圍棋相比，僅僅只是表現(xiàn)在規(guī)則相對(duì)簡(jiǎn)單，及搜索深度相對(duì)較小。因此，非常適合搜索算法的研究。

亞馬遜棋的博弈系統(tǒng)主要由估值和搜索兩大部分組成，在本文中所用的估值研究包含3個(gè)方面，分別是：靈活度、位置和領(lǐng)域[1-2]，本文探討的主要內(nèi)容則為搜索算法，對(duì)其詳述如下。

1基于PVS算法的搜索引擎

研究可知，由于亞馬遜棋的較高復(fù)雜度，將使其難于達(dá)到較高的搜索效率。目前，常用的方法有UCTS算法[3]、哈密爾頓環(huán)方法[4]等。其中，UCTS算法可以獲得較高的搜索深度，但估值的精確性較差，而相對(duì)來(lái)說(shuō)，哈密爾頓環(huán)的執(zhí)行效率卻會(huì)偏低。

本文采用的是基于PVS算法的搜索引擎，結(jié)合Amazons棋的特點(diǎn)，并且引入置換表技術(shù)和歷史啟發(fā)技術(shù)，該次研究旨在獲得較高的搜索效率，同時(shí)能夠?qū)置孢M(jìn)行準(zhǔn)確估值。

PVS是alpha-beta剪枝搜索算法的一個(gè)變種算法，其設(shè)計(jì)重點(diǎn)在于除主變量節(jié)點(diǎn)外的其它所有節(jié)點(diǎn)都用一個(gè)零窗口（alpha，beta）且alpha=beta 進(jìn)行搜索，遵循理念就是對(duì)淺層的節(jié)點(diǎn)進(jìn)行整理使其基本有序，并假設(shè)第一個(gè)節(jié)點(diǎn)是最好的，作為主變量，展開(kāi)全窗口搜索。通過(guò)零窗口搜索其它節(jié)點(diǎn)，判斷是否存在一些節(jié)點(diǎn)會(huì)比當(dāng)前最優(yōu)值更好。如果符合alpha-beta剪枝則進(jìn)行剪枝，假若失敗則證明當(dāng)初的節(jié)點(diǎn)不是主變量，即需對(duì)當(dāng)前節(jié)點(diǎn)重新發(fā)起一次全窗口搜索，作為新的主變量。本文結(jié)合了歷史啟發(fā)增強(qiáng)和置換表技術(shù)，確保了搜索效率及速度。

置換表技術(shù)用于在搜索到結(jié)果的情況下記錄最好的評(píng)分和方法，并在下一次搜索中直接返回相同的情況，大大提高了搜索效率。通常一個(gè)局面經(jīng)搜索被判定為較好時(shí)，在其后繼結(jié)點(diǎn)中往往有一些相似的局面也是較好的。歷史啟發(fā)就是建立在這樣一種論點(diǎn)之上的。在搜索過(guò)程中，每當(dāng)找到好的行棋方式時(shí)，加入一個(gè)增量來(lái)記錄其歷史分?jǐn)?shù)，而經(jīng)多次搜索均認(rèn)定為是好方式的歷史分?jǐn)?shù)即會(huì)更高。對(duì)于即將到來(lái)的節(jié)點(diǎn)，可根據(jù)歷史評(píng)分進(jìn)行排序。如此一來(lái)，更好的行走方法（歷史評(píng)分行棋方法）就可位列在前面，從而確保搜索的效率。

2實(shí)驗(yàn)與分析

博弈系統(tǒng)的性能可以從勝負(fù)和訪問(wèn)的節(jié)點(diǎn)數(shù)這2個(gè)方面進(jìn)行比較。對(duì)此可闡釋分述如下。

2.1勝負(fù)比較

勝負(fù)上的比較是對(duì)博弈系統(tǒng)棋力水平的直觀呈現(xiàn)。因?yàn)槊總€(gè)博弈系統(tǒng)的最終目的便是證實(shí)自己具有較高的棋力水平。在相同限制條件下進(jìn)行博弈，就可有效評(píng)判該博弈系統(tǒng)的水平高低。

首先雙方博弈系統(tǒng)基于同一個(gè)估值函數(shù)，將PVS搜索迭代時(shí)間限定在1 s，將alpha-beta剪枝搜索算法的最大深度限定在11層。然后設(shè)置基于PVS算法的博弈系統(tǒng)為先手，alpha-beta剪枝算法為后手，對(duì)弈一定局?jǐn)?shù)以后，先、后手互換。接著為PVS算法的博弈系統(tǒng)設(shè)置一個(gè)隨機(jī)的開(kāi)局，開(kāi)始雙方搏殺對(duì)弈，這些隨機(jī)的開(kāi)局將會(huì)為基于PVS算法的博弈系統(tǒng)造成一些難度。實(shí)驗(yàn)運(yùn)行后，可以得到PVS算法的博弈系統(tǒng)勝率可參見(jiàn)表1。

由表1可知，基于PVS算法的博弈系統(tǒng)在棋力上遠(yuǎn)勝于基于alpha-beta算法的效果表現(xiàn)。雙方基于相同的估值算法，從棋力角度說(shuō)明PVS算法更適用于亞馬遜棋。

2.2節(jié)點(diǎn)比較

訪問(wèn)節(jié)點(diǎn)數(shù)上的比較反映了搜索算法在時(shí)間上的消耗，在公平的限制條件下，也折射出搜索算法在這個(gè)博弈游戲中的優(yōu)劣。

本文通過(guò)6次函數(shù)擬合了訪問(wèn)節(jié)點(diǎn)_行棋回合函數(shù)。通過(guò)對(duì)圖表的處理分析，在公平的博弈條件限制下，PVS算法訪問(wèn)的節(jié)點(diǎn)數(shù)遠(yuǎn)超過(guò)了alpha-beta算法的最終統(tǒng)計(jì)數(shù)值。PVS算法的訪問(wèn)節(jié)點(diǎn)_行棋回合函數(shù)則如圖2所示。

由圖2中擬合的函數(shù)曲線可知，PVS算法所訪問(wèn)的節(jié)點(diǎn)在進(jìn)入殘局階段前是隨行棋過(guò)程逐漸增加，直至終局階段訪問(wèn)節(jié)點(diǎn)的顯著提速下降。

alpha-beta算法的訪問(wèn)節(jié)點(diǎn)_行棋回合函數(shù)則如圖3所示。

由圖3中擬合的函數(shù)曲線可知，alpha-beta算法所訪問(wèn)的節(jié)點(diǎn)在開(kāi)局階段是隨行棋過(guò)程逐漸增加，行棋到中局階段訪問(wèn)的節(jié)點(diǎn)數(shù)開(kāi)始下降，并一直持續(xù)至博弈終止。

通過(guò)研究后對(duì)比可知，PVS訪問(wèn)的葉子節(jié)點(diǎn)數(shù)遠(yuǎn)多于alpha-beta算法。究其原因即在于alpha-beta算法產(chǎn)生了很多剪枝，搜索的葉子節(jié)點(diǎn)遠(yuǎn)遠(yuǎn)少于整棵樹(shù)的葉子節(jié)點(diǎn)，對(duì)于亞馬遜棋這類(lèi)走法過(guò)多、尤其開(kāi)局階段會(huì)有1 000多種走法的博弈游戲來(lái)說(shuō)，并不適用。故而，在此方面，PVS算法明顯占優(yōu)。

3結(jié)束語(yǔ)

本文通過(guò)1 000多輪的對(duì)弈比較，利用6次函數(shù)去擬合訪問(wèn)節(jié)點(diǎn)_行棋回合函數(shù)，隨即又設(shè)計(jì)做出了擬合后的函數(shù)圖像，通過(guò)圖像比較了2種搜索算法在這個(gè)博弈游戲中的優(yōu)劣。最終結(jié)果表明，PVS算法在開(kāi)局階段與alpha-beta算法相比并未占優(yōu)領(lǐng)先，但是隨著棋局的深入，算法優(yōu)勢(shì)逐漸突出，在終局階段其優(yōu)勢(shì)則更加明顯，由此研發(fā)獲得的亞馬遜棋博弈系統(tǒng)也將具有較高水平。

參考文獻(xiàn)

[1] 郭琴琴，李淑琴，包華. 亞馬遜棋機(jī)器博弈系統(tǒng)中評(píng)估函數(shù)的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2012，48（34）：50-54，87.

[2] LIEBERUM J. An evaluation function for the game of Amazons[J]. Theoretical Computer Science， 2005，349（2）：230-244.

[3] KLOETZER J. Monte-Carlo opening books for Amazons[C]//International Conference on Computers and Games. Berlin/Heidelberg： Springer-Verlag， 2011：124-135.

[4] BURO M. Michael Buro. Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid Graphs[C]// International Conference on Computers and Games. Berlin/Heidelberg： Springer-Verlag， 2000：250-261.