基于UCT搜索算法的點(diǎn)格棋博弈系統(tǒng)研究

朱良雙　王靜文　李媛

摘要：蒙特卡羅樹(shù)搜索（MCTS）在許多完備的信息雙人游戲中獲得成功。本文給出了UCT（UpperConfidenceBoundApplytoTree）算法結(jié)合了UCB公式和蒙特卡洛樹(shù)搜索算法，同時(shí)與局面評(píng)估相結(jié)合，根據(jù)點(diǎn)格棋長(zhǎng)鏈和環(huán)的特點(diǎn)對(duì)算法進(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

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

0引言

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

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

1點(diǎn)格棋簡(jiǎn)介

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

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

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

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

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

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

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

2搜索算法

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

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

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

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

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

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

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

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

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

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

點(diǎn)格棋是通過(guò)占邊從而達(dá)到捕獲格子的目的，而邊的總數(shù)只有60條，數(shù)量相對(duì)較少，比較適合使用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

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

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

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

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

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

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

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

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

4，otherwise.

另一方面，如果對(duì)手下邊，當(dāng)打開(kāi)一個(gè)環(huán)，除去該環(huán)后的control_value（G）>2;或者打開(kāi)一條鏈，除去該鏈后的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é)果

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

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

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

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

參考文獻(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ì)算機(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]張雪峰，連蓮，徐心和.基于有限自動(dòng)機(jī)的“點(diǎn)點(diǎn)連格”機(jī)器博弈系統(tǒng)的建模與分析[J].沈陽(yáng)建筑大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，25（4）：796-801.