基于價(jià)值評(píng)估的不圍棋遞歸算法

郭倩宇 陳優(yōu)廣

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

關(guān)鍵詞：人工智能;機(jī)器博弈;不圍棋;價(jià)值評(píng)估;遞歸

中圖分類號(hào)：TP399 文獻(xiàn)標(biāo)志碼：A DOI：10.3969/j.issn.1000-5641.2019.01.007

0引言

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

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

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

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

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

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

2.1研究歷程

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

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

2.2 MCTS算法及其不足之處

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

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

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

（2）擴(kuò)展：對(duì)當(dāng)前的博弈樹葉子結(jié)點(diǎn)進(jìn)行擴(kuò)展.

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

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

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

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

3基于價(jià)值評(píng)估的遞歸算法

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

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

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

3.2基于價(jià)值評(píng)估的遞歸算法

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

3.2.1打散規(guī)則

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

在打散規(guī)則中選擇曼哈頓距離d（i，J），且即兩個(gè)點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上的絕對(duì)軸距總和來進(jìn)行打散，使行棋打散程度最大化.

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

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

第二步：計(jì)算所有可下點(diǎn)與棋盤已有子的曼哈頓距離的最小值.

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

3.2.2遞歸算法步驟

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

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

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

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

第四步：對(duì)所有候選點(diǎn)得到的局面進(jìn)行多次價(jià)值評(píng)估，直到有且僅有一個(gè)候選點(diǎn)的價(jià)值最大.

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

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

4.1功能展示

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

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

4.2效果對(duì)比

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

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

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

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

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

5結(jié)論

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