基于蘇拉卡爾塔棋的差分學(xué)習(xí)算法研究

李森潭 劉超富 李宇軒 張楚儀 李若溪

摘 要：文章結(jié)合深度神經(jīng)網(wǎng)絡(luò)與差分學(xué)習(xí)，在蘇拉卡爾塔棋博弈中引入人工神經(jīng)元為棋子的移動(dòng)估值，并結(jié)合差分學(xué)習(xí)得到最有價(jià)值的棋子移動(dòng)。神經(jīng)網(wǎng)絡(luò)的輸入為棋局，輸出為棋子的價(jià)值估計(jì)，之后用它們來指導(dǎo)即時(shí)差分學(xué)習(xí)（TD）。每出現(xiàn)一個(gè)局面，使用??貪婪法來選擇新的動(dòng)作和更新價(jià)值函數(shù)，從而使博弈效果越來越好。

關(guān)鍵詞：神經(jīng)網(wǎng)絡(luò);差分學(xué)習(xí);損失函數(shù)

0 引言

棋類博弈游戲具有智能性，所以在人工智能界很早就被重視，被稱為人工智能的“果蠅”。從戰(zhàn)勝世界棋王卡斯帕羅夫的國(guó)際象棋深藍(lán)到戰(zhàn)勝李世石的圍棋博弈程序 AlphaGo，計(jì)算機(jī)博弈再次引起業(yè)內(nèi)的廣泛關(guān)注。截至目前，國(guó)內(nèi)已經(jīng)順利舉辦了十四屆全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽，蘇拉卡爾塔棋是其中的一項(xiàng)比賽項(xiàng)目。

近年來，許多學(xué)者引入機(jī)器學(xué)習(xí)和強(qiáng)化學(xué)習(xí)對(duì)計(jì)算機(jī)博弈進(jìn)行優(yōu)化。主要搜索方法包括：差分學(xué)習(xí)、阿爾法貝塔剪枝和蒙特卡洛樹等，都在一些棋類中有其成功的應(yīng)用。

本文介紹了機(jī)器學(xué)習(xí)，強(qiáng)化學(xué)習(xí)與蘇拉卡爾塔棋機(jī)器博弈的階段性成果，該方法主要是結(jié)合深度神經(jīng)網(wǎng)絡(luò)與差分學(xué)習(xí)，在蘇拉卡爾塔棋博弈中引入人工神經(jīng)元為棋子的移動(dòng)估值，并通過差分學(xué)習(xí)修改網(wǎng)絡(luò)參數(shù)，從而得到最有價(jià)值的棋子移動(dòng)。神經(jīng)網(wǎng)絡(luò)的輸入為棋局，輸出為棋子的價(jià)值估計(jì)，之后用它們來指導(dǎo)即時(shí)差分學(xué)習(xí)（TD）。每出現(xiàn)一個(gè)局面，使用??貪婪法來選擇新的動(dòng)作和更新價(jià)值函數(shù)，從而使博弈效果越來越好[1]。

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

蘇拉卡爾塔棋是一種雙人游戲[2]，源自印尼爪哇島的蘇拉卡爾塔（Surakarta）。橫豎各6條邊構(gòu)成正方形棋盤，36個(gè)交叉點(diǎn)為棋位，各邊由8段圓弧連接，通常用2種不同顏色表示。游戲在開始時(shí)，每一方有12個(gè)棋子各排成2行。棋盤如圖1所示。

規(guī)則如下：

（1）參與者擲硬幣決定誰先開始。一次只能移動(dòng)一個(gè)棋子。兩個(gè)棋手輪流下棋。

（2）如果移動(dòng)方向沒有棋子，任何棋子都可以在8個(gè)方向（上、下、左、右、左上、左下、右上、右下）移動(dòng)1個(gè)格。

（3）如果你想吃掉對(duì)方的棋子，必須水平和垂直地走，并且至少穿過一條與路徑相切的弧線，移動(dòng)的路徑不能被自己的棋子阻塞。

（4）黑子可以吃掉紅子，紅色也可以吃掉同一路徑相反方向的黑子。

（5）當(dāng)一個(gè)界面上的一方所有棋子都被吃掉時(shí)，游戲結(jié)束，有剩余棋子方獲勝。

（6）計(jì)算機(jī)博弈一般說來，如果每局持續(xù)時(shí)間超過30分鐘，雙方都會(huì)停止，以剩余更多的棋子方贏得比賽。

2 蘇拉卡爾塔棋棋盤分析和程序?qū)崿F(xiàn)

2.1? 棋盤和棋子分析及表示

（1）棋盤每個(gè)點(diǎn)以坐標(biāo)的形式表示，左上角的點(diǎn)為坐標(biāo)原點(diǎn)，1號(hào)紅棋子坐標(biāo)為（0，0），2號(hào)紅棋子坐標(biāo)為（0，1）， 7號(hào)紅棋子坐標(biāo)為（1，0），如圖2所示。

（2）棋子雙方分別為紅和藍(lán)色區(qū)分，每一個(gè)棋子又有各自的編號(hào)。

（3）下棋信息記錄。對(duì)于行棋路徑信息，采用字典對(duì)表示，字典對(duì)的第一個(gè)元素記錄起始點(diǎn)，第二個(gè)元素記錄目標(biāo)點(diǎn)，其數(shù)據(jù)結(jié)構(gòu)必須滿足。

（4）判斷是否對(duì)局結(jié)束。在紅黑雙方每走一步后，程序通過對(duì)棋盤上雙方各自的棋子數(shù)量進(jìn)行統(tǒng)計(jì)，從而判斷出勝負(fù);若雙方在行棋時(shí)耗時(shí)過長(zhǎng)，則直接判負(fù)。

2.2? 程序?qū)崿F(xiàn)

棋類的博弈程序必須要有優(yōu)良的人機(jī)交互體驗(yàn)、良好的界面、快速的棋局計(jì)算時(shí)間、可供用戶自由選擇玩家對(duì)弈或人機(jī)對(duì)弈，并能自動(dòng)判斷成績(jī)和記錄分?jǐn)?shù)[3-4]。對(duì)應(yīng)功能需求劃為圖3中的幾個(gè)模塊，程序中重要的人機(jī)交互界面劃分，如圖3—4所示。

3基于搜索樹的深度神經(jīng)網(wǎng)絡(luò)與差分學(xué)習(xí)相結(jié)合的方法

3.1? 基于蘇拉卡爾塔棋的深度神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)特征

機(jī)器學(xué)習(xí)方法與傳統(tǒng)方法不同，它只需要將棋盤和歷史數(shù)據(jù)輸入到神經(jīng)網(wǎng)絡(luò)中，并不用特別特征設(shè)計(jì)及人工調(diào)參[5]。輸入網(wǎng)絡(luò)中的特征，如表1所示。

此外，與五子棋不同，蘇拉卡爾塔棋是移動(dòng)型棋子，即每步把棋子從某個(gè)位置移到另一個(gè)位置，我們使用一個(gè)平面來表示移動(dòng)棋子的位置，再使用另外一個(gè)平面來表示棋子移到的位置。然后，使用一個(gè)平面進(jìn)行表示當(dāng)前是否為先手方，如果是先手放，則該平面全部置為1，否則全置為0。筆者使用的深度神經(jīng)網(wǎng)絡(luò)為6層的卷積殘差網(wǎng)絡(luò)，分為策略網(wǎng)絡(luò)（見表2）和價(jià)值網(wǎng)絡(luò)（見表3）兩個(gè)部分。其中，以策略網(wǎng)絡(luò)作為36×36的輸出，表示所有允許的移動(dòng)。神經(jīng)網(wǎng)絡(luò)中的激活函數(shù)除已說明外，其余皆為relu函數(shù)。

3.2 差分學(xué)習(xí)

時(shí)序差分法（TD）學(xué)習(xí)是最重要的增強(qiáng)學(xué)習(xí)方法，其重要目標(biāo)是：當(dāng)不受人工干預(yù)時(shí)，進(jìn)行自學(xué)習(xí)訓(xùn)練，從而來進(jìn)行更新估值函數(shù)的權(quán)值向量[6]。在計(jì)算機(jī)博弈的背景下，TD學(xué)習(xí)可總結(jié)為修正權(quán)值向量以對(duì)估值函數(shù)進(jìn)行擬合的過程。TD利用回報(bào)值進(jìn)行學(xué)習(xí)，相比于一般的監(jiān)督學(xué)習(xí)，TD用差分序列來實(shí)現(xiàn)對(duì)權(quán)值向量的訓(xùn)練，其關(guān)鍵也在于誤差可以用一系列預(yù)測(cè)值之和來表示。TD同時(shí)與深度神經(jīng)網(wǎng)絡(luò)相結(jié)合，能夠更好地調(diào)整神經(jīng)網(wǎng)絡(luò)的參數(shù)。此次博弈程序思路基于同策略時(shí)間差分sarsa模型展開。

SARSA算法給定強(qiáng)化學(xué)習(xí)的7個(gè)要素：狀態(tài)集S，動(dòng)作集A，即時(shí)獎(jiǎng)勵(lì)R，衰減因子γ，探索率?，求解最優(yōu)的動(dòng)作價(jià)值函數(shù)q?和最優(yōu)策略π?，不需要環(huán)境的狀態(tài)轉(zhuǎn)化模型。對(duì)于它的控制問題求解，即通過價(jià)值函數(shù)的更新，來更新當(dāng)前的策略，再通過新的策略，來產(chǎn)生新的狀態(tài)和即時(shí)獎(jiǎng)勵(lì)，進(jìn)而更新價(jià)值函數(shù)。一直進(jìn)行下去，直到價(jià)值函數(shù)和策略都收斂[7-8]。

使用??貪婪法來更新價(jià)值函數(shù)和選擇新的動(dòng)作，即開始時(shí)設(shè)定一個(gè)較小的?值，以1??的概率貪婪地選擇目前認(rèn)為是最大行為價(jià)值的行為，而以?的概率隨機(jī)地從所有m個(gè)可選行為中選擇行為。用公式可以表示為：

在進(jìn)行迭代時(shí)，先用??貪婪法從當(dāng)前狀態(tài)S中選擇一個(gè)可行動(dòng)作A，隨后轉(zhuǎn)入到一個(gè)新的狀態(tài)S'，此時(shí)給出一個(gè)即時(shí)獎(jiǎng)勵(lì)R，在下一個(gè)狀態(tài)S'中再基于??貪婪法從狀態(tài)S''中得到一個(gè)動(dòng)作A'用來更新的價(jià)值函數(shù)，價(jià)值函數(shù)的更新公式是：

其中，γ是衰減因子，α是迭代步長(zhǎng)，收獲Gt的表達(dá)式是R+γQ（S'，A'）。

當(dāng)隨機(jī)初始化神經(jīng)網(wǎng)絡(luò)之后，對(duì)于每一個(gè)棋局狀態(tài)，可以得到選擇的行動(dòng)的價(jià)值估計(jì)，同時(shí)根據(jù)動(dòng)作A'之后的局面S'，得到v'=fθ（s'）。隨后，能夠使用反向傳播算法對(duì)我們所構(gòu)建的神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練。圖5—6為同策略差分學(xué)習(xí)模型。神經(jīng)網(wǎng)絡(luò)中以交叉熵和平方差兩部分來組成損失函數(shù)，即對(duì)于棋局中的某一個(gè)狀態(tài)：

x公式中以來作為使L2正則化的參數(shù)。

遵循某一策略時(shí)，在S，選擇一個(gè)行為A，與環(huán)境交互，得到獎(jiǎng)勵(lì)R，進(jìn)入S'，再次遵循當(dāng)前策略，產(chǎn)生一個(gè)行為A'，利用Q（S'，A'）更新Q（S，A）。

Every time-step：

Policy evaluation Sarsa，Q∣qm

Policy improvement ? -greedy policy improvement

下面是SARSA算法應(yīng)用于蘇拉卡爾塔棋的流程：? ?（1）算法輸入。迭代輪數(shù)T，狀態(tài)集S，動(dòng)作集A，步長(zhǎng)α，衰減因子γ，探索率?。（2）輸出。所有的狀態(tài)和動(dòng)作對(duì)應(yīng)的價(jià)值Q。①隨機(jī)初始化所有的狀態(tài)和動(dòng)作對(duì)應(yīng)的價(jià)值Q。對(duì)于終止?fàn)顟B(tài)其Q值初始化為0。②for i from 1 to T，進(jìn)行迭代。

（a）初始化S為當(dāng)前狀態(tài)序列的第一個(gè)狀態(tài)。設(shè)置A為??貪婪法在當(dāng)前狀態(tài)S選擇的動(dòng)作。

（b）在狀態(tài)S執(zhí)行當(dāng)前動(dòng)作A，得到新狀態(tài)S'和獎(jiǎng)勵(lì)R。

（c）用??貪婪法在狀態(tài)S'選擇新的動(dòng)作A'。

（d）更新價(jià)值函數(shù)Q（S，A）：

Q（S，A）=Q（S，A）+α（R+γQ（S'，A'）?Q（S，A））

（e）S=S'，A=A'。

（f）如果S'是終止?fàn)顟B(tài)，當(dāng)前輪迭代完畢，否則轉(zhuǎn)到步驟（b）。

對(duì)于步長(zhǎng)α，將隨著迭代的進(jìn)行逐漸變小，這樣才能保證動(dòng)作價(jià)值函數(shù)Q可以收斂。

同策略時(shí)間差分sarsa模型算法為：

Initialize Q（s，a），s∣S，a∣A（s），arbitrarily，and Q（ terminal-state，

Repeat （for each episode）：

Initialize S

Choose A from S using policy derived from Q（e.g.，ε -greedy）

Repeat （for each step of episode）：

Take action A，observe R，S'

Choose A' from S' using policy derived from Q （e.g.，ε -greedy）

until S is terminal

4 實(shí)驗(yàn)結(jié)果

對(duì)實(shí)際訓(xùn)練效果進(jìn)行檢驗(yàn)，對(duì)深度神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練和評(píng)估時(shí)，將訓(xùn)練時(shí)的溫度控制常量τ=1，在評(píng)估性能時(shí)τ= 0.1。對(duì)于網(wǎng)絡(luò)的訓(xùn)練，筆者進(jìn)行了3 000次的模擬。在評(píng)估性能時(shí)，筆者用訓(xùn)練500局的神經(jīng)網(wǎng)絡(luò)與訓(xùn)練更多次數(shù)的神經(jīng)網(wǎng)絡(luò)進(jìn)行了100局對(duì)戰(zhàn)，雙方各模擬了30 s。實(shí)驗(yàn)結(jié)果，如表4所示。值得注意的是，對(duì)于性能的評(píng)估，應(yīng)適當(dāng)?shù)卦黾幽M的次數(shù)，從而獲得更優(yōu)異的性能表現(xiàn)。

由此可見，當(dāng)增加訓(xùn)練局?jǐn)?shù)時(shí)，深度神經(jīng)網(wǎng)絡(luò)的博弈水平不斷地提高，所以，使用基于TD的深度神經(jīng)網(wǎng)絡(luò)博弈對(duì)于提高蘇拉卡爾塔程序的博弈水平是可行的。

5 結(jié)語

本文是在蘇拉卡爾塔棋機(jī)器博弈中應(yīng)用結(jié)合深度神經(jīng)網(wǎng)絡(luò)與差分學(xué)習(xí)的方法。在程序自學(xué)習(xí)訓(xùn)練的過程中，其博弈水平不斷地提高。由此可見，如果進(jìn)行上百萬局的自博弈訓(xùn)練，其博弈水平將會(huì)到達(dá)一個(gè)很高的高度。在未來的研究實(shí)踐中，調(diào)整自學(xué)習(xí)策略、優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)、引入人類對(duì)戰(zhàn)數(shù)據(jù)等方面會(huì)是我們不斷探索的方向。

[參考文獻(xiàn)]

[1]桂義勇.一種國(guó)際跳棋的博弈系統(tǒng)研究[J].智能計(jì)算機(jī)與應(yīng)用，2020（4）：32-34，39.

[2]曾小寧.五子棋中的博弈問題[J].廣東第二師范學(xué)院學(xué)報(bào)，2003（2）：96-100.

[3]王坤峰，茍超，段艷杰，等.生成式對(duì)抗網(wǎng)絡(luò)的研究進(jìn)展與展望[J].自動(dòng)化學(xué)報(bào)，2017（3）：321-332.

[4]BERTALMIO M，VESE L，SAPIRO G，et al.Simultaneous structure and texture image inpainting[J].IEEE Transactions on Image Processing，2003（8）：882-889.

[5]COLOMABALLESTER，MARCELO BOL，VICENT C，et al.Filling-in by joint interpolation of vector fields and gray levels[J].IEEE Transactions on Image Processing，2001（8）：1200-1211.

[6]GROSSAUER H.A combined PDE and texture synthesis approach to inpainting[C].Berlin：European Conference on Computer Vision.Springer，2004.

[7]BARNES C，GOLDMAN D B，SHECHTMAN E，et al.The patchmatch randomized matching algorithm for image manipulation[J].Communications of the ACM，2011（11）：103-110.

[8]MIYATO T，KATAOKA T，KOYAMA M，et al.Spectral normalization for generative adversarial networks[J].ArXiv Preprint Arxiv，2018（2）：75-59.

（編輯 姚 鑫）