基于UCT算法改進(jìn)的Hex棋博弈系統(tǒng)研究

徐志凡，王靜文，李 媛

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

0 引 言

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

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

1 Hex棋簡(jiǎn)介

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

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

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

圖1 Hex棋棋盤(pán)Fig.1 The chess board of Hex

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

計(jì)算機(jī)博弈游戲其核心由搜索和估值兩部分組成，傳統(tǒng)的搜索方法為Alpha-Beta算法及其諸多變種。由于Hex棋的特殊性，估值算法不能很好的評(píng)估當(dāng)前局面，所以采用UCT搜索算法。該算法能在可控的時(shí)間內(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）最初是針對(duì)K臂賭博機(jī)問(wèn)題提出來(lái)的，而UCT算法將MCTS搜索與UCB公式相結(jié)合，在大規(guī)模博弈樹(shù)的搜索過(guò)程中相對(duì)于傳統(tǒng)的搜索算法在時(shí)間和空間方面占據(jù)優(yōu)勢(shì)。UCT算法的優(yōu)勢(shì)在于工作時(shí)間可控、具有更好的魯棒性，并且搜索過(guò)程中，博弈樹(shù)以非對(duì)稱的形式動(dòng)態(tài)擴(kuò)展開(kāi)。UCT算法樹(shù)內(nèi)選擇的UCB公式（1）：

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

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

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

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

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

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

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

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

2.2 特殊棋型

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

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

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

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

圖4 無(wú)用位置Fig.4 Useless location

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

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

（4）邊界位置。在邊界處會(huì)存在一些棋型，無(wú)論敵方下在哪個(gè)位置，己方都存在另一個(gè)位置來(lái)保證與邊界相連，則稱這些位置為邊界位置，如圖6所示。

圖6 邊界位置Fig.6 Boundary position

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

圖7 梯子棋型Fig.7 Ladder pattern

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

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

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

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

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

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

在模擬時(shí)采用3種策略：

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

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

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

3 實(shí)驗(yàn)與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 選取c值

由于UCT算法中的參數(shù)是一個(gè)預(yù)先設(shè)定方參數(shù)，所以需要對(duì)值進(jìn)行優(yōu)化選取。由于Alpha-Beta算法的穩(wěn)定性，故采用UCT算法與搜索層數(shù)為3層的Alpha-Beta算法進(jìn)行測(cè)試，不同值均測(cè)試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 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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