基于AlphaZero 的不圍棋博弈系統研究

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

（北京信息科技大學 計算機學院，北京 100101）

0 引言

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

1 研究現狀

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

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

本文基于AlphaZero 對不圍棋博弈進行研究，使用深度神經網絡和MCTS 搜索組合形成強化學習框架，不斷自我對弈學習博弈知識，優化損失函數，提升不圍棋博弈棋力。

2 不圍棋及其規則［6］

2.1 棋盤

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

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

2.2 棋規

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

（2）對弈的目標不是吃掉對方的棋子，不是像圍棋那樣圍空占領地盤，相反，如果一方落子后吃掉了對方的棋子，則落子一方判負。

（3）如果一方在棋盤上某個交叉點落子后，該棋子將呈現無氣狀態，相當于自殺，落子自殺一方判負。

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

（5）如果有時間限制的，超時一方判負。

（6）對弈結果只有勝負，沒有和棋。

3 基于AlphaZero 不圍棋博弈系統的設計思想［7］

基于AlphaZero 不圍棋博弈系統主要分為3 個階段：自我對戰學習階段，訓練神經網絡階段和評估網絡階段。對此擬做研究分述如下。

3.1 自我對戰學習階段

3.1.1 自我對戰

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

3.1.2 蒙特卡洛樹搜索［8］

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

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

其中，s為搜索樹的一個節點代表的棋局狀態；a表示某一個可行的動作；N（s，a）表示狀態s下可行動作a被選中的次數；P（s，a）表示狀態s下的可行動作a的先驗概率；Q（s，a）表示狀態s下可行動作的平均動作價值；W（s，a）表示狀態s下可行動作的總動作價值；puct表示一個決定探索程度超參數。

（2）擴展和求值：當棋局還沒有結束且當前結點為葉子結點時，就需要進行擴展。擴展的新的結點作為當前結點的子結點，將當前局面輸入神經網絡得到向量p和勝率v。由此得到的數學公式為：

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

其中，st表示搜索樹中當次被遍歷路徑上節點對應的棋局狀態；at表示搜索樹中當次被遍歷路徑上節點對應棋局狀態下選擇的動作；v表示搜索樹中當次被遍歷路徑上節點的價值，由于搜索樹中相鄰2 層的落子方是不同的，因此相鄰2 層的節點價值互為相反數。

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

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

3.2 訓練神經網絡階段

3.2.1 局面描述

使用4 層9?9 的二維特征描述當前局面。9?9 表示棋盤大小。各層的數學表述具體如下。

（1）第一層：表示當前棋局。

（2）第二層：表示白子當前所占的位置。

（3）第三層：表示黑子當前所占的位置。

（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 網絡結構描述［9］

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

圖4 策略價值網絡訓練流程圖Fig.4 Strategy value network training flow chart

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

3.2.3 最小化損失函數

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

其中，z表示真實的對局結果；v表示策略價值網絡輸出的勝率；π為蒙特卡洛樹搜索輸出的概率；p為策略價值網絡輸出的當前局面下每一個可行動作的概率。式（8）的第三項是用于防止過擬合的正則項。

3.3 評估網絡階段

當神經網絡訓練完畢后，進行評估階段，這個階段主要用于確認神經網絡的參數是否得到了優化。這個過程中，自我對戰的雙方各自使用不同訓練程度、不同參數的神經網絡指導MCTS 搜索，并對戰若干局，來檢驗AlphaZero 在新神經網絡參數棋力是否得到了提高。除了神經網絡的參數不同外，這個過程和第一階段的自我對戰學習階段過程是類似的。如果使用新參數后勝率達到55%，就更新參數，而不再使用舊參數。

4 實驗結果與分析

本次研究的不圍棋項目結合上文所提到的算法，使用Python 語言進行編寫，在Windows10 下進行了基于AlphaZero 的不圍棋博弈系統的開發。

實驗中，硬件環境設置如下：i7-8750H，主頻2.2 GHz，內存16 GB，顯卡1060，四核八線程。

表1 是該算法與OASE-NoGo 軟件的對弈結果及勝率統計，該算法的勝率均在90%以上，體現出本文提出算法的可行性和高效性，實現的不圍棋博弈有較強的棋力。

表1 對弈結果統計Tab.1 Statistics of game results

本項目中使用深度學習優化損失函數，最小化自我預測的價值和自我對弈勝者之間的誤差，并最大化神經網絡的走子概率和搜索概率，令博弈程序通過自我對弈學習博弈知識，得到了自我強化，優化了評估函數。

5 結束語

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