徐志凡，王靜文，李 媛

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

0 引 言

博弈是一種對策行為，廣泛存在于社會生活的各個方面，而博弈論主要研究博弈行為中最優(yōu)的對抗策略，協(xié)助人們在一定規(guī)則內(nèi)尋找最適合的行為方式，因此在政治、經(jīng)濟(jì)、軍事、外交等領(lǐng)域可以應(yīng)用到博弈論。機(jī)器博弈是各個領(lǐng)域博弈理論的起源與基礎(chǔ)，其作為人工智能領(lǐng)域的一個重要研究方向，不僅是許多人工智能領(lǐng)域的基礎(chǔ)，而且被視為最具挑戰(zhàn)性的研究方向之一。機(jī)器博弈的核心為建立決策與選擇決策，建立決策指在給定規(guī)則中將所有可采取的策略建成策略集，選擇決策指在策略集中選擇一個最佳策略。因此，兩者成為了機(jī)器博弈研究的主要內(nèi)容。

Hex棋不僅是國際計算機(jī)奧林匹克錦標(biāo)賽的項目，自2016年起也成為中國計算機(jī)博弈錦標(biāo)賽的比賽項目。由于Hex棋規(guī)則簡單、易懂，但是選擇決策至關(guān)重要，因此吸引了越來越多的計算機(jī)博弈愛好者的關(guān)注與研究。

1 Hex棋簡介

Hex棋又名六角棋，譯作?？怂蛊?，是一種二人添子類零和游戲。

典型的棋盤由11×11的六邊形格子組成，上下兩個邊界線為紅色，左右兩個邊界線為藍(lán)色，紅色（橫向）坐標(biāo)表示范圍A-K，藍(lán)色（縱向）坐標(biāo)表示范圍1-11，如圖1所示。棋子為紅與藍(lán)兩種顏色的圓形棋子，對弈雙方各執(zhí)一種顏色棋子。

Hex棋的對弈規(guī)則：雙方輪流下棋且紅方先手，可以將己方棋子下到任意空閑的格子中，同種顏色的棋子相連則認(rèn)為其相互連接，任意一方將該方顏色的兩個邊界用相同顏色棋子連接，視為勝利，例如圖1中紅方獲勝。

圖1 Hex棋棋盤Fig.1 The chess board of Hex

2 Hex棋博弈系統(tǒng)

計算機(jī)博弈游戲其核心由搜索和估值兩部分組成，傳統(tǒng)的搜索方法為Alpha-Beta算法及其諸多變種。由于Hex棋的特殊性，估值算法不能很好的評估當(dāng)前局面，所以采用UCT搜索算法。該算法能在可控的時間內(nèi)獲取到準(zhǔn)確的結(jié)果。

2.1 UCT算法

UCT算法（Upper Confidence Bound Apply to Tree）即為上限置信區(qū)間算法，是MCTS算法（Monte Carlo Tree Search）的改進(jìn)。UCB公式（Upper Confidence Bound）最初是針對K臂賭博機(jī)問題提出來的，而UCT算法將MCTS搜索與UCB公式相結(jié)合，在大規(guī)模博弈樹的搜索過程中相對于傳統(tǒng)的搜索算法在時間和空間方面占據(jù)優(yōu)勢。UCT算法的優(yōu)勢在于工作時間可控、具有更好的魯棒性，并且搜索過程中，博弈樹以非對稱的形式動態(tài)擴(kuò)展開。UCT算法樹內(nèi)選擇的UCB公式（1）：

其中，r是樹內(nèi)選擇的評估值，選擇過程中會根據(jù)r選擇節(jié)點；v是以n為根節(jié)點的子樹的所有模擬結(jié)果的平均值，反映此節(jié)點能提供的回報值；T是節(jié)點n的訪問次數(shù)，即此節(jié)點被樹內(nèi)選擇策略選中的次數(shù)；是一個手工設(shè)定的參數(shù)，用來平衡開發(fā)與探索之間的關(guān)系。

UCT算法的執(zhí)行過程，如圖2所示。

圖2 UCT算法的執(zhí)行過程Fig.2 UCT algorithm implementation process

UCT算法的執(zhí)行過程分為4個階段：

（1）選擇階段：從根節(jié)點出發(fā)向下探索，選擇具有最大值的孩子節(jié)點，并將其作為下一次選擇的起點，直到到達(dá)葉子節(jié)點；

（2）擴(kuò)展階段：將選中的葉子節(jié)點所允許的所有可行下法作為新的葉子節(jié)點，加入到搜索樹中，并初始化值與值；

（3）模擬階段：對當(dāng)前局面進(jìn)行隨機(jī)模擬，直到棋局結(jié)束，一般情況下己方獲勝評估值取1，失敗評估值取0，通過若干次模擬后會得到新的值；

（4）反向傳播階段：當(dāng)葉子節(jié)點通過模擬獲得新的值和值時，UCT算法通過反向傳播更新搜索路徑上所有節(jié)點的值和值，公式（2）～（3）：

2.2 特殊棋型

Hex棋與許多其他棋類一樣，存在著一些特殊棋型，當(dāng)出現(xiàn)這些棋型時會存在最佳解。

（1）雙橋棋型。對角棋子同色且中間為空的棋型即為雙橋棋型，如圖3所示。無論敵方在中間哪個空位置落子，己方都可以在另一個位置落子來保證己方棋子相連。

圖3 雙橋棋型Fig.3 Double bridge pattern

（2）無用位置。如果某個位置無論被哪一方的棋子占領(lǐng)均不會對最終結(jié)果產(chǎn)生影響，則稱該位置為無用位置，如圖4所示。

圖4 無用位置Fig.4 Useless location

（3）被捕獲位置。如果某些空位置填充一方棋子均不會對最終結(jié)果產(chǎn)生影響，則稱該位置為被捕獲位置，如圖5所示。

圖5 被捕獲位置Fig.5 Captured position

（4）邊界位置。在邊界處會存在一些棋型，無論敵方下在哪個位置，己方都存在另一個位置來保證與邊界相連，則稱這些位置為邊界位置，如圖6所示。

圖6 邊界位置Fig.6 Boundary position

（5）梯子棋型。由于己方局面的某一個位置為迫切相連的位置，而敵方可以行棋在另一位置阻止此相連，并且此時己方仍存在一個迫切相連的位置，最終導(dǎo)致形成梯子形狀的棋型稱為梯子棋型，如圖7所示。

圖7 梯子棋型Fig.7 Ladder pattern

2.3 改進(jìn)的UCT算法

由于在UCT算法的模擬階段中，一般情況下的模擬是隨機(jī)選擇一種當(dāng)前局面下的可行下法，判斷局面是否獲勝，未獲勝則繼續(xù)以上過程，直到勝利2。該方法的模擬用時過長，在一定時間內(nèi)的模擬次數(shù)不理想。由于Hex獲勝的特殊性，可以得出一個簡單的結(jié)論：當(dāng)棋盤填滿時必定有一方獲勝。所以采取隨機(jī)填滿棋盤后判斷輸贏的方法，這會使模擬用時大大縮短。

由于簡單隨機(jī)模擬會使模擬結(jié)果與準(zhǔn)確結(jié)果有較大的誤差，依據(jù)Hex棋在模擬階段采用不同棋型對應(yīng)的最優(yōu)解可以提高模擬精度的特點，在模擬前采用3種策略：

（1）隨機(jī)填充雙橋。由于雙橋自身的特點，無論另一方如何行棋都能保證雙橋能夠相連，所以在模擬前隨機(jī)將雙橋位置填充，一個己方棋一個敵方棋；

（2）隨機(jī)填充無用位置與被捕獲位置。由于無用位置與被捕獲位置填上相應(yīng)的棋子不會影響最終的結(jié)果，所以在模擬前填上可以提高模擬精度；

（3）破壞敵方雙橋。如果在上一個節(jié)點己方棋子填充敵方雙橋的一個位置，且敵方并未連接其雙橋，那么己方棋子自動填充另一位置，破壞敵方雙橋。

在模擬時采用3種策略：

（1）自動連接雙橋。若一方入侵另一方的雙橋棋型，則另一方自動補(bǔ)全雙橋，保證棋子相連，防止被對面攻占；

（2）自動連接邊界。如果存在邊界棋型且敵方入侵該棋型，那么己方會自動填充相應(yīng)的棋子來保證己方與邊界相連接；

（3）自動連接梯子。由于梯子棋型的特點，有時會使己方優(yōu)勢逐漸消失，為避免對己方不利的情況，當(dāng)己方填充梯子棋型中的相應(yīng)位置時，敵方棋子自動填充另外一個棋子。按此方法則對己方不利的梯子棋型不會出現(xiàn)，能夠提高模擬準(zhǔn)確度。

3 實驗與結(jié)果

3.1 實驗環(huán)境

測試棋盤為11×11，規(guī)定實驗測試時單方限時30 min，單步限時30 s。實驗仿真環(huán)境：Window 10操作系統(tǒng)，Code：：Bloacks；測試硬件環(huán)境：Inter（R）Core（TM）i7-8700，主頻3.20 GHz，內(nèi)存為8G，顯卡NVIDIA GeForce GTX 1050Ti，六核十二線程。

3.2 選取c值

由于UCT算法中的參數(shù)是一個預(yù)先設(shè)定方參數(shù)，所以需要對值進(jìn)行優(yōu)化選取。由于Alpha-Beta算法的穩(wěn)定性，故采用UCT算法與搜索層數(shù)為3層的Alpha-Beta算法進(jìn)行測試，不同值均測試200次，先手后手各100次。優(yōu)化結(jié)果，如圖8所示。由優(yōu)化圖可以得出最優(yōu)的值為0.61。

圖8 UCT算法c值優(yōu)化圖Fig.8 UCT algorithm c value optimization diagram

3.3 實驗結(jié)果

選取搜索層數(shù)為兩層的Alpha-Beta算法與改進(jìn)后的UCT算法進(jìn)行測試，測試結(jié)果見表1。

表1 改進(jìn)UCT-Alpha-Beta對弈結(jié)果Tab.1 Result of improved UCT vs Alpha-Beta

由表1可知，改進(jìn)的UCT算法幾乎完勝兩層的Alpha-Beta算法，驗證了改進(jìn)UCT算法的優(yōu)越性。

選取改進(jìn)的UCT算法與原始的UCT算法對比。測試結(jié)果見表2。

表2 改進(jìn)UCT-原始UCT對弈結(jié)果Tab.2 Result of improved UCT vs UCT

由表2可知，改進(jìn)的UCT算法對弈原始的UCT算法無論先后手勝率都超過了90%，說明結(jié)合Hex棋棋型策略改進(jìn)的UCT算法具有更高的模擬準(zhǔn)確度和更高的勝率。

4 結(jié)束語

本文針對Hex棋在UCT算法中所得結(jié)果準(zhǔn)確度不夠精確的問題，提出了一種結(jié)合Hex棋棋型策略改進(jìn)的UCT算法。該算法對模擬過程采取了一系列的棋型策略，使得UCT模擬階段的模擬準(zhǔn)確度大幅提升，有效的提高了Hex棋的搜索效率與博弈水平。以此算法開發(fā)的Hex棋博弈程序獲得了2021年全國大學(xué)生計算機(jī)博弈大賽Hex棋項目一等獎。雖然改進(jìn)的算法的博弈水平有所提升，但還存在不夠精準(zhǔn)的問題，因此結(jié)合神經(jīng)網(wǎng)絡(luò)，進(jìn)行強(qiáng)化學(xué)習(xí)等成為下一步的研究方向。