基于Alpha－Beta 算法的蘇拉卡爾塔棋博弈系統(tǒng)研究

李東軒， 胡 偉， 王靜文

（沈陽工業(yè)大學 理學院， 沈陽 110870）

0 引 言

計算機博弈（Computer Games），亦稱機器博弈，是一個挑戰(zhàn)無窮、生機勃勃的研究領域。 隨著人工智能的興起，人們對計算機博弈的研究日趨深入，計算機博弈算法也已越來越多地被應用在各棋種上。

由于蘇拉卡爾塔棋的棋盤比較特殊，且規(guī)則有趣，走法多變，近年來受到許多機器博弈愛好者的關注，因此本文對此進行了深入研究。

1 蘇拉卡爾塔棋簡介

蘇拉卡爾塔是雙人游戲， 源自于印尼爪哇島的蘇拉卡塔（Surakarta） 。 棋盤由6×6 正方形網(wǎng)絡與角落上的8 個圓弧所組成，如圖1 所示。 棋子在游戲開始時，雙方各12 個棋子排成兩行。 其游戲規(guī)則如下：

圖1 蘇拉卡爾塔棋棋盤Fig.1 The board of Surakarta

（1）參賽者擲硬幣決定開始，每次只能移動一個棋子，雙方輪流走棋；

（2）每個棋子可以向8 個方向（上、下、左、右、左上、左下、右上、右下）移動一格（所去方向無棋子）；

（3）若要吃掉對方棋子，必須經(jīng)過至少一個完整的弧線，并且移動路徑中不可有本方棋子阻擋；

（4）黑子可以吃掉白子，同樣白子沿同一路徑的相反方向也可以吃掉黑子；

（5）當一方棋子全部被吃掉時棋局結束，有剩余棋子方獲勝；

（6）當雙方都不能再吃掉對方棋子時，剩余棋子多的一方獲勝。

2 蘇拉卡爾塔棋博弈系統(tǒng)

蘇拉卡爾塔棋博弈系統(tǒng)主要由可下位置的生成、估值函數(shù)、“三手進攻”算法與搜索算法相結合三部分構成。 其中，可下位置的生成需在給出當前局面時，迅速得到所有的可下位置，這與搜索算法的深度密切相關；估值函數(shù)需要準確的評估當前局面；搜索算法需要通過可下位置和估值函數(shù)，從而獲得最佳下棋位置。

2.1 可下位置的生成

在蘇拉卡爾塔棋博弈系統(tǒng)中，可下位置即棋子合法的移動位置。 通常情況，可下位置的生成方法需要遍歷兩邊棋盤，不斷地將棋子設為移動的起點和終點，并判斷該走法是否合法。 該方法需要遍歷兩邊棋盤，因此空間復雜度較高，搜索速度較慢。 由此可見，可下位置生成的速度尤為重要，關乎到搜索算法的深度及棋力。

關于生成可下位置的優(yōu)化基本思路：將棋盤中本方棋子設為移動的起點，然后在軌道中尋找其可落子的位置。 具體算法如下：

棋子可移動位置分為吃子移動和不吃子移動。不吃子移動的可下位置易于實現(xiàn)，只需在本方棋子周圍尋找即可；而吃子移動的可下位置較為繁瑣。在初始化棋盤中，將內(nèi)軌和外軌的位置分別存放到兩個向量中；之后首先找到本方棋子，判斷其在內(nèi)軌道還是外軌，或者是內(nèi)外軌道都在。 在內(nèi)、外軌道時分為兩種情況：一是在特殊點上（如圖2 所示）；二是不在特殊點上。 如果棋子不在特殊點，那么在軌道向量中找到棋子的位置，分別向上或向下找到對方的棋子，再判斷是否過弧而生成可下位置；如果棋子在特殊點上，棋子的位置在軌道向量中將會出現(xiàn)兩次，分別找到這兩次的位置并按上述方法生成可下位置。

圖2 特殊點位置Fig.2 Special point location

2.2 估值函數(shù)

由于蘇拉卡爾塔棋最終勝負判斷的方法是將對方的棋子全部吃完，或死棋時計算剩余棋子的個數(shù)，因此本文評估函數(shù)采用對盤面賦值（Value－1）與棋子數(shù)量（Value－2）相結合的策略。

2.2.1 盤面賦值（Value－1）

依據(jù)蘇拉卡爾塔棋的棋盤，可見許多價值比較高的點位。 即在占領該類點位時，勝率會明顯增高，故將不同位置的棋子評分，可得出各點價值對應的棋盤價值矩陣。 即：

2.2.2 棋子數(shù)量（Value－2）

棋子數(shù)量為當前下棋方的棋子個數(shù)。 一般情況下，剩余越多，優(yōu)勢越大。

綜合考慮上述兩方面，可以得出本方（黑方）總估值函數(shù)：

Value ＝Black－Value－Total－White－Value－Total

對方總估值函數(shù)White－Value－Total 同理。 最后計算出當前局面的價值：

Evalue ＝Black－Value－Total－White－value－Total

2.3 “三手進攻”開局與搜索算法相結合

蘇拉卡爾塔棋中有多種開局方法，經(jīng)過大量測試后，得出了先手方最優(yōu)的幾種進攻方式－－－“三手進攻”，如圖3 所示。 所謂“三手進攻”，就是用3 步把棋盤中的外圈軌道（或內(nèi)圈軌道）中的外?。▋?nèi)弧）“打開”，使己方棋子在占據(jù)最優(yōu)位置的同時，能夠利用最快的步驟吃掉對方的棋子，并在后期內(nèi)圈（外圈）軌道相互“換子”時，己方棋子會比敵方棋子多出一個，使得己方在殘局時，徹底占領內(nèi)圈（外圈）軌道，達到優(yōu)勢最大化。 己為后手方時，利用更深的搜索算法進行“防守”，當敵方中期有破綻時轉守為攻。

圖3 三手進攻走法Fig.3 Three steps attack method

2.4 Alpha－Beta 搜索算法

目前，關于蘇拉卡爾塔棋搜索效率較高的算法有Alpha－Beta 算法和UCT 算法。 但是，由于每步棋的可下位置較少，所以利用好估值函數(shù)時，Alpha－Beta 算法會更加精準。 Alpha－Beta 算法是由極大極小算法改變而來，兩者的區(qū)別在于Alpha－Beta 算法可以不斷的進行“剪枝”，將價值不高的局面剔除，進而提高搜索效率。 博弈系統(tǒng)中還使用了置換表和哈希表技術制作開局庫，通過計算當前局面的哈希值，再進入開局庫中查找是否存在，極大地提高了開局搜索效率。 Alpha－Beta 偽碼如下：

Function Alpha－Beta（int，int alpha，int）｛

if（0‖isWin（））

return value （）

getPositions

for（i ＝1 to getPositions.size（））

makeMove（）

val ＝－Alpha－Beta（1，，－alpha）

unMakeMove（）

if（val ＞＝）

return

if（）

return

｝

3 實驗與結果

針對蘇拉卡爾塔棋優(yōu)化后的可下位置搜索速度與普通版本（搜索層數(shù)均為7 層）搜索速度結果見表1。

表1 生成可下位置對比結果Tab.1 Comparison of different generated downloadable location algorithm

由表1 可明顯看出，運用Alpha－Beta 搜索算法搜索7 層時，優(yōu)化后的可下位置生成算法相比于普通算法，可以大大減少搜索時間，極大的提高了搜索效率。

針對蘇拉卡爾塔棋的估值，本文使用了棋盤估值Evalue 和Value－2，進行了Alpha－Beta 搜索算法，搜索層數(shù)為7 層時進行互相博弈比較。 比較結果見表2。

表2 不同的估值對比結果Tab.2 Comparison results of different valuations

由表2 可以看出，不同估值在同一算法下的勝率，在先后手上進行博弈時，Evalue 的估值在先后手全都取得了勝利，證明了該估值的可行性。

4 結束語

本文通過使用Alpha－Beta 搜索算法和優(yōu)化后的可下位置生成算法與普通可下位置生成算法相比較，結果表明：優(yōu)化后的位置生成算法在限制時間的比賽中有更好的搜索效率。 同時，在本博弈系統(tǒng)中加入了“三手進攻”策略和置換表與哈希表技術、迭代加深方法，并結合估值方法，極大地提高了棋力。使用本文提出的算法與策略完成的蘇拉卡爾塔棋博弈程序，在2021 年全國大學生計算機博弈競賽中取得了亞軍的好成績，再次證明了該算法的可行性。