基于強(qiáng)化學(xué)習(xí)的蘇拉卡爾塔博弈算法

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

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

0 引 言

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

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

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

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

1 蘇拉卡爾塔棋簡(jiǎn)介

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

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

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

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

2.1 樹(shù)搜索方法

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

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

對(duì)于蒙特卡洛搜索樹(shù)中的每一個(gè)節(jié)點(diǎn)，都存儲(chǔ)了以下值；

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

（1）選擇

搜索開(kāi)始時(shí)，要從根節(jié)點(diǎn)到達(dá)葉子節(jié)點(diǎn)。 在這個(gè)過(guò)程中，需要不斷的選擇搜索的節(jié)點(diǎn)，直到葉子節(jié)點(diǎn)。 當(dāng)選擇子節(jié)點(diǎn)時(shí)，通過(guò)PUCT 變種算法計(jì)算每個(gè)子節(jié)點(diǎn)的選擇值［8］，并選擇其中選擇值最大的節(jié)點(diǎn)。

其中：

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

（2）擴(kuò)展和評(píng)估

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

（3）回溯更新

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

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

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

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

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

表1 輸入特征Tab.1 Feature Representation

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)

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

4 結(jié)束語(yǔ)

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