基于UCT搜索算法的點格棋博弈系統研究

朱良雙　王靜文　李媛

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

關鍵詞：UCT算法;估值函數;點格棋

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

【Keywords】UCTalgorithm;evaluationfunction;DotsandBoxes

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

0引言

眾所周知，點格棋是由數學家愛德華·盧卡斯提出的一種只需要在紙上就可以進行的游戲。與一般的傳統游戲不同，點格棋的玩法是通過點與點之間的邊來占領格子，再根據所占領區域大小來判定勝負，是一種將圖論、數學等知識結合在一起的游戲。

在國內，自2011年起在全國大學生計算機博弈競賽已將該項目作為競賽項目之一，隨著國內外各類機器博弈賽事的陸續舉辦，對于點格棋搜索算法的研究受到了越來越多的愛好者關注，在2020年的全國大學生計算機大賽中，點格棋的參賽隊伍已達到27支，為歷年最多。

1點格棋簡介

點格棋的棋盤大小可以根據情況進行設置，典型的點格棋棋盤由6×6的點圍成的5×5的格子，如圖1所示。

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

點格棋的基本規則如下：

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

（2）當每個格子四條邊被占滿時，這個格子被最后一條邊的捕獲者所占領。

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

（4）當格子全部圍成后，根據格子歸屬統計得分，捕獲格子多的一方獲勝。

2搜索算法

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

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

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

UCT算法的執行過程如圖2所示。

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

（1）選擇：從根節點出發，用遞歸的方法對于每一個孩子節點進行選擇，選擇ri最大的節點作為下一次選擇的開始，直到葉子節點。

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

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

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

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

點格棋是通過占邊從而達到捕獲格子的目的，而邊的總數只有60條，數量相對較少，比較適合使用UTS搜索算法進行搜索。

將UCT算法結合到點格棋博弈系統中的偽碼如下：

FunctionUCT（NoderootNode）

currentNode=rootNode

while（currentNode∈T）

lastNode=currentNode

currentNode=select（currentNode）//選擇

lastNode=Expand（lastNode）//擴展

R=playSimulatedGame（lastNode）//模擬

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

currentNode=backPropagate（R）

currentNode.visitCount++

currentNode=currentNode.parent

returnbestMove

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

3優化估值方法

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

（1）當棋局出現死格時，直接捕獲該死格。

（2）棋局中出現死樹時，則對局面進行評估，根據連和環的定理判斷是否留下最后兩格。死格和死樹的狀態如圖3所示。

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

其中，G表示當前棋局局面[6];c（G）表示當前局面的控制值，即control_value（G）;size（G）表示G中未被占領格子數;long_chain表示長鏈數;loops表示環的數目。tb（G）取值如下：

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

4，otherwise.

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

點格棋的局面估值的偽碼如下：

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實驗與結果

在對比實驗中，采用的博弈系統為相同的UCT搜索算法，節點的估值則分別采用UCB計算公式和優化估值進行計算。UCT搜索算法的時間限制分別設為：5.00s，10.00s，15.00s和20.00s。并分別設定先后手來進行對弈，得到的結果見表1。

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

5結束語

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

參考文獻

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

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

[3]劉洋.點格棋博弈中UCT算法的研究與實現[D].合肥：安徽大學，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].沈陽建筑大學學報（自然科學版），2009，25（4）：796-801.