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

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

0 引 言

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

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

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

程序的代碼已經(jīng)發(fā)布： https：／／github.com／jimages／surakarta－cpp

1 蘇拉卡爾塔棋簡介

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

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

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

2 基于蒙特卡洛樹搜索的神經(jīng)網(wǎng)絡(luò)博弈方法

2.1 樹搜索方法

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

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

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

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

（1）選擇

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

其中：

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

（2）擴展和評估

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

（3）回溯更新

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

（4）選擇最優(yōu)行動

經(jīng)過多次選擇、評估和擴展、回溯更新之后，則根據(jù)所有可行域的訪問次數(shù)得到選擇行動的概率其中， τ 為控制探索程度的溫度參數(shù)，訓(xùn)練時τ ＝1，使得探索更多的可行域以提高探索程度；而當進行性能評估或?qū)謺rτ→0，盡可能獲得更優(yōu)的局面。

2.2 神經(jīng)網(wǎng)絡(luò)

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

表1 輸入特征Tab.1 Feature Representation

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

表2 策略網(wǎng)絡(luò)Tab.2 Policy Network

表3 價值網(wǎng)絡(luò)Tab.3 Value Network

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

其中，c 為控制L2 正則化的參數(shù)。

2.3 并行訓(xùn)練方法

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

圖2 并行訓(xùn)練架構(gòu)Fig.2 Architecture of Parallel Training

3 實驗

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

4 結(jié)束語

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