UCT算法在不圍棋博弈中的實現(xiàn)

梁國軍，謝垂益，胡伶俐，林　　昊，李景炤

（韶關(guān)學院 數(shù)學與統(tǒng)計學院，廣東 韶關(guān)5120051）

UCT算法在不圍棋博弈中的實現(xiàn)

梁國軍，謝垂益*，胡伶俐，林昊，李景炤

（韶關(guān)學院 數(shù)學與統(tǒng)計學院，廣東 韶關(guān)5120051）

摘要：計算機博弈是人工智能領(lǐng)域的挑戰(zhàn)性課題，它利用計算機進行分析、判斷和推理，從而得到理性的決策.不圍棋是近年來計算機博弈競賽的一個棋種，屬于圍棋的變體，其規(guī)則是先吃子或棋子自殺的一方為負.通過分析不圍棋博弈模型的特點，提出了對上限信心界樹搜索(UCT)算法的一個優(yōu)化方法，在算法的啟動過程優(yōu)先選擇評分較高的盤面進行模擬博弈，以便得到更好的落子選擇.在與著名的OASE-NoGo軟件的試驗對弈中，以該算法為核心設(shè)計的不圍棋軟件取得了90%以上的勝率，證明是可行、有效的.

關(guān)鍵詞：人工智能；計算機博弈；不圍棋；UCT算法

棋類游戲是計算機博弈領(lǐng)域的重要研究課題，這些研究工作有助于加深對人工智能與計算機科學的認識，促進對人類認知過程的理解.不圍棋是十多年前開始出現(xiàn)的一種雙人博弈游戲，屬于圍棋的變體，如果一方落子后吃掉了對方的棋子、或者令已方棋子自殺，則落子一方判負［1］.2011年起，由國際計算機博弈協(xié)會（International Computer Games Association，ICGA）組織的計算機奧林匹克（Computer Olynpiad）大賽增加了不圍棋項目.2012年起，由中國人工智能學會舉辦的中國機器博弈錦標賽也將不圍棋列入比賽項目.在這些高級別賽事的推動下，不圍棋正在為人們認識并開始進行研究.

筆者總結(jié)了不圍棋的研究現(xiàn)狀，分析了不圍棋的博弈模型，給出上限信心界樹搜索 （UCT，UCB for Tree Search）中的UCB1子算法的一個修正，使其能更早地選擇優(yōu)勢盤面，并據(jù)此設(shè)計了一個不圍棋博弈軟件，通過與對照軟件的對弈實驗來驗證算法的有效性.

1　　研究現(xiàn)狀

早些年，計算機博弈對于棋類游戲的研究集中在基于模式識別和專家系統(tǒng)的方法上（最典型的是基于靜態(tài)評估函數(shù)的α-β博弈樹方法），并在國際象棋、中國象棋等項目中獲得了成功.但是對于圍棋類的項目，由于搜索空間巨大只能訪問博弈樹的一小部分、無法進行準確的靜態(tài)盤面評估，因此傳統(tǒng)的方法一直無法取得滿意的結(jié)果，在2000年前后，世界上最高水平的計算機圍棋軟件的棋力還比不上人類的業(yè)余初段.2006年，Levente Kocsis和Csaba Szepesvári將蒙特卡洛樹搜索（Monte-Carlo Tree Search，MCTS）方法與UCB公式［2］結(jié)合，提出上限信心界樹搜索（UCT，UCB for Tree Search）算法［3］，顯著地提高了搜索效率. UCT算法的出現(xiàn)開創(chuàng)了計算機博弈研究的新局面.此后人們圍繞MCTS方法進行研究和改進，推動圍棋軟件的棋力不斷提高.2013年3月，圍棋軟件CrazyStone在受讓四子的情況下，戰(zhàn)勝日本棋手石田芳夫九段，其棋力已達到業(yè)余五、六段的水平.

首次對不圍棋的研究報道出現(xiàn)在2011年，文獻［4］介紹了MCTS算法在不圍棋中的實現(xiàn).通過對比測試發(fā)現(xiàn)，在圍棋中常用的快速動作值估計（Rapid Action-Value Estimates，RAVE）、節(jié)點慢速創(chuàng)建、布局模板、UCT等方法和算法，在不圍棋中同樣有效；文獻［5］提出一個結(jié)合本體、進化計算、模糊邏輯、模糊標記語言的遺傳算法，根據(jù)收集的棋局模式和預構(gòu)建的不圍棋模糊本體，用基于模糊推理機制的遺傳模糊標記語言分析當前棋局，得到下一個最好的棋步，并應用了遺傳學習機制，可在與參照棋局的對壘中不斷提高棋力；文獻［6-7］分析了棋局模板的分類和格式定義，在對弈過程中優(yōu)先使用模板進行棋步的選擇，當出現(xiàn)模板中沒有的棋局時再使用MCTS算法；文獻［8］提出在對弈過程中進行UCT樹的重用，可以增加5%～30%的搜索深度；文獻［9］通過啟發(fā)式、暴力搜索、參數(shù)調(diào)整等方式，提高UCT算法的搜索成功率；文獻［10］提出在MCTS算法中增加靜態(tài)估計方法，根據(jù)周圍棋子的類型標記出允許自由落子的點和禁止落子的點，加快博弈樹搜索速度.

由于不圍棋是新的棋類，相關(guān)的研究成果較少.目前對不圍棋的主要研究方法是參考棋類尤其是圍棋的相關(guān)理論和技術(shù)，根據(jù)其博弈規(guī)則進行改造和拓展.但由于博弈規(guī)則不同，博弈模型的建立、盤面優(yōu)勢評估、博弈樹搜索等過程相較其他棋類有很大的區(qū)別.對于不圍棋博弈的研究，大多內(nèi)容都將會是創(chuàng)新性的工作.

2　　不圍棋的博弈模型

一個不圍棋的博弈模型包括對弈規(guī)則［9］、博弈樹的生成、盤面評估、博弈搜索算法等內(nèi)容.

2.1博弈樹的生成

9路不圍棋的盤面有9行9列，總共81個點.在雙人對弈過程中，先手方要考慮的落子點依次為81、79、77、……、3、1個，后手方要考慮的落子點依次為80、78、76、……、4、2個.對于選手在第i步（先手時1≤i≤41，后手時1≤i≤40）時，若考慮連續(xù)的d步落子（從本步算起），則可供選擇的盤面數(shù)R為：

根據(jù)式(1)，表1列出選手在盤中下完第20步后，考慮第21步開始的連續(xù)2、5、10步落子時需要檢查的盤面數(shù).

表1　　盤中第21步起的盤面數(shù)

以當前的盤面作為根結(jié)點，后續(xù)d步的可選盤面構(gòu)成子樹結(jié)點，形成一個d+1層的博弈樹.計算機通過搜索該博弈樹得到下一步落子的最優(yōu)選擇.

從下棋的經(jīng)驗中知道，能夠預估的后續(xù)落子步數(shù)(d)越多，棋手的棋力就越強，獲勝的概率越高，計算機博弈也是如此.但當考慮過多的后續(xù)步（例如5步以上）時，博弈樹中的結(jié)點數(shù)量過于龐大、呈指數(shù)級增長，對于普通計算機來說，需要較多的計算時間和存儲空間，容易出現(xiàn)落子過慢、內(nèi)存不足的情況.

2.2盤面評估

下面先給出氣、眼、虎口、禁入點等基本術(shù)語的定義．

定義1：氣指與棋子/棋塊相鄰的空白點.

定義2：眼指同種顏色的棋子圍成的一個空白點，相當于棋塊內(nèi)的“氣”.對方如果在該眼位落子，則該棋子的氣為0，形成一種自殺行為.

定義3：虎口指這樣的一個空白點，落在該點的棋子的氣為1.虎口是最接近完成眼之前的一個狀態(tài).定義4：禁入點指能使對方的棋子或棋塊無氣的一個未落子的點.若在禁入點落子，將殺死對方的棋子或棋塊，本方直接判負.

在對弈過程中，每走一步棋，應使己方的合法落子點盡量多、對方的合法落子點盡量少，這樣就越有機會接近勝利.根據(jù)不圍棋的對弈規(guī)則，對弈過程中應使已方盤面中的眼和虎口的數(shù)量盡量多、禁入點的數(shù)量盡量少.因此，定義盤面N的評估函數(shù)S(N)為：

式（2）中，n1為盤面N中眼的個數(shù)，s1為每個眼的分值，n2為虎口的個數(shù)，s2為每個虎口的分值，n3為禁入點的個數(shù)，s3為每個禁入點的分值.S(N)的值越大表明盤面越有利，否則盤面狀態(tài)越不理想.

2.3博弈搜索算法

在不圍棋博弈中，假設(shè)雙方總是采用最佳的落子策略.最佳的落子策略是指選手在任意給定的盤面中，如果存在致勝的走法，則選手就會選擇致勝的走法落子.給定任意的盤面狀態(tài)，總是可以構(gòu)建、遍歷博弈樹，然后總能找到最佳落子點，使該選手取得勝利，所以不圍棋是可解的.

由于不圍棋博弈樹的規(guī)模非常大，即使模擬數(shù)百萬次的對局，也僅僅能夠覆蓋博弈樹很小的一部分.如果隨機地選擇博弈樹的子節(jié)點，則會花費非常多的搜索空間和時間，使得搜索的效率低下.建議在子節(jié)點的隨機模擬過程中加入不圍棋知識的各種策略，進而得到更高的搜索效率和更準確的結(jié)果.

博弈搜索算法的基本思路是：給定一個任意盤面和某一選手的棋子顏色，建立博弈樹，進行搜索、評估和剪枝，返回評估分值最好的一條路線.

3　UCT算法的設(shè)計

UCT算法是UCB算法與蒙特卡洛方法的結(jié)合.筆者提出對UCB算法的一個修正，據(jù)此對UCT算法進行優(yōu)化設(shè)計.

3.1蒙特卡洛方法

蒙特卡洛方法的主要理論基礎(chǔ)是大數(shù)定律，在隨機取樣的情況下，可以獲得有誤差的評估值，取樣的數(shù)量越多，誤差將越小，評估值將越準確.運用蒙特卡洛方法模擬不圍棋中隨機落子的步驟是：保存當前棋盤狀態(tài)，生成下一步所有可落子點，選一可落子點落一子，接著按對應黑白子落子的順序，黑子和白子輪流隨機落子，直至分出勝負.記錄勝負和模擬次數(shù)，恢復棋盤至之前保存狀態(tài).重復多次模擬以提高準確性，直至模擬到時間結(jié)束或者到達規(guī)定的模擬次數(shù)為止，選擇勝率最大的可落子點，該點為最佳落子點.蒙特卡洛方法算法的偽碼為：

MonteCarlo(棋盤狀態(tài)){

根據(jù)棋盤狀態(tài)生成下一步所有可落子點；while(模擬時間未到或者未達到模擬次數(shù)){黑子和白子輪流隨機落子，直至分出勝負；記錄勝負和模擬次數(shù)；

更新相關(guān)節(jié)點的方向次數(shù)和獲勝的次數(shù)信息值；}返回勝率最大的可落子點；}.

3.2 UCB算法的修正

UCB算法來源于多臂匪徒模型，它采用在線的機器學習策略，既對當前已有知識進行利用，又有對未了解的知識進行探索.這當中最著名的是UCB1算法［2］，其核心是信心上界索引計算公式(UCB1公式)：

式中N為博弈樹中的給定節(jié)點，Ni為N的子節(jié)點，I(Ni)為Ni的信心上界索引，t(N)為對N的模擬次數(shù)，t (Ni)為Ni在模擬中被選中的次數(shù)，X(Ni)為Ni的收益平均值.C為加權(quán)系數(shù)，如果C比較小則表明當前的搜索偏重于利用；C比較大則說明當前搜索偏重于探索.

UCB1算法采取隨機的方式開始第一步的選擇.但是對于棋類博弈的情形，當處于盤中某一個對弈盤面時，可以根據(jù)對盤面的評估，優(yōu)先選擇往有利方向發(fā)展的落子.因此，本文提出對UCB1算法的修正思路：對于博弈樹中的子結(jié)點Ni（對應一個可能的盤面)，先按式(2)進行盤面評估，評估結(jié)果作為Ni的收益初始值X1(Ni.由于在棋類博弈中Ni的收益平均值往往取為該節(jié)點對應盤面的勝率，是一個不大于1的數(shù)字，因此可事先設(shè)定一個極大值常數(shù)M，使得S(Ni)/M小于1.經(jīng)過修正的UCB算法偽碼為：

UCB_modify(棋局盤面N){//得到盤面N的下一步可落子點if(N無孩子結(jié)點){//創(chuàng)建下一層博弈樹

下一步的所有可落子點Ni作為N的孩子結(jié)點；

＜--盤面評估值S(Ni)/M；}

Else{//訪問下一層博弈樹

循環(huán)：遍歷訪問N的所有下一步可落子點Ni，用公式(3)計算；}

返回值最大的子節(jié)點Ni；}.

3.3優(yōu)化的UCT算法

通過蒙特卡洛方法可以解決不圍棋落子搜索的問題，但是因為蒙特卡洛方法是隨機模擬的，而且沒有先驗知識的指導，使得博弈樹的可擴展層數(shù)較少，很難得到最優(yōu)解.UCT算法的基本思想是將UCB算法應用到蒙特卡洛規(guī)劃過程中，通過計算UCB值來選擇落子點，不再是隨機選擇，有利于更早得到最優(yōu)解.但是UCB算法的初始階段還是通過隨機選擇落子點啟動模擬對弈過程，沒有考慮盤面的差異對勝負趨勢的影響.本文根據(jù)修正的UCB算法實現(xiàn)對UCT算法的優(yōu)化，使得盤面局勢影響落子位置，盤面評估得分較高的位置落子的機會更大，而盤面評估結(jié)果較差的落子位置也會有機會被選中、只是優(yōu)先級比較低.該UCT算法偽碼為：

UCT(棋局盤面root){//根據(jù)棋盤狀態(tài)返回一個落子點

建第一層博弈樹，以下一步的所有可落子點作為root的孩子結(jié)點；

node［0］＜--root；

while(模擬時間未用完或者未達到模擬次數(shù)){

i＜--0；

while（node［i］不是終局盤面){//向下擴展，創(chuàng)建或訪問多層博弈樹

i++；

node［i］＜--UCB_modify(node［i-1］)；//選出下一步可落子點

}

value＜--對node［i］的評判結(jié)果（取勝為1、負為0）；

若i為偶數(shù)，value＜---value；//偶數(shù)次是對方的落子，相應獲勝數(shù)取負值以便區(qū)分

for(j=i-1；j＞0；j--){//向上更新父節(jié)點的獲勝數(shù)和模擬次數(shù)

value＜---value；

node［j］的獲勝數(shù)增加value、模擬次數(shù)增加1；}

}pos＜--勝率(獲勝數(shù)/模擬次數(shù))最高的可落子點(root的某個孩子結(jié)點)；

刪除以root為根的博弈樹；

返回pos；}.

4　　實驗結(jié)果

根據(jù)上述的UCT算法，實現(xiàn)了一個不圍棋博弈軟件，并通過與著名的臺灣大學不圍棋軟件OASE-No-Go V1.1進行對弈測試實現(xiàn)效果.

與OASE-NoGo V1.1的初級棋的對弈結(jié)果見圖1，與OASE-NoGo V1.1的高級棋的對弈結(jié)果見圖2.

圖1初級對弈結(jié)果　

圖2高級對弈結(jié)果

表2為與OASE-NoGo V1.1初級和高級對弈的結(jié)果記錄，可以看出，本文實現(xiàn)的不圍棋博弈軟件有較強的棋力，在與對照軟件的對弈中，取得了90%以上的勝率.

表2　　對弈結(jié)果記錄表

5　　結(jié)論

針對不圍棋博弈模型的特點，對UCT算法中的UCB子算法進行了修正，將盤面評估結(jié)果作為算法啟動時的初始值，優(yōu)先選擇較優(yōu)的盤面進行模擬對弈，以便更快得到較好的棋步.所有的盤面都有機會被選中，只是較差的盤面被選中的概率較低而已.UCT算法的“利用已知、探索未知”的特性仍然得以保留.在與著名的不圍棋軟件OASE-NoGo V1.1的多次對弈實驗中，以上述算法為核心實現(xiàn)的不圍棋博弈軟件取得了90%以上的勝率，結(jié)果證明該算法可行、有效.

參考文獻：

［1］Denim S.Anti Atari Go［EB/OL］.(2011-12-07)［2014-8-30］.http://senseis.xmp.net/?AntiAtariGo.

［2］Auer P，Cesa-Bianchi N，F(xiàn)ischer P.Finite-time Analysis of the Multiarmed Bandit Problem［J］.Machine Learning，2002，47(2-3):235-256.

［3］Kocsis L,Szepesvári C.Bandit based monte-carlo planning［C］.//Proceedings of the 17th European conference on Machine Learning, Berlin in Germany:Springer-Verlag,2006:282-293.

［4］CHOU C W,Teytaud O,and YEN S J.Revisiting Monte-Carlo tree search on a normal form game:NoGo［C］.//Proceedings of the 2011 international conference on Applications of Evolutionary Computation,Torino in Italy:Springer-Verlag,2011:73-82.

［5］LEE C S，WANG M H，CHEN Y J，et al..Genetic fuzzy markup language for game of NoGo［J］.Knowledge-Based Systems，2012(34): 64-80.

［6］SUN Y X,LIU C,and QIU H K.The research on patterns and UCT algorithm in NoGo game［C］.//25th Chinese Control and Decision Conference,Guiyang:IEEE,2013:1178-1182.

［7］SUN Y X,WANG Y J,and LI F.Pattern matching and Monte-Carlo simulation mechanism for the game of NoGo［C］.//Proceedings of IEEE CCIS2012,Hangzhou:IEEE,2012:61-64.

［8］LI R,WU Y Q,ZHANG A D,et al.Technique analysis and designing of program with UCT algorithm for NoGo［C］.//25th Chinese Control and Decision Conference,Guiyang:IEEE,2013:923-928.

［9］佘博玄，禁圍棋程式設(shè)計與研究［D］.臺灣新竹：交通大學，2013.

［10］SUN Y X,RAO G J,SUN H M,et al.Research on static evaluation method for computer game of NoGo［C］.//26th Chinese Control and Decision Conference,Changsha:IEEE,2014:3455-3459.

（責任編輯：歐愷）

中圖分類號：TP312

文獻標識碼：A

文章編號：1007-5348（2015）08-0017-04

［收稿日期］2015-05-15

［基金項目］國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(201410576018)；廣東省大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(201410576060)；韶關(guān)學院科研項目(2012-16).

［作者簡介］梁國軍(1992-)，男，廣東清遠人，韶關(guān)學院數(shù)學與統(tǒng)計學院本科生；研究方向：計算機算法.*通訊作者.

An Implementation of UCT Algorithm for NoGo Game

LIANG Guo-jun,XIE Chui-yi,HU Ling-li,LIN Hao,LI Jing-zhao
（School of Mathematics and Statistics,Shaoguan University,Shaoguan 512005,Guangdong,China）

Abstract：Computer game is a challenging task in the field of artificial intelligence,which makes use of com

puter to analyze,judge and reason,so as to get the rational decision.In recent years,NoGo game is a kind of computer game competitions,similar to the game of Go,with the rules of no capture or suicide which is allowed. According to the characteristics of NoGo game model,an optimized UCT(UCB for Tree Search)algorithm is pro

posed to compute the better move by choosing certain chess layout with high score preferentially.A NoGo game software is designed mainly relies on the above-mentioned algorithm and proved to be feasible and efficient by the result of achieving more than 90%of winning with the famous OASE-NoGo.

Key words：artificial intelligence;computer game;NoGo;UCT algorithm