李卓軒 李媛 冉冠陽 王靜文

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ī)則和復雜度均介于圍棋和國際象棋之間。由于亞馬遜棋類設計中含有較大的分支因子，使其非常適合于搜索算法的研究。亞馬遜棋的棋盤構成則如圖1所示。

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

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

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

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

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

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

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

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

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

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

1基于PVS算法的搜索引擎

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

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

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

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

2實驗與分析

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

2.1勝負比較

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

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

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

2.2節(jié)點比較

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

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

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

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

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

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

3結(jié)束語

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

參考文獻

[1] 郭琴琴，李淑琴，包華. 亞馬遜棋機器博弈系統(tǒng)中評估函數(shù)的研究[J]. 計算機工程與應用，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.