郭倩宇 陳優(yōu)廣

摘要：介紹了不圍棋及其規(guī)則，并且給出了當(dāng)前不圍棋人工智能的方法及其不足之處.通過分析不圍棋博弈的特點，提出了價值評估模型函數(shù);基于此，構(gòu)造出了遞歸算法，實現(xiàn)了不圍棋人工智能，解決了當(dāng)前已有算法時間和空間復(fù)雜度過高的問題;給出了實現(xiàn)此算法的程序與著名開源軟件OASE-NoGo的對弈結(jié)果：達到了90%以上的勝率.同時，通過一個常見局面展示了本文算法較傳統(tǒng)算法在程序計算上的優(yōu)勢，證明了本文算法的可行性和高效性.

關(guān)鍵詞：人工智能;機器博弈;不圍棋;價值評估;遞歸

中圖分類號：TP399 文獻標志碼：A DOI：10.3969/j.issn.1000-5641.2019.01.007

0引言

機器博弈一直是人工智能領(lǐng)域的熱點問題.自2016年谷歌公司研制出的“阿爾法圍棋”挑戰(zhàn)人類世界冠軍李世石成功后，博弈類人工智能吸引了更加廣泛和熱烈的關(guān)注.不圍棋，是十多年前開始的一項博弈類游戲，和圍棋有相似之處，比如都使用相同的棋子并且有一些相似的概念如“氣”、“眼”等，但與圍棋是以最后雙方所圍交叉點數(shù)來判斷輸贏完全不同.在不圍棋中，如果一方提掉另一方的子或者是選擇放棄落子，則被判負.因此，不圍棋在輸贏策略上就有了完全不同的思維方式，而不圍棋人工智能與圍棋人工智能的思路也就有所不同.

針對以上問題，本文提出了使用基于價值評估的遞歸算法來實現(xiàn)不圍棋人工智能.通過利用價值評估模型和函數(shù)來對當(dāng)前局面選出候選點，之后使用遞歸來確定最優(yōu)解.本文在接下來的組織結(jié)構(gòu)是：第1節(jié)介紹不圍棋及其規(guī)則;第2節(jié)介紹目前關(guān)于不圍棋人工智能的實現(xiàn)算法和主要缺點;第3節(jié)給出本文的主要工作，包括對不圍棋博弈的思考、價值評估函數(shù)的構(gòu)建，以及基于價值評估的遞歸算法的具體思路和步驟等;第4節(jié)給出實驗結(jié)果，包括與開源軟件OASE-NoGo的對弈圖和與傳統(tǒng)算法在程序計算上的對比;第5節(jié)對全文進行總結(jié).

1不圍棋及其規(guī)則

不圍棋使用9×9棋盤，黑棋先行，之后黑白交替落子，對弈中禁止自殺，如果一方吃掉另一方的子或者是選擇Pass則被判負.吃子規(guī)則與圍棋相同，就是指某種顏色的一個子或者一串棋子在棋盤上，與它直線緊鄰的交叉點為它的“氣”，若所有的氣都被另一種顏色占據(jù)，則被吃掉.

2011年起，國際計算機奧林匹克大賽增加了不圍棋項目;2012年起，由中國人工智能學(xué)會舉辦的全國機器博弈大賽中也把不圍棋列入競賽項目.由此，不圍棋人工智能開始被大家所研究.

2不圍棋人工智能研究現(xiàn)狀

2.1研究歷程

計算機博弈，就是希望計算機像人類一樣，學(xué)習(xí)并實現(xiàn)博弈功能.簡而言之，就是希望計算機擁有類似人一樣準確的思維、判斷和推理決策能力.1996年，由幾名國際特級大師和電腦專組成的“深藍”國際象棋小組研究開發(fā)出的“Deeper Blue”.以3.5：2.5擊敗了世界冠軍卡斯帕洛夫.而圍棋項目，則直到2016年才被谷歌公司用深度學(xué)習(xí)和樹搜索的結(jié)合方法攻克.在這期間，蒙特卡洛思想的UCT（upper Confidence Bound Apply to Tree）算法曾一度在圍棋人工智能領(lǐng)域主導(dǎo)了近十年的時間.文獻等都是從不同思路優(yōu)化UCT算法，來提高博弈樹的搜索速度.

不圍棋，作為一種由圍棋發(fā)展而來的棋種，其人工智能的研究，在之前的工作中，絕大部分都是采用與圍棋類似的蒙特卡洛樹搜索（The Monte-Carlo Search Tree，MCTS）算法來解決.最早關(guān)于不圍棋人工智能的研究出現(xiàn)于2011年，通過對比圍棋，發(fā)現(xiàn)快速評估、MCTS等方法同樣適用于不圍棋.與之類似的文獻和文獻都是利用MCTS來解決不圍棋問題，其中文獻在選點過程中使用了和圍棋相似的模式匹配方式，一定程度上優(yōu)化了使用MCTS造成的巨大的搜索空間的問題;文獻則在啟動MCTS算法時，優(yōu)先對評分較高的局面進行模擬，通過這種方法來盡可能減少模擬次數(shù).

2.2 MCTS算法及其不足之處

MCTS是一種動態(tài)評估方法，更多的是利用數(shù)學(xué)統(tǒng)計中概率的思想.具體來說，就是對問題領(lǐng)域內(nèi)的所有可選情況，通過不斷反復(fù)地進行大量抽樣，最終所得結(jié)果會在解空間上形成一個分布，而這個分布是接近真實的，進而就能夠得到所需的最優(yōu)解或近似的最優(yōu)解.

MCTS方法主要包括以下4個方面的內(nèi)容.

（1）搜索：從博弈樹的根節(jié)點（即終局狀態(tài)）向下搜索直至當(dāng)前的葉子結(jié)點（即當(dāng)前局面）.

（2）擴展：對當(dāng)前的博弈樹葉子結(jié)點進行擴展.

f3）模擬：從當(dāng)前的博弈樹葉子結(jié)點開始進行蒙特卡洛概率模擬并給出一個蒙特卡洛概率統(tǒng)計數(shù)值.

（4）更新：把蒙特卡洛模擬的結(jié)果更新到搜索過程中博弈樹的每一個節(jié)點上.

之后，重新從（1）開始，不斷反復(fù)地進行迭代，使得添加的局面越來越多，則對于博弈樹中所有的子節(jié)點的勝利率也越來越準.最后，選擇勝利率最高的選點.因此，怎樣對蒙特卡洛中博弈樹進行剪枝和如何提供準確侯選點成為難題，在這種情況下，利用模式匹配等方式成為主流.或標記出不能落子的點來縮小搜索范圍，但以上的方法依舊不能改變蒙特卡洛思想需要大量隨機模擬的事實，無法克服蒙特卡洛思想本身的時間、空間復(fù)雜度高的問題.所以MCTS算法實現(xiàn)的程序就會對硬件水平、時間等提出較高要求，不適用于硬件水平較低或反應(yīng)速度要求較快的軟件中.

為解決以上問題，本文沒有選擇主流的MCTS算法，而是利用不圍棋博弈本身的特點，構(gòu)建了價值評估模型和函數(shù)，通過遞歸的方法來實現(xiàn)不圍棋人工智能，并達到了與之前研究相同的棋力效果，克服了MCTS計算復(fù)雜的問題.

3基于價值評估的遞歸算法

3.1不圍棋行棋思路及價值評估函數(shù)的構(gòu)建

為了避免蒙特卡洛思想本身的弊端，本文選擇用價值評估模型來實現(xiàn)不圍棋人工智能，主要是從不圍棋本身的博弈思路來考慮.為了達到不輸?shù)舯荣惖哪康?，就是努力不吃掉對手的子，那么，就會有兩種行棋思路：第一，使自己的“氣”比對手的少;第二，使自己的“眼”比對手的多.

基于以上兩點，本文將被對方打吃的子數(shù)與己方“眼”的個數(shù)規(guī)定為權(quán)利數(shù)，以此來構(gòu)造不圍棋的價值評估模型和函數(shù).顯而易見，在后盤，雙方都在消耗自己的權(quán)利，而權(quán)利數(shù)多的一方將取得勝利，因此，不圍棋行棋的主要目的可以描述為制造己方權(quán)利或是破壞對方權(quán)利.本文中將權(quán)利的制造和破壞稱為權(quán)利規(guī)則，這一規(guī)則容易想到的方法是把各種棋形擺出來，比如被打吃、“眼”等等.但在實際局面中，形成權(quán)利的棋形千奇百怪，遠不是能夠一一列舉的.如果用模式庫的方式，則難以避免占用空間較多的問題.所以，本文利用“氣”這一概念來思考，形成權(quán)利值的標志就是會在棋子周圍的點中形成一個或多個對手無法落子的交叉點，即這個交叉點是己方的單個眼位或己方在此處有且僅有最后一口氣（如圖1和圖2中標記處），則這個交叉點就是自己的權(quán)利.

3.2基于價值評估的遞歸算法

由第3.1節(jié)中得到的評估函數(shù)可以評價任意局面中任一交叉點的價值，且此價值與當(dāng)前行棋的顏色無關(guān)，若只有一個最高價值的點，則此點為最佳選點.但在執(zhí)行過程中，由于局面的復(fù)雜性，經(jīng)常會遇到一個問題，就是在某一局面下會出現(xiàn)不只一個使式（4）中V最大的點.因此，為了解決這個問題，也為了找到最優(yōu)解，本文采用遞歸的算法來完善價值評估思路.特別地，當(dāng)所有點的價值在遞歸（一般選用三層）之后，計算結(jié)果仍均為0，本文將采用打散規(guī)則來處理.

3.2.1打散規(guī)則

在不圍棋中，有時會出現(xiàn)遞歸三層的價值評估最大值都相同的情況.典型的例子就是開局階段，經(jīng)常會出現(xiàn)選點沒有優(yōu)劣之分的情況.在這種情況中，可以選擇隨機落子來解決問題，這并不會過多地影響人工智能的整體水平.但在本文中，基于對不圍棋的大量實踐和博弈特點的思考，選擇使用打散規(guī)則來代替隨機落子，作為對不圍棋開局的一種優(yōu)化，且當(dāng)棋盤為空時，算法中選擇最中心，即天元點作為開局.

在打散規(guī)則中選擇曼哈頓距離d（i，J），且即兩個點在標準坐標系上的絕對軸距總和來進行打散，使行棋打散程度最大化.

打散功能函數(shù)具體步驟如下.

第一步：選出所有可下點，剔除已有子的交叉點和己方不能行棋的點，如對方眼位或會吃掉對方棋子處.

第二步：計算所有可下點與棋盤已有子的曼哈頓距離的最小值.

第三步：找出第二步中所得最小值的最大值，標記相應(yīng)的點，若唯一，則確定此點為打散規(guī)則中的最優(yōu)解，若有多個，則隨機選擇.

3.2.2遞歸算法步驟

當(dāng)出現(xiàn)最大評估價值包含多個交叉點時，本文將這些交叉點設(shè)為候選點，之后利用遞歸的思想對這些候選點進行多次的價值評估，最終選取多次價值評估后出現(xiàn)最大值的候選點為最優(yōu)解.其遞歸算法步驟為如下.

第一步：尋找出當(dāng)前局面中價值評估為最大的所有候選點.

第二步：依次將所有候選點設(shè)置為當(dāng)前行棋的棋子（黑子或白子）.

第三步：更新第二步所得棋盤，計算評估值，若為0，則跳出遞歸算法，執(zhí)行打散規(guī)則;若非0，則繼續(xù).

第四步：對所有候選點得到的局面進行多次價值評估，直到有且僅有一個候選點的價值最大.

第五步：出現(xiàn)價值最大的情況，則返回最初選擇的候選點.

4實驗結(jié)果

4.1功能展示

根據(jù)上述算法，本文實現(xiàn)了一個不圍棋人工智能軟件，在普通配置（4 GP內(nèi)存，雙核）的筆記本上每一手的響應(yīng)時間在2 s之內(nèi).圖3和圖4為此軟件的運行結(jié)果圖，其中圖3是與開源軟件OAsE-NoG0的對弈結(jié)果.

同時，此算法實現(xiàn)的程序還可以在普通安卓手機上運行，測試手機為內(nèi)存3 GB，8核，響應(yīng)時間在2 s之內(nèi).結(jié)果如圖5所示.

4.2效果對比

表1是本文系統(tǒng)與OASE-NoGo軟件的對弈結(jié)果及勝率統(tǒng)計，本文的勝率均達到90%以上.針對圖6這對奕中的一常見局面，本算法與傳統(tǒng)蒙特卡洛算法的復(fù)雜性對比可以體現(xiàn)出本文算法的可行性和高效性.

文獻中所實現(xiàn)的程序與OASE-NoGo V1.1初級的對弈勝率為90%，小于本文中程序的勝率.

復(fù)雜性對比方面，圖6為對弈中的某一局面，按照理論，MCTS算法在足夠長的時間中才能給出標記點結(jié)果，而本文算法在1 s內(nèi)即給出與MCTS算法相同結(jié)果，即交叉點為最佳選點.而當(dāng)MCTS算法沒有足夠時間模擬時，將可能不能得到此結(jié)果，具體分析如下.

MCTS算法計算過程：當(dāng)前落子顏色為黑，可下點為65個.通過模式匹配、快速估計等方式找出3到4個候選點，其中包括標記點.之后在規(guī)定時間內(nèi)對所有候選點進行盡可能多的蒙特卡洛模擬，一次模擬的方式為采用黑一手、白一手的交替落子方式將棋至終局，若黑勝，則給此候選點加特定分數(shù)，若黑負，則減少特定分數(shù)，在最后時間用完時比較幾個候選點的分數(shù)，選擇分數(shù)最高的點為最佳.顯而易見，此算法將消耗大量的時間空間，且若時間不充分，模擬次數(shù)不夠，則評分不一定準確，不能保證得出最佳結(jié)果.

本文系統(tǒng)算法計算過程：可下點為65個，對所有點進行一次價值評估計算，即進行130次黑白是否能夠落子的判斷;之后進行65次加法運算，可得到標記處和標記出左邊的交叉點價值最高，為1，其他點均為0;后對這兩個候選點進行第二次計算，分別將計算128次是否落子的判斷和64次加法運算，可得到標記出第二次計算的價值為1，而標記出左邊的交叉點第二次計算的價值為0.因此得出最佳結(jié)果，運行時間為1 s之內(nèi).

5結(jié)論

針對當(dāng)前不圍棋人工智能中使用蒙特卡洛思想帶來的不足之處，結(jié)合不圍棋本身的博弈特點，本文給出了全新的基于價值評估函數(shù)的遞歸的解決方法;詳細介紹了價值評估模型的構(gòu)建和價值函數(shù)的計算過程;針對在價值評估中會出現(xiàn)的多候選點問題，提出了打散規(guī)則和使用遞歸這一思想，使這一難點得以解決.以上述算法為核心的軟件在實驗結(jié)果中取得了較好的效果，證明了本文算法的可行性和有效性.