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

梁國(guó)軍，謝垂益，胡伶俐，林　　昊，李景炤

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

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

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

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

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

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

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

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

1　　研究現(xiàn)狀

早些年，計(jì)算機(jī)博弈對(duì)于棋類游戲的研究集中在基于模式識(shí)別和專家系統(tǒng)的方法上（最典型的是基于靜態(tài)評(píng)估函數(shù)的α-β博弈樹方法），并在國(guó)際象棋、中國(guó)象棋等項(xiàng)目中獲得了成功.但是對(duì)于圍棋類的項(xiàng)目，由于搜索空間巨大只能訪問博弈樹的一小部分、無(wú)法進(jìn)行準(zhǔn)確的靜態(tài)盤面評(píng)估，因此傳統(tǒng)的方法一直無(wú)法取得滿意的結(jié)果，在2000年前后，世界上最高水平的計(jì)算機(jī)圍棋軟件的棋力還比不上人類的業(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)了計(jì)算機(jī)博弈研究的新局面.此后人們圍繞MCTS方法進(jìn)行研究和改進(jìn)，推動(dòng)圍棋軟件的棋力不斷提高.2013年3月，圍棋軟件CrazyStone在受讓四子的情況下，戰(zhàn)勝日本棋手石田芳夫九段，其棋力已達(dá)到業(yè)余五、六段的水平.

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

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

2　　不圍棋的博弈模型

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

2.1博弈樹的生成

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

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

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

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

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

2.2盤面評(píng)估

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

定義1：氣指與棋子/棋塊相鄰的空白點(diǎn).

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

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

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

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

2.3博弈搜索算法

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

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

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

3　UCT算法的設(shè)計(jì)

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

3.1蒙特卡洛方法

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

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

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

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

3.2 UCB算法的修正

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

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

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

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

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

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

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

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

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

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

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

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

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

node［0］＜--root；

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

i＜--0；

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

i++；

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

}

value＜--對(duì)node［i］的評(píng)判結(jié)果（取勝為1、負(fù)為0）；

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

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

value＜---value；

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

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

刪除以root為根的博弈樹；

返回pos；}.

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

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

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

圖1初級(jí)對(duì)弈結(jié)果　

圖2高級(jí)對(duì)弈結(jié)果

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

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

5　　結(jié)論

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

參考文獻(xiàn)：

［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è)計(jì)與研究［D］.臺(tái)灣新竹：交通大學(xué)，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.

（責(zé)任編輯：歐愷）

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1007-5348（2015）08-0017-04

［收稿日期］2015-05-15

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

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

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