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

李卓軒 李媛 冉冠陽 王靜文

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.

引言

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

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

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

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

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

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

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

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

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

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

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

1基于PVS算法的搜索引擎

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

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

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

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

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

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

2.1勝負(fù)比較

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

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

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

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

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

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

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

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

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

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

3結(jié)束語

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

參考文獻(xiàn)

[1] 郭琴琴，李淑琴，包華. 亞馬遜棋機(jī)器博弈系統(tǒ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.