基于價值評估的不圍棋遞歸算法

郭倩宇 陳優廣

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

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

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

0引言

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

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

1不圍棋及其規則

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

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

2不圍棋人工智能研究現狀

2.1研究歷程

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

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

2.2 MCTS算法及其不足之處

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

MCTS方法主要包括以下4個方面的內容.

（1）搜索：從博弈樹的根節點（即終局狀態）向下搜索直至當前的葉子結點（即當前局面）.

（2）擴展：對當前的博弈樹葉子結點進行擴展.

f3）模擬：從當前的博弈樹葉子結點開始進行蒙特卡洛概率模擬并給出一個蒙特卡洛概率統計數值.

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

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

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

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

3.1不圍棋行棋思路及價值評估函數的構建

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

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

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

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

3.2.1打散規則

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

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

打散功能函數具體步驟如下.

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

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

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

3.2.2遞歸算法步驟

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

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

第二步：依次將所有候選點設置為當前行棋的棋子（黑子或白子）.

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

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

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

4實驗結果

4.1功能展示

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

同時，此算法實現的程序還可以在普通安卓手機上運行，測試手機為內存3 GB，8核，響應時間在2 s之內.結果如圖5所示.

4.2效果對比

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

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

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

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

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

5結論

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