基于蘇拉卡爾塔棋的差分學習算法研究

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

摘 要：文章結合深度神經網絡與差分學習，在蘇拉卡爾塔棋博弈中引入人工神經元為棋子的移動估值，并結合差分學習得到最有價值的棋子移動。神經網絡的輸入為棋局，輸出為棋子的價值估計，之后用它們來指導即時差分學習（TD）。每出現一個局面，使用??貪婪法來選擇新的動作和更新價值函數，從而使博弈效果越來越好。

關鍵詞：神經網絡;差分學習;損失函數

0 引言

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

近年來，許多學者引入機器學習和強化學習對計算機博弈進行優化。主要搜索方法包括：差分學習、阿爾法貝塔剪枝和蒙特卡洛樹等，都在一些棋類中有其成功的應用。

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

1 ? 蘇拉卡爾塔棋簡介

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

規則如下：

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

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

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

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

（5）當一個界面上的一方所有棋子都被吃掉時，游戲結束，有剩余棋子方獲勝。

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

2 蘇拉卡爾塔棋棋盤分析和程序實現

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

（1）棋盤每個點以坐標的形式表示，左上角的點為坐標原點，1號紅棋子坐標為（0，0），2號紅棋子坐標為（0，1）， 7號紅棋子坐標為（1，0），如圖2所示。

（2）棋子雙方分別為紅和藍色區分，每一個棋子又有各自的編號。

（3）下棋信息記錄。對于行棋路徑信息，采用字典對表示，字典對的第一個元素記錄起始點，第二個元素記錄目標點，其數據結構必須滿足。

（4）判斷是否對局結束。在紅黑雙方每走一步后，程序通過對棋盤上雙方各自的棋子數量進行統計，從而判斷出勝負;若雙方在行棋時耗時過長，則直接判負。

2.2? 程序實現

棋類的博弈程序必須要有優良的人機交互體驗、良好的界面、快速的棋局計算時間、可供用戶自由選擇玩家對弈或人機對弈，并能自動判斷成績和記錄分數[3-4]。對應功能需求劃為圖3中的幾個模塊，程序中重要的人機交互界面劃分，如圖3—4所示。

3基于搜索樹的深度神經網絡與差分學習相結合的方法

3.1? 基于蘇拉卡爾塔棋的深度神經網絡的結構特征

機器學習方法與傳統方法不同，它只需要將棋盤和歷史數據輸入到神經網絡中，并不用特別特征設計及人工調參[5]。輸入網絡中的特征，如表1所示。

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

3.2 差分學習

時序差分法（TD）學習是最重要的增強學習方法，其重要目標是：當不受人工干預時，進行自學習訓練，從而來進行更新估值函數的權值向量[6]。在計算機博弈的背景下，TD學習可總結為修正權值向量以對估值函數進行擬合的過程。TD利用回報值進行學習，相比于一般的監督學習，TD用差分序列來實現對權值向量的訓練，其關鍵也在于誤差可以用一系列預測值之和來表示。TD同時與深度神經網絡相結合，能夠更好地調整神經網絡的參數。此次博弈程序思路基于同策略時間差分sarsa模型展開。

SARSA算法給定強化學習的7個要素：狀態集S，動作集A，即時獎勵R，衰減因子γ，探索率?，求解最優的動作價值函數q?和最優策略π?，不需要環境的狀態轉化模型。對于它的控制問題求解，即通過價值函數的更新，來更新當前的策略，再通過新的策略，來產生新的狀態和即時獎勵，進而更新價值函數。一直進行下去，直到價值函數和策略都收斂[7-8]。

使用??貪婪法來更新價值函數和選擇新的動作，即開始時設定一個較小的?值，以1??的概率貪婪地選擇目前認為是最大行為價值的行為，而以?的概率隨機地從所有m個可選行為中選擇行為。用公式可以表示為：

在進行迭代時，先用??貪婪法從當前狀態S中選擇一個可行動作A，隨后轉入到一個新的狀態S'，此時給出一個即時獎勵R，在下一個狀態S'中再基于??貪婪法從狀態S''中得到一個動作A'用來更新的價值函數，價值函數的更新公式是：

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

當隨機初始化神經網絡之后，對于每一個棋局狀態，可以得到選擇的行動的價值估計，同時根據動作A'之后的局面S'，得到v'=fθ（s'）。隨后，能夠使用反向傳播算法對我們所構建的神經網絡進行訓練。圖5—6為同策略差分學習模型。神經網絡中以交叉熵和平方差兩部分來組成損失函數，即對于棋局中的某一個狀態：

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

遵循某一策略時，在S，選擇一個行為A，與環境交互，得到獎勵R，進入S'，再次遵循當前策略，產生一個行為A'，利用Q（S'，A'）更新Q（S，A）。

Every time-step：

Policy evaluation Sarsa，Q∣qm

Policy improvement ? -greedy policy improvement

下面是SARSA算法應用于蘇拉卡爾塔棋的流程：? ?（1）算法輸入。迭代輪數T，狀態集S，動作集A，步長α，衰減因子γ，探索率?。（2）輸出。所有的狀態和動作對應的價值Q。①隨機初始化所有的狀態和動作對應的價值Q。對于終止狀態其Q值初始化為0。②for i from 1 to T，進行迭代。

（a）初始化S為當前狀態序列的第一個狀態。設置A為??貪婪法在當前狀態S選擇的動作。

（b）在狀態S執行當前動作A，得到新狀態S'和獎勵R。

（c）用??貪婪法在狀態S'選擇新的動作A'。

（d）更新價值函數Q（S，A）：

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

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

（f）如果S'是終止狀態，當前輪迭代完畢，否則轉到步驟（b）。

對于步長α，將隨著迭代的進行逐漸變小，這樣才能保證動作價值函數Q可以收斂。

同策略時間差分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 實驗結果

對實際訓練效果進行檢驗，對深度神經網絡進行訓練和評估時，將訓練時的溫度控制常量τ=1，在評估性能時τ= 0.1。對于網絡的訓練，筆者進行了3 000次的模擬。在評估性能時，筆者用訓練500局的神經網絡與訓練更多次數的神經網絡進行了100局對戰，雙方各模擬了30 s。實驗結果，如表4所示。值得注意的是，對于性能的評估，應適當地增加模擬的次數，從而獲得更優異的性能表現。

由此可見，當增加訓練局數時，深度神經網絡的博弈水平不斷地提高，所以，使用基于TD的深度神經網絡博弈對于提高蘇拉卡爾塔程序的博弈水平是可行的。

5 結語

本文是在蘇拉卡爾塔棋機器博弈中應用結合深度神經網絡與差分學習的方法。在程序自學習訓練的過程中，其博弈水平不斷地提高。由此可見，如果進行上百萬局的自博弈訓練，其博弈水平將會到達一個很高的高度。在未來的研究實踐中，調整自學習策略、優化網絡結構、引入人類對戰數據等方面會是我們不斷探索的方向。

[參考文獻]

[1]桂義勇.一種國際跳棋的博弈系統研究[J].智能計算機與應用，2020（4）：32-34，39.

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

[3]王坤峰，茍超，段艷杰，等.生成式對抗網絡的研究進展與展望[J].自動化學報，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.

（編輯 姚 鑫）