朱良雙　王靜文　李媛

摘要：蒙特卡羅樹搜索（MCTS）在許多完備的信息雙人游戲中獲得成功。本文給出了UCT（UpperConfidenceBoundApplytoTree）算法結(jié)合了UCB公式和蒙特卡洛樹搜索算法，同時與局面評估相結(jié)合，根據(jù)點(diǎn)格棋長鏈和環(huán)的特點(diǎn)對算法進(jìn)行了優(yōu)化。有利于更快更準(zhǔn)地找到當(dāng)前局面的最優(yōu)解。

關(guān)鍵詞：UCT算法;估值函數(shù);點(diǎn)格棋

【Abstract】MonteCarlotreesearch（MCTS）hasbeensuccessfulinmanyperfectinformationgames.Inthispaper，UCT（UpperConfidenceBoundApplytoTree）algorithmisproposed，whichcombinesUCBformulaandMonteCarlotreesearchalgorithm.Meanwhilecombinedwithsituationassessment，theselectionofnodesforevaluationbyUCBalgorithmisconducivetofindtheoptimalsolutionofthecurrentsituationfasterandmoreaccurately.

【Keywords】UCTalgorithm;evaluationfunction;DotsandBoxes

作者簡介：朱良雙（1999-），男，本科生，主要研究方向：計算機(jī)博弈;王靜文（1965-），男，工程師，主要研究方向：人工智能和信息安全;李媛（1976-），女，博士后，教授，主要研究方向：人工智能和隨機(jī)過程。

0引言

眾所周知，點(diǎn)格棋是由數(shù)學(xué)家愛德華·盧卡斯提出的一種只需要在紙上就可以進(jìn)行的游戲。與一般的傳統(tǒng)游戲不同，點(diǎn)格棋的玩法是通過點(diǎn)與點(diǎn)之間的邊來占領(lǐng)格子，再根據(jù)所占領(lǐng)區(qū)域大小來判定勝負(fù)，是一種將圖論、數(shù)學(xué)等知識結(jié)合在一起的游戲。

在國內(nèi)，自2011年起在全國大學(xué)生計算機(jī)博弈競賽已將該項(xiàng)目作為競賽項(xiàng)目之一，隨著國內(nèi)外各類機(jī)器博弈賽事的陸續(xù)舉辦，對于點(diǎn)格棋搜索算法的研究受到了越來越多的愛好者關(guān)注，在2020年的全國大學(xué)生計算機(jī)大賽中，點(diǎn)格棋的參賽隊伍已達(dá)到27支，為歷年最多。

1點(diǎn)格棋簡介

點(diǎn)格棋的棋盤大小可以根據(jù)情況進(jìn)行設(shè)置，典型的點(diǎn)格棋棋盤由6×6的點(diǎn)圍成的5×5的格子，如圖1所示。

圖1中，棋盤中共60條邊，格子數(shù)為25，由于比賽勝負(fù)是按照雙方所占格子數(shù)來確定，格子數(shù)為奇數(shù)時可以避免出現(xiàn)平局情況。

點(diǎn)格棋的基本規(guī)則如下：

（1）雙方輪流在水平或豎直方向的相鄰兩點(diǎn)之間下棋。

（2）當(dāng)每個格子四條邊被占滿時，這個格子被最后一條邊的捕獲者所占領(lǐng)。

（3）當(dāng)一方占有格子后，必須在下一條邊，直至不再占有格子。

（4）當(dāng)格子全部圍成后，根據(jù)格子歸屬統(tǒng)計得分，捕獲格子多的一方獲勝。

2搜索算法

點(diǎn)格棋博弈系統(tǒng)的構(gòu)成要素主要由搜索算法和估值函數(shù)兩個部分組成[1]。傳統(tǒng)的搜索算法是以極大極小算法為基礎(chǔ)并加以改進(jìn)而來，UCT搜索算法是近幾年在計算機(jī)博弈游戲設(shè)計被逐步采用的一種算法，具有時間可控、搜索效率高的特點(diǎn)。

UCT算法（UpperConfidenceBoundApplytoTree），即上限置信區(qū)間算法，是將蒙特卡洛樹搜索（Monte-CarloTreeSearch，MCTS）方法與UCB公式結(jié)合，在超大規(guī)模博弈樹的搜索過程中相對于傳統(tǒng)的搜索算法有著時間和空間方面的優(yōu)勢，UCT的工作模式是時間可控的[2-3]。在算法執(zhí)行過程中的任何時間突然終止算法，UCT算法可以返回一個理想的結(jié)果。當(dāng)然如果允許更為充分的執(zhí)行時間的話，算法結(jié)果會非常逼近實(shí)際的最優(yōu)值。UCT算法的計算方法如下：

其中，vi表示以節(jié)點(diǎn)ni（非葉節(jié)點(diǎn)）為根節(jié)點(diǎn)的所有仿真結(jié)果的平均值，反映了根據(jù)目前仿真結(jié)果觀察到的節(jié)點(diǎn)ni能提供的回報值的期望;Ti表示節(jié)點(diǎn)ni的訪問次數(shù)，也是被樹內(nèi)選擇策略選中的次數(shù);c表示一個參數(shù)，用來平衡深度優(yōu)先還是寬度優(yōu)先。

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

這里，對UCT算法的4個過程的設(shè)計功能可分述為：

（1）選擇：從根節(jié)點(diǎn)出發(fā)，用遞歸的方法對于每一個孩子節(jié)點(diǎn)進(jìn)行選擇，選擇ri最大的節(jié)點(diǎn)作為下一次選擇的開始，直到葉子節(jié)點(diǎn)。

（2）擴(kuò)展：通過選擇的節(jié)點(diǎn)，將所有合法的下法作為新的葉子節(jié)點(diǎn)加入到搜索樹中，并正確初始化v值和T值。

（3）仿真：簡單的仿真策略是對所有合法的下法，均勻地隨機(jī)選擇下一步，葉子節(jié)點(diǎn)的評估策略可以比較簡單，例如：當(dāng)己方獲勝時為1，對方獲勝時為0。通過若干次仿真后獲得新的v值。

（4）反向傳播：當(dāng)葉子節(jié)點(diǎn)通過仿真獲得新的v和T時，UCT算法通過結(jié)果回傳更新搜索路徑上的所有節(jié)點(diǎn)v和T的值，其計算公式為：

由式（2）、式（3）可知，父節(jié)點(diǎn)的訪問次數(shù)T是所有葉子節(jié)點(diǎn)訪問次數(shù)Ti之和，v是當(dāng)前節(jié)點(diǎn)下所有葉子節(jié)點(diǎn)vi的加權(quán)平均值，權(quán)值為子節(jié)點(diǎn)的訪問比例Ti/T。結(jié)果回傳從葉子節(jié)點(diǎn)開始，沿搜索路徑逐級向上更新，直到根節(jié)點(diǎn)。

點(diǎn)格棋是通過占邊從而達(dá)到捕獲格子的目的，而邊的總數(shù)只有60條，數(shù)量相對較少，比較適合使用UTS搜索算法進(jìn)行搜索。

將UCT算法結(jié)合到點(diǎn)格棋博弈系統(tǒng)中的偽碼如下：

FunctionUCT（NoderootNode）

currentNode=rootNode

while（currentNode∈T）

lastNode=currentNode

currentNode=select（currentNode）//選擇

lastNode=Expand（lastNode）//擴(kuò)展

R=playSimulatedGame（lastNode）//模擬

while（currentNode∈T）//反向傳播

currentNode=backPropagate（R）

currentNode.visitCount++

currentNode=currentNode.parent

returnbestMove

在搜索過程中，若僅采用基本的UCT搜索算法進(jìn)行搜索，搜索的效率就比較低，特別是在搜索的初期，會產(chǎn)生大量的無效模擬，從而降低搜索效率。在采用UCT算法進(jìn)行搜索過程中，引入估值，對節(jié)點(diǎn)的評估采用優(yōu)化估值的方法進(jìn)行，用以提高搜索效率和搜索的準(zhǔn)確度。

3優(yōu)化估值方法

點(diǎn)格棋的下法與一般棋類游戲的下法略有所不同，在完成一步下棋后，需要對是否捕獲格子來做出判斷，若捕獲格子則要再繼續(xù)下一步走棋，直到不再捕獲格子為止，這個過程會導(dǎo)致一方連續(xù)捕獲格子的情況。在博弈中后期，需要直接捕獲局面，并且做出讓格（中斷捕獲格子）、還是不讓格的判斷，所以在進(jìn)行搜索前就要對當(dāng)前局面進(jìn)行評估和預(yù)處理，預(yù)處理由2部分組成，對此可闡釋如下。

（1）當(dāng)棋局出現(xiàn)死格時，直接捕獲該死格。

（2）棋局中出現(xiàn)死樹時，則對局面進(jìn)行評估，根據(jù)連和環(huán)的定理判斷是否留下最后兩格。死格和死樹的狀態(tài)如圖3所示。

對局面進(jìn)行估值主要分為2方面。一方面是局面的控制估值，用于判斷對棋局是否保持控制[4-5]。公式如下：

其中，G表示當(dāng)前棋局局面[6];c（G）表示當(dāng)前局面的控制值，即control_value（G）;size（G）表示G中未被占領(lǐng)格子數(shù);long_chain表示長鏈數(shù);loops表示環(huán)的數(shù)目。tb（G）取值如下：

tb（G）=0，Ghasnochainsorloops;8，Ghasoneormoreloops;6，Ghasoneormoreloopsand3-chains;

4，otherwise.

另一方面，如果對手下邊，當(dāng)打開一個環(huán)，除去該環(huán)后的control_value（G）>2;或者打開一條鏈，除去該鏈后的control_value（G）>4，則己方應(yīng)保持控制，否則放棄控制。

點(diǎn)格棋的局面估值的偽碼如下：

Functionvalue（）

ifcontrol_value≥2thenvalue=control_value.，

ifcontrol_value=0and

G=4l+（anythingexcept3+3），

thenvalue=0.

ifnumberof3-chains=0，orifnumberof3-chains=1

andsize（G）≡3mod4，then

ifcontrol_value+numberof4-loops≥2thenvalue=0，

1，2，3，4accordingtowhethercontrol_value≡0，±1，±2，±3，4mod8.

ifcontrol_value+4f<2then

ifGisoddthenv=1resp.3iffisoddresp.even.

ifsize（G）≡2mod4thenvalue=2.

ifsize（G）≡0mod4thenvalue=0resp.4ifnumberof

4-loopsisodd

resp.even.

inallothercases，value=1，2assize（G）isodd，even.

returnvalue

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

在對比實(shí)驗(yàn)中，采用的博弈系統(tǒng)為相同的UCT搜索算法，節(jié)點(diǎn)的估值則分別采用UCB計算公式和優(yōu)化估值進(jìn)行計算。UCT搜索算法的時間限制分別設(shè)為：5.00s，10.00s，15.00s和20.00s。并分別設(shè)定先后手來進(jìn)行對弈，得到的結(jié)果見表1。

通過表1分析發(fā)現(xiàn)，在采用相同的UCT搜索算法的情況下，運(yùn)用估值函數(shù)的勝率要顯著高于運(yùn)用UCB值搜索的勝率。對于點(diǎn)格棋，各種局面的長鏈和環(huán)一般的估值并不適用。因此，該估值函數(shù)有顯著優(yōu)勢，同時，隨著每步搜索時間的增加，使用優(yōu)化后的估值函數(shù)的搜索算法勝率更高。

5結(jié)束語

本文通過先后手多輪對弈比較，計算出運(yùn)用UCB估值和最佳估值的不同勝率。通過勝率對比結(jié)果表可以看出，采用優(yōu)化估值的方法對于局面的評估提供了一定的幫助，并能有效提高博弈勝率。

參考文獻(xiàn)

[1]ALLCOCKD.Bestplayindotsandboxesendgames[EB/OL].[2021-02-04].https：//doi.org/10.1007/s00182-020-00730-4.

[2]張宜放，孟坤.基于點(diǎn)格棋的UCT算法研究與分析[J].智能計算機(jī)與應(yīng)用，2020，10（4）：27-31.

[3]劉洋.點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn)[D].合肥：安徽大學(xué)，2016.

[4]BERLEKAMPE.Forcingyouropponenttostayincontrol[J].PlosOne，2001，11（1）.

[5]BREWKAG，HABELC，NEBELB.Anartificialintelligenceapproachtodots-and-boxes[C]//GermanConferenceonArtificialIntelligence：AdvancesinArtificialIntelligence.Berlin/Heidelberg：Springer-Verlag，1997.

[6]張雪峰，連蓮，徐心和.基于有限自動機(jī)的“點(diǎn)點(diǎn)連格”機(jī)器博弈系統(tǒng)的建模與分析[J].沈陽建筑大學(xué)學(xué)報（自然科學(xué)版），2009，25（4）：796-801.