一種自學(xué)習(xí)的智能五子棋算法的設(shè)計(jì)與實(shí)現(xiàn)

李大舟，沈雪雁，高 巍，張小明，孟智慧，2

1(沈陽化工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，沈陽110142)

2(中國移動(dòng)集團(tuán)設(shè)計(jì)院有限公司河北分公司，太原030000)

1 引 言

五子棋起源于中國古代的傳統(tǒng)黑白棋種之一，屬于一種策略性的游戲類型.在現(xiàn)代，日本將五子棋稱為“連珠”，而其常見的英文名稱為“Gobang”或者“Five in a row”(其縮寫形式為FIR)，五子棋在中國還演變出了“五目”、“五子連”等一些名稱、五子棋游戲?qū)嶋H的規(guī)則非常簡單，而且游戲過程中的變化也比較多，入門非常容易，因此，受到了廣泛的喜愛［1］.由于五子棋游戲有很大的分支因素，采用暴力搜索得到結(jié)果的方法往往會(huì)使得搜索樹的深度非常大，這不僅僅會(huì)使得耗時(shí)巨大，并且計(jì)算機(jī)的性能很難滿足需要.因此，想在計(jì)算資源有限的短時(shí)間內(nèi)找出一種必勝的策略顯然是件非常困難的事情.而使用蒙特卡洛樹搜索對五子棋對弈進(jìn)行模擬，不需要窮舉所有組合，就可以找到最優(yōu)或者次優(yōu)的移動(dòng)方案.

本文將探究基于蒙特卡洛樹搜索與深度神經(jīng)網(wǎng)絡(luò)的智能五子棋算法的實(shí)現(xiàn)過程，本算法完全由自對弈強(qiáng)化學(xué)習(xí)訓(xùn)練，從隨機(jī)游戲開始，沒有任何監(jiān)督或使用人類數(shù)據(jù)，只使用五子棋棋盤上的棋子狀態(tài)作為輸入特征，并且使用單一的深度神經(jīng)網(wǎng)絡(luò)，而不是單獨(dú)的策略和價(jià)值網(wǎng)絡(luò).本算法使用蒙特卡洛樹搜索依賴于這個(gè)單一深度神經(jīng)網(wǎng)絡(luò)來評估落子位置和樣本移動(dòng)，從而選擇最有價(jià)值的落子方式.

本算法訓(xùn)練過程主要分為三個(gè)階段:自我對弈階段，訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)階段和評估深度神經(jīng)網(wǎng)絡(luò)階段.

1)自我對弈階段:實(shí)驗(yàn)在自我對弈階段產(chǎn)生大量棋局樣本作為訓(xùn)練數(shù)據(jù)用于后續(xù)神經(jīng)網(wǎng)絡(luò)的訓(xùn)練.在自我對弈階段，每一步落子由蒙特卡洛樹搜索完成，將蒙特卡洛樹搜索得到的落子策略與最終的勝負(fù)獎(jiǎng)勵(lì)用于訓(xùn)練深度神經(jīng)網(wǎng)絡(luò).

2)訓(xùn)練深度神經(jīng)網(wǎng)絡(luò):通過訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)，優(yōu)化深度神經(jīng)網(wǎng)絡(luò)的參數(shù)，用于后續(xù)指導(dǎo)蒙特卡洛樹搜索過程.

3)評估深度神經(jīng)網(wǎng)絡(luò):自我對弈的雙方各自使用自己的深度神經(jīng)網(wǎng)絡(luò)指導(dǎo)蒙特卡洛樹搜索并對戰(zhàn)，檢驗(yàn)本算法在新的深度神經(jīng)網(wǎng)絡(luò)參數(shù)下的棋力是否得到提升.

2 相關(guān)研究

隨著人工智能近幾年的飛速發(fā)展，人工智能成為了許多國家的重點(diǎn)研究項(xiàng)目.最優(yōu)化策略是人工智能研究的一個(gè)分支，博弈論則是其代表性算法，許多研究者把博弈論應(yīng)用到各種棋類游戲中.2018 年孫世文使用了極大極小值算法對整個(gè)博弈樹的搜索全過程進(jìn)行了優(yōu)化處理，針對五子棋的智能算法思路進(jìn)行了探究和優(yōu)化［2］.2019 年宋萬洋采用 α-β 剪枝樹算法實(shí)現(xiàn)設(shè)計(jì)并研發(fā)了一種基于智能算法的安卓五子棋應(yīng)用程序，程序具有較高智能程度，能夠擊敗大多數(shù)業(yè)余選手［3］.

蒙特卡洛樹搜索可以較為有效地解決一些探索空間巨大的問題，一般的圍棋算法都是基于蒙特卡洛樹搜索實(shí)現(xiàn)的，AlphaGo Zero 用的就是蒙特卡羅樹搜索算法的一種.2011 年Sylvain Gelly 等人基于蒙特卡羅模擬的新搜索范例徹底改變了計(jì)算機(jī)圍棋計(jì)劃的性能，并在理論上和實(shí)踐中首次全面描述了蒙特卡羅樹搜索的擴(kuò)展框架［4］.2012 年 Vien 等人研究了一種基于蒙特卡洛樹搜索算法的大型POMDPs 在線學(xué)習(xí)算法，用于解決貝葉斯強(qiáng)化學(xué)習(xí)問題［5］.2018 年Chenjun Xiao等人提出了記憶增強(qiáng)的蒙特卡洛樹搜索方法，提供了利用在線實(shí)時(shí)搜索的泛化能力的新方法.

在 2016 年 3 月，DeepMind 研發(fā)的 AlphaGo 以 4:1 的成績，擊敗了曾榮獲18 次世界冠軍的圍棋選手李世石［6］.在2017 年 10 月 18 日，DeepMind 又再次取得了突破，揭示了一種新的算法——AlphaGo Zero，它以100:0 的成績打敗了AlphaGo［7］.并且完全從零開始，通過自我博弈，逐漸學(xué)會(huì)了能打敗自己之前的策略.至此，開發(fā)一個(gè)超級AI 不再需要依賴人類專家的游戲數(shù)據(jù)庫了.僅48 天后的2017 年12 月5日，DeepMind 又展示了AlphaGo Zero 如何能夠?qū)W會(huì)國際象棋和象棋.整個(gè)學(xué)習(xí)過程，從第一次參與游戲到成為世界上最厲害的計(jì)算機(jī)程序，只用了24 小時(shí)［8］.

隨著AlphaGo 的成功，強(qiáng)化學(xué)習(xí)成為了當(dāng)下機(jī)器學(xué)習(xí)中最熱門的研究領(lǐng)域之一.2018 年Xingyu Wang 等人提出在已知專家證明不是最優(yōu)的時(shí)候，在零和隨機(jī)博弈中進(jìn)行逆強(qiáng)化學(xué)習(xí);引入了一種新的目標(biāo)函數(shù)，直接將專家與納什均衡策略對立起來，以深度神經(jīng)網(wǎng)絡(luò)作為模型逼近，在逆強(qiáng)化學(xué)習(xí)的背景下求解獎(jiǎng)勵(lì)函數(shù)［9］.同年，Rachit Dubey 等人提出調(diào)查各種有助于人類學(xué)習(xí)的先驗(yàn)知識，并發(fā)現(xiàn)對象的一般先驗(yàn)在指導(dǎo)人類游戲玩法中起著最關(guān)鍵的作用［10］.2019 年，Andre Barreto 等人使用通用的策略改進(jìn)和繼承特性來進(jìn)行傳輸技能，以兩種方式擴(kuò)展了 SF 和 GPI 框架［11］.

3 工作原理

本算法主要包括兩部分:蒙特卡洛樹搜索與深度神經(jīng)網(wǎng)絡(luò).蒙特卡洛樹搜索通過自我對弈進(jìn)行五子棋游戲，將游戲過程中產(chǎn)生的棋盤數(shù)據(jù)作為深度神經(jīng)網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù).棋盤上每個(gè)位置的落子概率以及獲勝概率會(huì)隨著蒙特卡洛樹搜索的不斷執(zhí)行而趨于穩(wěn)定，其與深度神經(jīng)網(wǎng)絡(luò)輸出的落子概率和勝率之差構(gòu)成損失函數(shù).深度神經(jīng)網(wǎng)絡(luò)對于落子概率和獲勝概率的估算將隨著訓(xùn)練的不斷進(jìn)行越來越準(zhǔn)確.在之后的對局中，深度神經(jīng)網(wǎng)絡(luò)可以達(dá)到蒙特卡洛樹搜索的模擬效果，估算出在游戲中未模擬過下法的獲勝概率.

3.1 蒙特卡洛樹搜索

通過給定的一個(gè)游戲狀態(tài)來選擇最佳的下一步是蒙特卡洛樹搜索的主要目標(biāo).一組沿著博弈樹向下的遍歷過程即為搜索，是蒙特卡洛樹搜索的主要概念.蒙特卡洛樹搜索根據(jù)多次模擬博弈的結(jié)果預(yù)測出最優(yōu)的移動(dòng)方案.其中單次遍歷的路徑以當(dāng)前博弈狀態(tài)作為根節(jié)點(diǎn)，延伸到子節(jié)點(diǎn)至少有一個(gè)未被訪問到的未完全展開的節(jié)點(diǎn).此時(shí)其中一個(gè)未被訪問的子節(jié)點(diǎn)將會(huì)作為單次模擬的根節(jié)點(diǎn)，隨后模擬的結(jié)果將會(huì)反向傳播回當(dāng)前樹的根節(jié)點(diǎn)并更新博弈樹的節(jié)點(diǎn)統(tǒng)計(jì)數(shù)據(jù).當(dāng)受限于計(jì)算力或時(shí)間搜索終止，下一步行動(dòng)將基于收集到的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行決策.

本文在實(shí)際實(shí)驗(yàn)過程中將五子棋棋盤大小設(shè)置為15×15 的標(biāo)準(zhǔn)五子棋棋盤.為方便算法講解，以棋盤大小為7×7的五子棋對局為例，深度神經(jīng)網(wǎng)絡(luò)記作fθ，假設(shè)當(dāng)前游戲狀態(tài)為s，fθ根據(jù)當(dāng)前游戲狀態(tài)輸出一個(gè)動(dòng)作概率向量 p，表示五子棋盤上每個(gè)位置的落子概率;以及一個(gè)估值標(biāo)量v，對應(yīng)當(dāng)前游戲狀態(tài)的獲勝概率.蒙特卡洛樹搜索以p 和v 作為搜索方向依據(jù)，既降低了其時(shí)間復(fù)雜度，也使得強(qiáng)化學(xué)習(xí)在訓(xùn)練過程中的穩(wěn)定性得以提升.

針對棋盤大小為7×7 的一個(gè)五子棋對局，其游戲狀態(tài)對應(yīng)的蒙特卡洛樹搜索流程如圖1 所示.將當(dāng)前五子棋對局的游戲狀態(tài)s 作為根節(jié)點(diǎn)，從根節(jié)點(diǎn)開始選擇一個(gè)落子動(dòng)作到達(dá)葉子節(jié)點(diǎn)，其中，節(jié)點(diǎn)訪問次數(shù)C(s，d)、累計(jì)行動(dòng)價(jià)值E(s，d)、平均行動(dòng)價(jià)值 Q(s，d)、先驗(yàn)概率 P(s，d)這四個(gè)值儲(chǔ)存在節(jié)點(diǎn)與節(jié)點(diǎn)之間的邊r(s，d)中.在整個(gè)搜索過程中具體分為以下四個(gè)階段:選擇階段、展開與評估階段、回傳階段，最后執(zhí)行階段通過蒙特卡洛樹搜索γθ得到落子概率分布π.

3.1.1 選擇階段

從圖1 中所示初始五子棋游戲狀態(tài)s0作為根節(jié)點(diǎn)，選擇一個(gè)落子動(dòng)作d 進(jìn)行走子.其中Q(s，d)+U(s，d)取值最大的動(dòng)作d 將被蒙特卡洛樹搜索選擇為搜索路徑.第一步選擇最大值為0.207 的動(dòng)作d，第二步選擇最大值為0.326 的動(dòng)作d，如圖1 中選擇階段所示.其中相關(guān)公式如式(1)、式(2)所示.

其中，本文將超參數(shù)cpuct設(shè)定為1，用來平衡分配搜索過程中探索與利用之間的權(quán)重［7］，搜索樹會(huì)在這個(gè)值較大時(shí)趨向于向未模擬過的落子點(diǎn)探索，在其較小時(shí)則會(huì)快速收斂.這種搜索方式最初會(huì)傾向于先驗(yàn)概率P(s，d)較高和節(jié)點(diǎn)訪問次數(shù)C(s，d)較低的落子動(dòng)作，之后會(huì)漸漸傾向于平均行動(dòng)價(jià)值Q(s，d)較高的落子動(dòng)作.式中∑bC(s，b)表示根節(jié)點(diǎn)的訪問次數(shù);C(s，d)表示當(dāng)前葉子節(jié)點(diǎn)的訪問次數(shù);P(s，d)為深 度神經(jīng)網(wǎng)絡(luò)fθ(s)的策略輸出對應(yīng)動(dòng)作d 的概率值.

圖1 蒙特卡洛樹搜索流程示例Fig.1 Example of the monte carlo search tree process

3.1.2 展開與評估階段

根節(jié)點(diǎn)s0經(jīng)過選擇一系列的落子動(dòng)作d 到達(dá)葉子節(jié)點(diǎn)st，然后對葉子節(jié)點(diǎn) st進(jìn)行展開與評估.由深度神經(jīng)網(wǎng)絡(luò)fθ(st)輸出當(dāng)前葉子節(jié)點(diǎn)st對應(yīng)的策略輸出pt和估值輸出vt，其中pt向量是當(dāng)前葉子節(jié)點(diǎn)st每個(gè)合法落子動(dòng)作d 的走子概率，存儲(chǔ)在st的所有邊中.然后將st的邊r(st，d)中的訪問次數(shù)、累計(jì)行動(dòng)價(jià)值、平均行動(dòng)價(jià)值以及先驗(yàn)概率值初始化，即:C(st，d)=0，E(st，d)=0，Q(st，d)=0，P(st，d)=pt.

3.1.3 回傳階段

深度神經(jīng)網(wǎng)絡(luò)fθ(st)對當(dāng)前葉子節(jié)點(diǎn)st的估值輸出vt在其展開與評估階段完成后可以獲取到.在從根節(jié)點(diǎn)s0經(jīng)過一系列落子動(dòng)作到達(dá)葉子節(jié)點(diǎn)st的路徑中，每次走子之后，存儲(chǔ)在節(jié)點(diǎn)與節(jié)點(diǎn)之間邊的信息在路徑中進(jìn)行反向更新.訪問次數(shù) C(st，dt)、累計(jì)行動(dòng)價(jià)值 E(st，dt)、平均行動(dòng)價(jià)值Q(st，dt)的具更新方式如式(3)、式(4)、式(5)所示:

由圖1 中回傳階段可見，在該示例中 Q 的值更新為0.027 回傳給根節(jié)點(diǎn).

3.1.4 執(zhí)行階段

本文設(shè)置在五子棋對局中每步走子進(jìn)行300 次蒙特卡洛樹搜索.在多次搜索后，整個(gè)過程中產(chǎn)生的所有數(shù)據(jù)信息會(huì)存儲(chǔ)在樹中邊r(st，d)中，落子概率分布π(d|s0)可以根據(jù)這些數(shù)據(jù)信息得到.這個(gè)落子概率分布與根節(jié)點(diǎn)s0的訪問次數(shù)C(s0，d)的關(guān)系如下所示:

在本算法中，用來控制蒙特卡洛樹搜索的探索水平由τ來控制，初始值設(shè)置為1.這個(gè)參數(shù)在自我對弈階段早期鼓勵(lì)探索的進(jìn)行，隨著游戲的進(jìn)行，τ 的值逐漸降至零，此時(shí)會(huì)產(chǎn)生根據(jù)蒙特卡洛樹搜索評估在五子棋對局選擇最佳移動(dòng)的策略.在落子動(dòng)作執(zhí)行完畢后，下一輪蒙特卡洛樹搜索將以擴(kuò)展節(jié)點(diǎn)作為新的根節(jié)點(diǎn)重復(fù)上述階段.

3.2 深度神經(jīng)網(wǎng)絡(luò)

3.2.1 深度神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)

在本算法中只含有一個(gè)深度神經(jīng)網(wǎng)絡(luò)fθ，這個(gè)網(wǎng)絡(luò)結(jié)合了策略網(wǎng)絡(luò)和估值網(wǎng)絡(luò)，其結(jié)構(gòu)是由卷積神經(jīng)網(wǎng)絡(luò)組成的深度殘差網(wǎng)絡(luò).隨著網(wǎng)絡(luò)深度的增加，使用一般卷積神經(jīng)網(wǎng)絡(luò)往往會(huì)出現(xiàn)梯度彌散或者梯度爆炸以至于無法收斂以及網(wǎng)絡(luò)退化誤差增大的問題［12，13］.本算法使用的深度殘差網(wǎng)絡(luò)含有32個(gè)卷積層，每個(gè)殘差塊跨越兩個(gè)卷積層，整個(gè)網(wǎng)絡(luò)包含輸入層、卷積層、15 個(gè)殘差塊、全連接層與輸出層，其網(wǎng)絡(luò)模型的整體結(jié)構(gòu)如圖2 所示.

圖2 深度殘差網(wǎng)絡(luò)模型圖Fig.2 Deep residual network model

在深度殘差網(wǎng)絡(luò)的輸入層，輸入包含了五子棋對局中當(dāng)前行棋方的信息以及黑棋和白棋最近五步行棋狀態(tài)，數(shù)據(jù)類型為7×7×11 的0/1 矩陣.可以把0/1 矩陣直接輸入到深度殘差網(wǎng)絡(luò)中，無需進(jìn)行歸一化操作.

其中卷積層和殘差塊對數(shù)據(jù)的處理主要分為以下五個(gè)階段:

第一階段:棋盤數(shù)據(jù)進(jìn)入卷積層1，這里的卷積運(yùn)算使用32 個(gè)大小為5×5，步長為1 的卷積核，用來提取較大范圍的五子棋盤特征.為了防止邊緣數(shù)據(jù)的丟失，棋盤數(shù)據(jù)在卷積層1 首先進(jìn)行邊緣為2 的零擴(kuò)展處理，得到大小為11×11×11的訓(xùn)練數(shù)據(jù).在之后的每個(gè)卷積層后面需要?dú)w一化處理數(shù)據(jù)，再使用Relu 激活函數(shù).

第二階段:此階段由5 個(gè)殘差塊組成，數(shù)據(jù)在殘差塊1 ～5 中的每個(gè)卷積層都需進(jìn)行邊長為1 的零擴(kuò)展，將數(shù)據(jù)填充至9×9×11 大小.這階段的卷積運(yùn)算使用64 個(gè)大小3×3，步長為1 的卷積核.

第三階段:此階段由5 個(gè)殘差塊組成，數(shù)據(jù)在殘差塊6 ～10 中每個(gè)卷積層進(jìn)行邊長為1 的零擴(kuò)展，將數(shù)據(jù)填充至9×9×11 大小.這一階段的卷積運(yùn)算使用128 個(gè)大小3×3，步長為1 的卷積核.

第四階段:此階段由5 個(gè)殘差塊組成，棋盤數(shù)據(jù)在殘差塊11 ～15 中的每個(gè)卷積層都需進(jìn)行邊長為1 的零擴(kuò)展，將數(shù)據(jù)填充至9×9×11 大小.在這一階段的卷積運(yùn)算使用256 個(gè)大小3×3，步長為1 的卷積核.

第五階段:歸一化處理深度殘差網(wǎng)絡(luò)的殘差區(qū)域結(jié)束后輸出的數(shù)據(jù)，然后再接入卷積層2.在卷積層2 的卷積運(yùn)算使用1 個(gè)大小為1×1，步長為1 的卷積核，對輸出數(shù)據(jù)進(jìn)行降維，降維后為7×7×1 大小的數(shù)據(jù)矩陣.

在深度殘差網(wǎng)絡(luò)的全連接與輸出部分，輸出端分為策略端與估值端，使用非線性函數(shù)softmax 的全連接層在策略端直接輸出棋盤上每個(gè)位置落子概率，對應(yīng)大小為7×7 五子棋盤上的49 個(gè)落子點(diǎn).使用雙曲正切函數(shù)tanh 的全連接層在估值端，輸出-1 到1 之間的實(shí)數(shù)，對應(yīng)五子棋當(dāng)前對局盤面獲勝的概率.

3.2.2 深度神經(jīng)網(wǎng)絡(luò)的訓(xùn)練流程

深度神經(jīng)網(wǎng)絡(luò)fθ將當(dāng)前五子棋游戲棋盤數(shù)據(jù)以及歷史棋盤數(shù)據(jù)作為輸入，并將棋盤狀態(tài)轉(zhuǎn)換為矩陣輸入，如圖3 所示.如果當(dāng)前是黑方行棋，則當(dāng)前有黑棋的點(diǎn)取值1，有白棋或者沒有棋子的位置取值為0;反之，如果當(dāng)前是白方行棋，則當(dāng)前有白棋的點(diǎn)取值1，有黑棋或者沒有棋子的位置取值0.然后輸出動(dòng)作概率分布p 和對應(yīng)的估值v.p 表示五子棋盤上每個(gè)位置的落子概率，v 對應(yīng)當(dāng)前游戲狀態(tài)的獲勝概率.

蒙特卡洛樹搜索可以被視作是一個(gè)策略提升算子.對于每個(gè)狀態(tài)s，原本的深度神經(jīng)網(wǎng)絡(luò)fθ本身輸出了一個(gè)動(dòng)作概率分布p，然后蒙特卡洛樹搜索基于該網(wǎng)絡(luò)，再輸出一個(gè)概率分布π.由蒙特卡洛樹搜索定義可知新的概率分布π 較p 會(huì)選擇更強(qiáng)的動(dòng)作.同時(shí)，然后蒙特卡洛樹搜索也可以被視作是一個(gè)估值提升算子.在一次模擬棋局結(jié)束時(shí)，蒙特卡洛樹搜索會(huì)輸出一個(gè)輸贏結(jié)果Z，以最小化fθ輸出的價(jià)值v 與Z 的誤差來更新深度神經(jīng)網(wǎng)絡(luò).在本算法中自我對弈與深度神經(jīng)網(wǎng)絡(luò)的訓(xùn)練流程如圖4、圖5 所示.

圖3 棋盤數(shù)據(jù)處理Fig.3 Checkerboard data processing

其中自我對弈訓(xùn)練的流程如圖4 所示:程序自我博弈，從第一步到第 T 步標(biāo)記狀態(tài)為 s1，s2，…，sT.在第 t 步 st，使用最新的神經(jīng)網(wǎng)絡(luò)fθ執(zhí)行一次蒙特卡洛樹搜索γθ(如圖1 執(zhí)行階段所示).每個(gè)走子選擇的依據(jù)是通過蒙特卡洛樹搜索得出的概率πt.在最終的位置第T 步sT根據(jù)游戲規(guī)則計(jì)算對局的最終勝者Z.

圖4 自我對弈流程Fig.4 Process of self-play

本算法中深度神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程如圖5 所示:當(dāng)前五子棋對局的棋盤狀態(tài)為st，將其輸入fθ，通過32 個(gè)卷積層，fθ會(huì)輸出在五子棋盤上每一走子的概率分布的向量pt以及一個(gè)估值標(biāo)量vt表示當(dāng)前玩家在位置st上的獲勝概率.深度神經(jīng)網(wǎng)絡(luò)的參數(shù)θ 將自動(dòng)更新，以最大化策略向量pt和搜索概率πt的相似性，以及最小化預(yù)測獲勝概率vt與實(shí)際贏家Z的誤差.下一次自對弈迭代中將使用新參數(shù)θ.

其中損失函數(shù)loss 由兩部分組成，第一部分為深度神經(jīng)網(wǎng)絡(luò)fθ的估值輸出vt與蒙特卡洛樹搜索所得的勝負(fù)結(jié)果Z的均方和誤差，第二部分為fθ的策略輸出pt和蒙特卡羅樹搜索的策略πt的交叉信息熵誤差.為了進(jìn)一步優(yōu)化深度神經(jīng)網(wǎng)絡(luò)fθ的權(quán)值，需要在深度神經(jīng)網(wǎng)絡(luò)的每步輸出并行反向傳播.其中參數(shù)θ 通過損失函數(shù)loss 的梯度下降來調(diào)整.損失函數(shù)loss 的具體公式如式(7)、式(8)所示，其中c 是控制L2 權(quán)重正則化水平的參數(shù)(防止過擬合):

圖5 深度神經(jīng)網(wǎng)絡(luò)訓(xùn)練流程Fig.5 Deep neural network training process

4 算法實(shí)現(xiàn)過程

4.1 運(yùn)行環(huán)境

本實(shí)驗(yàn)在運(yùn)行內(nèi)存為16.0GB，配置為NVIDIA GeForce GTX 1060，Intel(R)Core(TM)i5-8300H CPU @2.3GHz 的臺式設(shè)備上實(shí)現(xiàn).代碼通過 TensorFlow 實(shí)現(xiàn)，共包含12 個(gè) py文件.

4.2 算法實(shí)現(xiàn)

4.2.1 設(shè)置游戲規(guī)則進(jìn)行自我對弈

本文將游戲規(guī)則設(shè)置為在大小為15×15 的標(biāo)準(zhǔn)五子棋棋盤上進(jìn)行五子棋對局，每次落子進(jìn)行300 次蒙特卡洛樹搜索.在實(shí)驗(yàn)中設(shè)置best_player 和current_player 兩個(gè)智能體，其中best_player 通過自我對弈生成記憶，并且使用當(dāng)前最佳的深度神經(jīng)網(wǎng)絡(luò)模型.current_player 可以在best_player 生成的記憶上重新訓(xùn)練它的深度神經(jīng)網(wǎng)絡(luò)，然后再與best_player對局.如果current_player 獲勝，best_player 內(nèi)部的深度神經(jīng)網(wǎng)絡(luò)將與current_player 內(nèi)部的深度神經(jīng)網(wǎng)絡(luò)進(jìn)行轉(zhuǎn)換，然后進(jìn)行下一次迭代.

在實(shí)驗(yàn)的第一階段，通過蒙特卡洛樹搜索進(jìn)行自我對弈收集第一批棋盤數(shù)據(jù)，每次迭代使用蒙特卡洛樹搜索進(jìn)行200 局五子棋對局.此時(shí)由于沒有深度神經(jīng)網(wǎng)絡(luò)的指導(dǎo)，對局中落子策略為均等概率的隨機(jī)投子.因此，第一批通過自我對弈收集到的棋盤數(shù)據(jù)棋力水平是比較差的.

4.2.2 訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)生成模型

使用第一階段自我對弈收集到的棋盤數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)訓(xùn)練神經(jīng)網(wǎng)絡(luò).將棋盤狀態(tài)轉(zhuǎn)換為矩陣輸入，如果當(dāng)前是黑方行棋，則當(dāng)前有黑棋的點(diǎn)取值1，有白棋或者沒有棋子的位置取值為0;反之，如果當(dāng)前是白方行棋，則當(dāng)前有白棋的點(diǎn)取值1，有黑棋或者沒有棋子的位置取值0，如圖3 所示.

best_player 通過使用訓(xùn)練好的深度神經(jīng)網(wǎng)絡(luò)模型進(jìn)行自我對弈，在對弈結(jié)束后使用收集到的棋盤數(shù)據(jù)更新深度神經(jīng)網(wǎng)絡(luò)參數(shù)θ.在多次迭代中，參數(shù)θ 通過不斷最大化策略向量pt和搜索概率πt的相似性以及最小化估值vt與實(shí)際贏家Z的誤差不斷更新，使得深度神經(jīng)網(wǎng)絡(luò)輸出的落子概率pt和評估值vt能夠越來越接近能夠把五子棋局贏下的落子方式.經(jīng)過兩天的訓(xùn)練，可以得到損失與當(dāng)前迭代次數(shù)的關(guān)系圖，如圖6 所示.其中策略損失表示pt與πt的交叉熵，價(jià)值損失表示vt與Z 之間的均方誤差，平均損失則為兩者的平均值.

4.2.3 評估深度神經(jīng)網(wǎng)絡(luò)模型

實(shí)驗(yàn)中使用比賽的形式對當(dāng)前神經(jīng)網(wǎng)絡(luò)模型進(jìn)行評估.current_player 與執(zhí)行當(dāng)前最佳的神經(jīng)網(wǎng)絡(luò)模型的best_player在每次迭代后進(jìn)行對弈，設(shè)置對弈局?jǐn)?shù)為20 局，獲勝一局得一分，然后統(tǒng)計(jì)兩者獲得總積分.如果current_player 積分較高，best_player 內(nèi)部的深度神經(jīng)網(wǎng)絡(luò)將被轉(zhuǎn)換為current_player 內(nèi)部的深度神經(jīng)網(wǎng)絡(luò)，然后進(jìn)行下一次迭代.實(shí)驗(yàn)中前三次迭代后的評估結(jié)果如表1 所示.

圖6 損失與迭代次數(shù)的關(guān)系圖Fig.6 Graph of loss and number of iterations

表1 評估深度神經(jīng)網(wǎng)絡(luò)模型Table 1 Evaluate the deep neural network model

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

經(jīng)過兩天的訓(xùn)練，深度神經(jīng)網(wǎng)絡(luò)在預(yù)測五子棋游戲狀態(tài)的值以及可能的下一步移動(dòng)中逐漸變的更好.從深度神經(jīng)網(wǎng)絡(luò)的第一次迭代到第28 次，隨著深度神經(jīng)網(wǎng)絡(luò)參數(shù)θ 的更新，共生成了28 個(gè)深度神經(jīng)網(wǎng)絡(luò)模型.為了說明本算法在五子棋領(lǐng)域如何變得越來越強(qiáng)大，在28 個(gè)深度神經(jīng)網(wǎng)絡(luò)模型中，從初始深度神經(jīng)網(wǎng)絡(luò)模型1 開始，每隔兩個(gè)挑選一個(gè)組成比賽，一直到模型28，共挑選10 個(gè)，每組比賽兩次，玩家1 和玩家2 隨機(jī)優(yōu)先落子，計(jì)算最后得分(score)，結(jié)果如表2 所示.

表2 比賽積分表Table 2 Game score

從表2 中可以看出，隨著訓(xùn)練時(shí)間的增長，在挑選出的10 個(gè)深度神經(jīng)網(wǎng)絡(luò)模型中，模型28 在五子棋游戲中的表現(xiàn)要明顯優(yōu)于最初的深度神經(jīng)網(wǎng)絡(luò)模型，在五子棋對局中獲得了大部分的勝利.這個(gè)學(xué)習(xí)過程并沒有達(dá)到極限，本算法在五子棋游戲中的表現(xiàn)將會(huì)隨著訓(xùn)練時(shí)間的進(jìn)一步增長變得越來越強(qiáng)，學(xué)習(xí)越來越復(fù)雜的落子策略.

以往的智能五子棋算法主要通過極大極小值搜索算法和Alpha-Beta 剪枝算法進(jìn)行實(shí)現(xiàn)，可以擊敗大多數(shù)的業(yè)余選手.將實(shí)驗(yàn)過程中得到的28 個(gè)深度神經(jīng)網(wǎng)絡(luò)模型與基于極大極小值算法的智能五子棋算法以及基于Alpha-Beta 剪枝算法的智能五子棋算法通過五子棋對局的方式進(jìn)行比較，設(shè)置對局?jǐn)?shù)為20，觀察對局結(jié)果，記錄深度神經(jīng)網(wǎng)絡(luò)模型獲勝局?jǐn)?shù)，如表3 所示，可以看出從模型16 開始，深度神經(jīng)網(wǎng)絡(luò)模型在與兩種智能五子棋算法的20 個(gè)對局中已經(jīng)能夠取得較大優(yōu)勢，模型25 與28 則以明顯優(yōu)勢贏得了大部分的對局.

表3 三種算法對比Table 3 Three algorithms are compared

在正規(guī)的五子棋比賽中，一般將規(guī)則制定為五局三勝制，即在五局比賽中，首先贏得三局的一方取得勝利.以此制度對三種算法進(jìn)行二次比較，其結(jié)果如表4 所示，可以看出在五局三勝的比賽制度下，深度神經(jīng)網(wǎng)絡(luò)模型取得了更好的成績，從模型13 到28，均獲得了比賽的勝利.

表4 五局三勝制比賽結(jié)果Table 4 Result of the best-of-five game

本實(shí)驗(yàn)使用埃洛等級分(Elo)對基于蒙特卡洛樹搜索與深度神經(jīng)網(wǎng)絡(luò)的智能五子棋算法的五子棋水平進(jìn)行評分.其訓(xùn)練時(shí)間與Elo 等級分的變化趨勢如圖7 所示.僅僅經(jīng)過40小時(shí)的訓(xùn)練，本算法的五子棋等級分已經(jīng)達(dá)到了4000 分左右，遠(yuǎn)遠(yuǎn)高于普通人類水平.

6 總 結(jié)

本文基于蒙特卡洛樹搜索與深度神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)并實(shí)現(xiàn)了一種自學(xué)習(xí)的智能五子棋算法.通過蒙特卡洛樹搜索進(jìn)行自我對弈，在沒有人類五子棋游戲經(jīng)驗(yàn)的前提下，從零開始，蒙特卡洛樹搜索使用深度神經(jīng)網(wǎng)絡(luò)評估落子位置和選擇移動(dòng)，提高樹搜索的強(qiáng)度，使落子質(zhì)量更高，自對弈迭代更強(qiáng).將訓(xùn)練過程中得到的模型組成比賽，可以看到隨著訓(xùn)練時(shí)間的增長，模型效果越來越好.經(jīng)過兩天的訓(xùn)練，本算法的埃洛等級分已經(jīng)達(dá)到4000 分，遠(yuǎn)遠(yuǎn)高于了普通人類水平.在以后的研究中，這種干凈、穩(wěn)定的學(xué)習(xí)算法可以應(yīng)用到更多離散型的游戲當(dāng)中.并且隨著人工智能領(lǐng)域的飛速發(fā)展，越來越多的人工智能達(dá)到甚至遠(yuǎn)遠(yuǎn)超過人類水平，相信以后會(huì)有更強(qiáng)大智能的算法出現(xiàn)并應(yīng)用到人類的生活中.

圖7 Elo 等級分與訓(xùn)練時(shí)間關(guān)系圖Fig.7 Diagram of the relationship between Elo rating system and training time