基于強化學習的蘇拉卡爾塔博弈算法

王仁泉， 丁 濛， 李淑琴， 石露穎， 戚譯中， 劉朔言

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

0 引 言

自計算機誕生以來，機器博弈就是其重要的研究方向，被稱為計算機領域的“果蠅”。 很多人工智能領域的方法及技術都在其上進行了實驗和應用。

機器博弈研究的發展主要分為兩個階段。 第一階段，利用手工構造的估值函數權重，輔以搜索樹剪枝，以降低計算復雜度，這個方法也被稱為傳統方法。 在此期間，最引人注目是1997 年，深藍打敗了國際象棋大師加里· 卡斯帕羅夫（ Garry Kasparov）［1］。 但傳統方法面臨著兩大挑戰：一是手工構造的估值函數實際上是一個專家系統，對函數的構造具有很高的要求；二是計算難度大，Allis 曾計算［2］出，國際象棋搜索樹的復雜度為10123、中國象棋為10150，而圍棋的搜索樹復雜度則為10360，這對機器的運算能力提出巨大的挑戰。 鑒于以上原因，近年來許多學者引入人工智能的自學習方法進行優化和學習，使機器博弈進入第二階段，即機器學習方法。 主要方法包括差分學習方法［3-5］和基于蒙特卡洛樹搜索的神經網絡方法［6］。 將人工神經元引入機器博弈的評估函數，通過強化學習方法，表現了走子的內在邏輯和潛在規則。

本文介紹了自學習方法與蘇拉卡爾塔棋機器博弈的階段性成果，該方法主要是將神經元與蒙特卡羅方法結合，引入蘇拉卡爾塔機器博弈的評估函數，通過自對弈方法，獲得大量對局數據，并通過反向傳播算法［7］提高神經網絡的評估能力。

程序的代碼已經發布： https：／／github.com／jimages／surakarta－cpp

1 蘇拉卡爾塔棋簡介

蘇拉卡爾塔棋（Surakarta）是源自印尼爪哇島的兩人吃子類別的游戲。 棋盤由6x6 的正方形網絡和4 個角落上的圓弧構成，正方形網格構成的交叉點為落子的棋子位置。 雙方采用不同的顏色，各十二枚，一般采用黑白或者紅黑兩色。 棋局開始時，雙方在各自的底線排成兩排，如圖1 所示。

圖1 蘇拉卡爾塔棋盤、棋子以及開局布局Fig.1 Iayout of the Surakarta and Opening

在游戲開始時，雙方輪流走棋，每次可以移動一個棋子或者吃掉對方的棋子。 當移動棋子時，只能沿垂直或者對角方向走動一格，并且在該位置上沒有己方或者對方的棋子。 而當需要吃掉對方的棋子時，則需要經過至少一條完整的弧線，并且在我方棋子對對方棋子的路徑上沒有棋子阻礙。 游戲以吃掉對方棋子獲取勝利，比賽結果以剩余棋子多的一方獲勝。

2 基于蒙特卡洛樹搜索的神經網絡博弈方法

2.1 樹搜索方法

通過使用蒙特卡洛方法，在樹中對每一個棋局狀態進行搜索。 隨著模擬次數的增多，搜索樹的深度和廣度越來越大，并且對棋局的評估越來越接近實際情況。 因此，隨著搜索時間的增多，選擇具有高價值的子節點，算法選擇的策略則越來越好。

神經網絡為殘差卷積神經網絡fθ，其中θ 為神經網絡的參數，輸入值為當前對局的局面s，p 為將棋子移動到某個點的概率，值為0～1。v 是當前局面的評分，表示當前局面對我方的有利或不利程度，值為－1－－1， －1 表示輸、1 表示贏。 表達形式如下：

對于蒙特卡洛搜索樹中的每一個節點，都存儲了以下值；

其中，N (s，a) 表示該節點的訪問次數。W（s，a）表示評估值的總和。 Q（s，a） 表示評估值的平均。P（s，a） 表示在父親節點來看選擇該節點的概率值。蒙特卡洛樹搜索通過以下步驟選擇最優的下棋方法：

（1）選擇

搜索開始時，要從根節點到達葉子節點。 在這個過程中，需要不斷的選擇搜索的節點，直到葉子節點。 當選擇子節點時，通過PUCT 變種算法計算每個子節點的選擇值［8］，并選擇其中選擇值最大的節點。

其中：

式中， Q (s，a) 表示對于子節點的評估的平均值；∑bN（s，b） 表示所有子節點訪問次數的總和，即父節點的訪問次數N（sp，ap），cpuct為一個常數；用于控制探索更多節點和利用已有信息的平衡。

（2）擴展和評估

當通過選擇到達葉子節點時，對于局面s 通過神經網絡進行前向推理獲得p 和v。 對于可行域中的每一個可行動作a，新建對應的節點edge（s，a），值被初始化為｛N (s，a) ＝0，W (s，a) ＝0，Q (s，a) ＝0，P (s，a) ＝p｝，而對于v 將進行回溯更新。

（3）回溯更新

當葉子節點被擴展和評估后，將按照搜索樹的選擇自下而上對所有祖輩節點回溯更新，所有祖輩節點的訪問次數均加一，即N (s，a) ＝N (s，a) ＋1。對于評估值的總和以及均值則根據行動方加v 或者－ v，即若當前的下棋方為評估局面方，則W (s，a) ＝W (s，a) ＋ v；若為評估局面方的對手方，則W (s，a) ＝W (s，a) － v。 同時均值也相應的更新為

（4）選擇最優行動

經過多次選擇、評估和擴展、回溯更新之后，則根據所有可行域的訪問次數得到選擇行動的概率其中， τ 為控制探索程度的溫度參數，訓練時τ ＝1，使得探索更多的可行域以提高探索程度；而當進行性能評估或對局時τ→0，盡可能獲得更優的局面。

2.2 神經網絡

與傳統方法不同，機器學習方法并不需要特別的特征設計，只需要將棋盤數據和歷史數據輸入到網絡中即可。 本文使用的輸入特征見表1。 值得注意的是，與圍棋不同，蘇拉卡爾塔為移動型棋子，即把棋子從某一個位置移動到另外一個位置。 本文使用一個平面表示移動棋子的位置，用另一個平面表示棋子移動到的位置。 除此之外，使用了一個平面指示當前是否為先手方，若為先手方，則該平面全置為1，否則置為0。

表1 輸入特征Tab.1 Feature Representation

神經網絡為6 層卷積殘差網絡，根據策略網絡（見表2）和價值網絡（見表3）分為2 個部分。 策略網絡為36?36 的輸出，表示所有可行的移動。 價值網絡為1 的神經元。

表2 策略網絡Tab.2 Policy Network

表3 價值網絡Tab.3 Value Network

隨機初始化神經網絡后，運用基于蒙特卡洛樹搜索的神經網絡方法進行自對弈，收集對弈數據（s，π，z）。 對于雙方的歷史棋局，結束時的棋局為sL，則對于所有歷史局面sll ≤L， 得到選擇行動的概率值π（a ｜sl）， 同時根據棋局最后的勝負結果，給予勝負值z ∈｛1，－1｝，即若當前方勝利z ＝1，否則z ＝－ 1。 為了防止過擬合［9］，程序將所有自對弈的歷史放入到數據集中，當完成一定數量的自對弈后，則從數據集中采樣一定數量的歷史數據，通過反向傳播算法對神經網絡訓練。 損失函數由交叉熵和平方差兩部分組成，即對于某一歷史：

其中，c 為控制L2 正則化的參數。

2.3 并行訓練方法

為了加快自對弈速度，本文使用了根并行方法［10］，如圖2 所示。 當自對弈需要評估和擴展節點時，程序把當前局面發送到評估隊列中，評估服務器按批進行前向推理并返回相應的自對弈程序。 當一局自對弈程序完成后，對弈程序將局歷史發送到訓練服務器，訓練服務器維護一個訓練數據集池，訓練服務器將數據加入到數據集池后，從數據池中采樣進行一次反向傳播計算更新權重。 同時每1 min，訓練服務器和評估服務器進行一次權重的同步，以保證評估服務器的權重是最新的。

圖2 并行訓練架構Fig.2 Architecture of Parallel Training

3 實驗

為了檢驗實際訓練效果，神經網絡在訓練和評估時，cpuct＝2；對于溫度控制常量，訓練時τ ＝1，性能評估時τ ＝0.1。 訓練中，選擇走子時僅進行了1 600次模擬。 而在評估性能時，應適當增加模擬次數，以獲得更好的性能表現。 通過將訓練560 局的神經網絡與訓練1 000局的神經網絡進行100 局對戰，雙方均模擬30 s。 結果證明：1 000局訓練后的神經網絡勝率為60%。 由此可見，隨著訓練局數的增多，神經網絡的水平逐漸提高，使用基于蒙特卡洛樹搜索的神經網絡博弈方法有助于提高蘇拉卡爾塔程序的博弈水平。

4 結束語

本文將基于蒙特卡洛樹搜索的神經網絡博弈方法，應用于蘇拉卡爾塔機器博弈中。 從零知識進行自學習的方案，能在五子棋、圍棋等非移動型棋種上獲得良好效果，但本文的實驗不能證明其方法也適合于移動型棋子。 但經過自學習訓練，程序的水平有明顯的提高，可以斷言，若自對弈上百萬盤，程序的博弈水平必然有更好的提高。 在未來的研究實踐中，還將在優化網絡結構、調整自學習策略、引入人類對戰數據等方面進行探索。