高彤彤，丁佳慧，舒文奧，陰思琪

（北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101）

0 引言

作為2012 年出現(xiàn)在大學(xué)生博弈大賽［1］中的一種新棋種，不圍棋迅速在博弈比賽中流行起來。一般情況下，對圍棋的基本理解是消滅敵人取得勝利，而不圍棋則與其相反。不圍棋的規(guī)則不允許有棋子死亡，無論是哪一方自殺、或是吃掉了對方的棋子都會判負(fù)。這種規(guī)則看似不合理，其實(shí)是要求玩家在和平中取勝，最后依然是比較雙方占地盤的多少。從某種角度來說，不圍棋更符合中華傳統(tǒng)文化中“和為貴”的思想。在此背景下，本文提出了基于AlphaZero 的不圍棋博弈系統(tǒng)［2］，通過不斷自我學(xué)習(xí)提高棋力。

1 研究現(xiàn)狀

計(jì)算機(jī)博弈，歷來是人工智能的一個(gè)重要的研究領(lǐng)域，早期人工智能的研究實(shí)踐，正是從計(jì)算機(jī)下棋開始。從1997 年的“深藍(lán)”，再到2016 年谷歌公司研發(fā)的阿爾法圍棋戰(zhàn)勝圍棋世界冠軍，計(jì)算機(jī)博弈取得了可觀的成就。在這期間，蒙特卡洛思想的UCT（Upper Confidence Bound Apply to Tree）算法曾在圍棋人工智能領(lǐng)域主導(dǎo)很長時(shí)間。人們圍繞蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）算法始終在做改進(jìn)和研究，從而不斷提高圍棋棋力。

不圍棋作為研發(fā)時(shí)間不長的新棋種，相關(guān)研究較少。最早對不圍棋的研究報(bào)道出現(xiàn)在2011年，通過對比圍棋發(fā)現(xiàn)，MCTS、快速評估、UCT 等方法在不圍棋中同樣有效。文獻(xiàn)［3-4］都是利用MCTS 解決不圍棋問題。文獻(xiàn)［3］在啟動MCTS 算法時(shí)，優(yōu)先對評分較高的局面進(jìn)行模擬，通過這種方法來盡可能減少模擬次數(shù)。文獻(xiàn)［4］為克服MCTS 計(jì)算復(fù)雜的問題，利用不圍棋博弈本身特點(diǎn)，構(gòu)建了價(jià)值評估模型和函數(shù)，遞歸實(shí)現(xiàn)不圍棋人工智能。文獻(xiàn)［5］提出在對弈過程中進(jìn)行UCT 樹的重用，可以增加5%～30%的搜索深度。

本文基于AlphaZero 對不圍棋博弈進(jìn)行研究，使用深度神經(jīng)網(wǎng)絡(luò)和MCTS 搜索組合形成強(qiáng)化學(xué)習(xí)框架，不斷自我對弈學(xué)習(xí)博弈知識，優(yōu)化損失函數(shù)，提升不圍棋博弈棋力。

2 不圍棋及其規(guī)則［6］

2.1 棋盤

不圍棋使用9×9 棋盤，分別用字母和數(shù)字表示橫縱坐標(biāo)，棋子位置形如C4、E1。棋盤表示如圖1所示。

圖1 棋盤表示Fig.1 Representation of a chessboard

2.2 棋規(guī)

（1）黑棋先行，之后黑白交替落子，落子后棋子不可移動。

（2）對弈的目標(biāo)不是吃掉對方的棋子，不是像圍棋那樣圍空占領(lǐng)地盤，相反，如果一方落子后吃掉了對方的棋子，則落子一方判負(fù)。

（3）如果一方在棋盤上某個(gè)交叉點(diǎn)落子后，該棋子將呈現(xiàn)無氣狀態(tài)，相當(dāng)于自殺，落子自殺一方判負(fù)。

（4）不圍棋對弈中，禁止空手（pass），空手一方判負(fù)。

（5）如果有時(shí)間限制的，超時(shí)一方判負(fù)。

（6）對弈結(jié)果只有勝負(fù)，沒有和棋。

3 基于AlphaZero 不圍棋博弈系統(tǒng)的設(shè)計(jì)思想［7］

基于AlphaZero 不圍棋博弈系統(tǒng)主要分為3 個(gè)階段：自我對戰(zhàn)學(xué)習(xí)階段，訓(xùn)練神經(jīng)網(wǎng)絡(luò)階段和評估網(wǎng)絡(luò)階段。對此擬做研究分述如下。

3.1 自我對戰(zhàn)學(xué)習(xí)階段

3.1.1 自我對戰(zhàn)

自我對戰(zhàn)學(xué)習(xí)階段主要是蒙特卡洛樹搜索進(jìn)行自我對弈，產(chǎn)生大量棋局樣本和勝負(fù)關(guān)系的過程，由于AlphaZero 并不使用大師的棋局來學(xué)習(xí)，而在沒有對戰(zhàn)數(shù)據(jù)基礎(chǔ)的前提下訓(xùn)練效率不高，因此需要蒙特卡洛樹搜索進(jìn)行自我對弈得到訓(xùn)練數(shù)據(jù)用于后續(xù)神經(jīng)網(wǎng)絡(luò)的訓(xùn)練。在自我對戰(zhàn)學(xué)習(xí)階段，每一步的落子是由MCTS 搜索來完成的。在MCTS 搜索的過程中，遇到不在樹中的狀態(tài)，則使用神經(jīng)網(wǎng)絡(luò)的結(jié)果來更新MCTS 樹結(jié)構(gòu)上保存的內(nèi)容。而每一次的迭代過程中，在每個(gè)棋局當(dāng)前狀態(tài)s下，每一次移動使用1 600 次MCTS 搜索模擬。最終MCTS 給出最優(yōu)的落子策略π，這個(gè)策略π和神經(jīng)網(wǎng)絡(luò)的下一步輸出p是不一樣的，此時(shí)的神經(jīng)網(wǎng)絡(luò)還沒有進(jìn)行訓(xùn)練。當(dāng)每一局對戰(zhàn)結(jié)束后，可以得到在s棋局狀態(tài)下，使用落子策略π 最終的勝負(fù)獎勵z，z為1 或者-1，這取決于游戲的勝負(fù)，如此一來，就可以得到非常多的樣本（s，π，z），這些數(shù)據(jù)可以用來訓(xùn)練神經(jīng)網(wǎng)絡(luò)。

3.1.2 蒙特卡洛樹搜索［8］

MCTS 就是用來自對弈生成棋譜的。MCTS 樹中保存的數(shù)據(jù)包括N（s，a）、W（s，a）、Q（s，a）、P（s，a），分別表示狀態(tài)s下可行動作a被選中的次數(shù)、總的行動價(jià)值、平均行動價(jià)值、可行動作a的先驗(yàn)概率。搜索過程主要由選擇、擴(kuò)展求值、仿真回溯三部分組成，經(jīng)過多次模擬后落子。這里對此將給出闡釋論述如下。

（1）選擇：選擇平均行動價(jià)值與總行動價(jià)值之和Q（s，a）+U（s，a）最大的action搜索分支，U（s，a）和Q（s，a）的計(jì)算公式如下所示：

其中，s為搜索樹的一個(gè)節(jié)點(diǎn)代表的棋局狀態(tài)；a表示某一個(gè)可行的動作；N（s，a）表示狀態(tài)s下可行動作a被選中的次數(shù)；P（s，a）表示狀態(tài)s下的可行動作a的先驗(yàn)概率；Q（s，a）表示狀態(tài)s下可行動作的平均動作價(jià)值；W（s，a）表示狀態(tài)s下可行動作的總動作價(jià)值；puct表示一個(gè)決定探索程度超參數(shù)。

（2）擴(kuò)展和求值：當(dāng)棋局還沒有結(jié)束且當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)，就需要進(jìn)行擴(kuò)展。擴(kuò)展的新的結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn)，將當(dāng)前局面輸入神經(jīng)網(wǎng)絡(luò)得到向量p和勝率v。由此得到的數(shù)學(xué)公式為：

（3）仿真回溯：如果已被擴(kuò)展的局面進(jìn)行選擇操作分出了勝負(fù)，或者未擴(kuò)展的局面執(zhí)行擴(kuò)展操作，則將勝率回傳給上一層，對上一層的值進(jìn)行更新，被選中的次數(shù)加1，總的行動價(jià)值加v，并重新計(jì)算平均行動價(jià)值。此時(shí)需用到的數(shù)學(xué)公式分別如以下公式所示：

其中，st表示搜索樹中當(dāng)次被遍歷路徑上節(jié)點(diǎn)對應(yīng)的棋局狀態(tài)；at表示搜索樹中當(dāng)次被遍歷路徑上節(jié)點(diǎn)對應(yīng)棋局狀態(tài)下選擇的動作；v表示搜索樹中當(dāng)次被遍歷路徑上節(jié)點(diǎn)的價(jià)值，由于搜索樹中相鄰2 層的落子方是不同的，因此相鄰2 層的節(jié)點(diǎn)價(jià)值互為相反數(shù)。

（4）落子：往棋盤上落一個(gè)棋子之前，會進(jìn)行1 600次模擬，每次模擬都包含上面的3 個(gè)步驟，在此基礎(chǔ)上MCTS 才會做出真正的決策。文中推導(dǎo)得到的公式可表示為：

其中，τ為溫度參數(shù)，控制探索的程度。τ越大，不同走法間差異變小，探索比例增大。反之，則更多選擇當(dāng)前最優(yōu)操作。在零狗中，每一次自我對弈的前30步，參數(shù)τ＝1，即早期鼓勵探索。游戲剩下的步數(shù)，該參數(shù)將逐漸降低至0。如果是比賽，則直接為0。

3.2 訓(xùn)練神經(jīng)網(wǎng)絡(luò)階段

3.2.1 局面描述

使用4 層9?9 的二維特征描述當(dāng)前局面。9?9 表示棋盤大小。各層的數(shù)學(xué)表述具體如下。

（1）第一層：表示當(dāng)前棋局。

（2）第二層：表示白子當(dāng)前所占的位置。

（3）第三層：表示黑子當(dāng)前所占的位置。

（4）第四層：表示哪一方先下棋，如果該下黑子，則矩陣全部等于1；如果該下白子，則矩陣全部等于0。

以圖2 局面為例，分析4 層特征，即如圖3 所示。

圖2 局面描述Fig.2 A description of the situation

圖3 各層特征詳解Fig.3 Detailed explanation of the characteristics of each layer

3.2.2 網(wǎng)絡(luò)結(jié)構(gòu)描述［9］

策略價(jià)值網(wǎng)絡(luò)訓(xùn)練流程如圖4 所示。使用卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）進(jìn)行策略價(jià)值網(wǎng)絡(luò)的訓(xùn)練。CNN 結(jié)構(gòu)比較簡單，由公共網(wǎng)絡(luò)層、行動策略層和狀態(tài)價(jià)值網(wǎng)絡(luò)層構(gòu)成。AlphaZero 需要策略網(wǎng)絡(luò)輸出各個(gè)動作先驗(yàn)概率以及價(jià)值網(wǎng)絡(luò)評判當(dāng)前棋局狀態(tài)的好壞。在AlphaZero 中策略網(wǎng)絡(luò)和估值網(wǎng)絡(luò)共享一部分的卷積層，共享的卷積層為3層，分別使用32、64、128 個(gè)3×3 的filter，使用relu激活函數(shù)，此后再分成策略policy和價(jià)值value兩個(gè)輸出。在policy這一端，先使用4 個(gè)1×1 的filter 進(jìn)行降維，再接一個(gè)全連接層、內(nèi)有81 個(gè)神經(jīng)元，使用softmax非線性函數(shù)直接輸出棋盤上所有可能的走子概率。在value這一端，先使用2 個(gè)1×1 的filter 進(jìn)行降維，再接一個(gè)全連接層、內(nèi)有64 個(gè)神經(jīng)元，最后再接一個(gè)全連接層，使用tanh 非線性函數(shù)輸出局面評分。

圖4 策略價(jià)值網(wǎng)絡(luò)訓(xùn)練流程圖Fig.4 Strategy value network training flow chart

該方法既能避免人工設(shè)計(jì)復(fù)雜的靜態(tài)評估函數(shù)，又能較好地解決傳統(tǒng)的智能博弈程序中搜索用時(shí)巨大、智力水平受程序編寫者對博弈技巧理解水平的限制的問題。

3.2.3 最小化損失函數(shù)

神經(jīng)網(wǎng)絡(luò)的輸入為當(dāng)前的局面s，輸出為下一步行動的概率p和對于當(dāng)前局面勝率的估計(jì)v。在訓(xùn)練神經(jīng)網(wǎng)絡(luò)階段，使用自我對戰(zhàn)學(xué)習(xí)階段得到的樣本集合（s，π，z），訓(xùn)練策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)的模型參數(shù)。訓(xùn)練的目標(biāo)是讓策略價(jià)值網(wǎng)絡(luò)輸出的當(dāng)前局面下每一個(gè)可行動作的概率p更加接近蒙特卡洛樹搜索輸出的概率π，讓策略價(jià)值網(wǎng)絡(luò)輸出的局面評分v更加接近真實(shí)的對局結(jié)果z。在自我對弈數(shù)據(jù)集上不斷地最小化損失函數(shù)，如式（8）所示：

其中，z表示真實(shí)的對局結(jié)果；v表示策略價(jià)值網(wǎng)絡(luò)輸出的勝率；π為蒙特卡洛樹搜索輸出的概率；p為策略價(jià)值網(wǎng)絡(luò)輸出的當(dāng)前局面下每一個(gè)可行動作的概率。式（8）的第三項(xiàng)是用于防止過擬合的正則項(xiàng)。

3.3 評估網(wǎng)絡(luò)階段

當(dāng)神經(jīng)網(wǎng)絡(luò)訓(xùn)練完畢后，進(jìn)行評估階段，這個(gè)階段主要用于確認(rèn)神經(jīng)網(wǎng)絡(luò)的參數(shù)是否得到了優(yōu)化。這個(gè)過程中，自我對戰(zhàn)的雙方各自使用不同訓(xùn)練程度、不同參數(shù)的神經(jīng)網(wǎng)絡(luò)指導(dǎo)MCTS 搜索，并對戰(zhàn)若干局，來檢驗(yàn)AlphaZero 在新神經(jīng)網(wǎng)絡(luò)參數(shù)棋力是否得到了提高。除了神經(jīng)網(wǎng)絡(luò)的參數(shù)不同外，這個(gè)過程和第一階段的自我對戰(zhàn)學(xué)習(xí)階段過程是類似的。如果使用新參數(shù)后勝率達(dá)到55%，就更新參數(shù)，而不再使用舊參數(shù)。

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

本次研究的不圍棋項(xiàng)目結(jié)合上文所提到的算法，使用Python 語言進(jìn)行編寫，在Windows10 下進(jìn)行了基于AlphaZero 的不圍棋博弈系統(tǒng)的開發(fā)。

實(shí)驗(yàn)中，硬件環(huán)境設(shè)置如下：i7-8750H，主頻2.2 GHz，內(nèi)存16 GB，顯卡1060，四核八線程。

表1 是該算法與OASE-NoGo 軟件的對弈結(jié)果及勝率統(tǒng)計(jì)，該算法的勝率均在90%以上，體現(xiàn)出本文提出算法的可行性和高效性，實(shí)現(xiàn)的不圍棋博弈有較強(qiáng)的棋力。

表1 對弈結(jié)果統(tǒng)計(jì)Tab.1 Statistics of game results

本項(xiàng)目中使用深度學(xué)習(xí)優(yōu)化損失函數(shù)，最小化自我預(yù)測的價(jià)值和自我對弈勝者之間的誤差，并最大化神經(jīng)網(wǎng)絡(luò)的走子概率和搜索概率，令博弈程序通過自我對弈學(xué)習(xí)博弈知識，得到了自我強(qiáng)化，優(yōu)化了評估函數(shù)。

5 結(jié)束語

針對不圍棋本身的博弈特點(diǎn)，本文給出了基于AlphaZero 的不圍棋博弈系統(tǒng)，詳細(xì)介紹了算法的訓(xùn)練過程。在與開源軟件OASE-NoGo 的多次對弈實(shí)驗(yàn)中，本文算法取得了90%以上的勝率，證明了本文算法的可行性和有效性。