基于MCTS和卷積神經網絡的五子棋策略研究

歐俊臣，沙 玲，楊淞文

（上海工程技術大學 機械與汽車工程學院，上海 201620）

0 引言

隨著計算機的發展，基于“人工智能”而生的產物越來越多，在人機博弈領域內更是如此。無論是 IBM 設計的“Deep Blue”還是 Google開發的AlphaGo Zero，都代表了人工智能在人機博弈所能達到的最高水平。五子棋，又稱為五子連珠，英文名Gobang或者Gomoku，發源于古代中國，后流傳到日本，如今在世界范圍內廣受人們的喜愛。五子棋的規則很簡單，對局雙方分別持黑白棋子，持黑棋者為先手、白棋者為后手，雙方先后落子，誰先在橫、豎、斜任一方向形成五顆棋子相連，便取得比賽的勝利[1]。

五子棋中游戲中，由于棋盤點數有限，假設對局雙方棋力相當，當持黑棋者以某些定式開局，理想情況下雙方無限制地對局，勝利總是出現在執先手的一方，故在職業比賽中常常會有禁手規則，即禁止持黑棋者以一定定式開局[2]。本論文環境下不考慮禁手規則。

1 背景介紹

1.1 蒙特卡洛樹搜索（Monte-Carlo Tree Search，MCTS）

MCTS是一種通過在決策空間中獲取隨機樣本并根據結果構建搜索樹來在給定域中查找最優決策的方法。它已經對人工智能（AI）方法產生了深遠的影響，這些方法可以表示為連續決策樹，特別是游戲和規劃問題。在搜索空間狹小的情況下存在盲目搜索。盲目搜索的意思就是，以當前局勢為根節點，按照博弈樹展開的形式，直到遍歷完整個搜索空間。這樣的遍歷方式有兩種，如圖1所示，分別是深度優先搜索（Deepth-first search，DFS）和廣度優先搜索（Breadth-first search，BFS）[3-4]。

圖1 DFS和BFS搜索示意圖Fig.1 DFS and BFS search diagram

MCTS的主要概念是搜索，即沿著博弈樹向下的一組遍歷過程。單次遍歷的路徑會從根節點（當前博弈狀態）延伸到沒有完全展開的節點，未完全展開的節點表示其子節點至少有一個未訪問到。遇到未完全展開的節點時，它的一個未訪問子節點將會作為單次模擬的根節點，隨后模擬的結果將會反向傳播回當前樹的根節點并更新博弈樹的節點統計數據。一旦搜索受限于時間或計算力而終止，下一步行動將基于收集到的統計數據進行決策[5]。MCTS分為四個步驟：

（1）選擇（Selection）：在初始狀態下，棋盤狀態為空，以當前狀態 為根節點隨機選擇一個未被展開過的節點進行訪問。

（2）擴展（Expansion）在此過程中，將一個新的子節點添加到樹中，并將其添加到在選擇過程中最優到達的節點。

（3）模擬（Simulation）在這個過程中，通過選擇動作或策略進行模擬，直到達到結果或預定義的狀態。

（4）反向傳播（Backpropagation）在確定新添加節點的值之后，必須更新剩余的樹。因此，執行反向傳播過程，從新節點反向傳播到根節點。在此過程中，每個節點中存儲的模擬數量將增加。此外，如果新節點的模擬結果是 win，那么 win的數量也會增加[6]。MCTS流程圖如圖2所示。

圖2 MCTS搜索流程圖Fig.2 MCTS search flowchart

1.2 卷積神經網絡（Convolutional Neural Network，CNN）

卷積神經網絡是近年發展起來的，并引起廣泛重視的一種高效識別方法，20世紀60年代，Hubel和Wiesel在研究貓腦皮層中用于局部敏感和方向選擇的神經元時發現其獨特的網絡結構可以有效地降低反饋神經網絡的復雜性，繼而提出了卷積神經網絡。現在，CNN已經成為眾多科學領域的研究熱點之一，特別是在模式分類領域，由于該網絡避免了對圖像的復雜前期預處理，可以直接輸入原始圖像，因而得到了更為廣泛的應用[7]。

2 訓練框架搭建

我們本次使用的硬件為聯想 Thinkpad Edge E431，采用Intel 酷睿i5 3210M處理器，CPU主頻為 2.5 GHz。軟件環境為 Python3.7.2和 Tensor-Flow1.13。由于CPU算力有限，我們以8x8的棋盤作為研究。我們首先以MCTS為基礎設計五子棋的搜索算法，再利用該算法與CNN的算法進行對弈，將對弈結果反饋給模型，使該模型能夠實時更新最新數據，不斷提升模型的棋力。以下將該模型簡稱為self-play模型，如圖3所示。

在 self-play中，相應的 s為當前狀態，z是self-play的結果，在描述時二者都基于當前游戲者視角進行，一般通過兩個二值矩陣來對當前兩個游戲者棋子的位置進行描述。不過在實際的對局中，一局中每一個中的z需要在對局結束后才可確定出，如判斷發現最后勝者是 s局面對應的當前游戲者，則z=1，而若敗者是，則z=–1，在平局情況下，z=0。

圖3 Self-play過程示意圖Fig.3 Self-play process diagram

我們首先將棋盤信息定義為矩陣T，分別用0、1、–1來填充。其中 0代表空位，即未有落子的點位，令1代表黑棋落子點，–1代表白棋落子點。再將矩陣T當作CNN的訓練數據。

利用TensorFlow的API函數：tf.layers.conv2d創建每一個二維卷積層，將輸入進行卷積來輸出一個 tensor。首先定義一個策略網絡類（class PolicyValueNet），在該類下我們可以自由定義PolicyValueNet的各種屬性。我們首先將矩陣 T定義為輸入層，然后定義三個公共的全卷積網絡，其filters參數分別為32、64、128，kernal_size為3 3×，padding=“same”，data_format=“channels_last”，激活函數為 ReLU函數，其他參數設置為默認值。ReLU函數圖像如圖4(a)所示。

接著以上述第三個二維卷積層為輸入層定義一個激活網絡，其參數為：filters=4，kernal_size=[3,3]，padding=“same”，data_format=“channels_last”，激活函數同樣為ReLU激活，其他參數設置為默認值。接著進一步分成policy和value兩個輸出。在policy端，先通過 4個濾波器進行降維，接著通過tf.layers.dense()定義全連接層，filters=2，units=board_height * board_width，activation=tf.nn.log_softmax，使用softmax非線性函數直接輸出棋盤上每個位置的落子概率。其中參數units表示輸出的維度大小，改變inputs的最后一維。log_softmax激活函數為：

其中，logits表示一個非空的Tensor，且該tensor必須是下列類型之一：half，float32，float64；axis表示將執行 softmax的維度，默認值為–1，表示最后一個維度。

在 value這一端再定義評估網絡（Evaluation Networks）。同樣利用tf.layers.conv2d()函數來構建。同樣以上述三個公共二維卷積網絡為輸入，filters=2，kernal_size=[1,1]，padding=“same”，data_format=“channels_last”，activation 為 ReLU 激活函數，其他參數設置為默認值。然后再用tf.layers.dense()命令定義兩個全連接層，其中前者的輸入為以上的卷積層，units 64= ，ReLU為激活函數；后者的輸入為第一個全連接層，units=1，激活函數為 tanh，函數圖像如圖 4(b)所示。在此基礎上輸出的為一個評估分數，可通過其反映出當前狀態，具體表達式如下。

圖4 ReLU和tanh函數圖像Fig.4 ReLU and tanh function images

根據前面的論述可知，策略價值網絡在處理過程中輸入為當前局面描述s，當前評分π則為輸出，通過自學習中采集的(,,)szπ數據來對這種網絡進行訓練。具體分析以上的訓練示意圖可知，在此訓練過程中，需要控制這種網絡的輸出概率p和MCTS的概率π趨于一致，使得對應的評分結果和真實的對局結果 z盡可能的接近，從而實現相應的處理目標[8]。進行優化分析可知，這種操作也就 是在self-play數據集中通過迭代操作而使損失函數最小：

其中第三項主要作用是避免過擬合，為盡可能的降低損失函數，在訓練過程中需要不斷的使得其值減小。

3 數據分析

我們在8x8的棋盤上與MCTS算法進行五子棋對弈，其每一下一步所進行的搜索信息如圖5所示。MCTS會對計算機每一個落子點位所進行的搜索，其中包括每一個點位的概率和對應的勝率。從圖中可知，總共進行了 4701次搜索，最大搜索深度為41層，最終得出的坐標為[6,6]。正因為MCTS搜索算法需要從當前局面開始往下遍歷一定深度，所以耗時時間長。

圖5 MCTS搜索點位信息圖Fig.5 MCTS search point infographic

當對MCTS&CNN的模型進行訓練時，相應的函數值和self-play局數的相關性如圖6所示，在此實驗過程中開展了3000局對局，此函數的值也最終降低到2.2。

圖6 損失函數Fig.6 Loss function

對此模型而言，self-play數據可基于最新模型確定出，且進行一定更新操作，雖然表面上看基于最優模型確定出的self-play數據可滿足要求，有較高的收斂性，對提高結果的準確性有重要的意義，本文進行對比分析發現對6×6棋盤的4子棋而言，通過這種模型進行更新得到的self-play數據進行訓練，五百局后所得模型就可有效的滿足應用要求，對比分析發現基于最優模型對應的self-play數據進行訓練，在同樣的條件下需要1500局才可滿足要求[9]。

在訓練過程中，除了觀察到損失函數在慢慢減小，我們一般還會關注策略價值網絡輸出的策略（輸出的落子概率分布）的熵（entropy）的變化情況。正常情況下，最開始的時候，策略網絡基本上是均勻的隨機輸出落子的概率，因此熵會比較大。隨著訓練過程的慢慢推進，策略網絡會慢慢學會在不同的局面下哪些位置應該有更大的落子概率，也就是說落子概率的分布不再均勻，會有比較強的偏向，這樣熵就會變小。也正是由于策略網絡輸出概率的偏向，才能幫助MCTS在搜索過程中能夠在更有潛力的位置進行更多的模擬，從而在比較少的模擬次數下達到比較好的性能。圖7展示的是同一次訓練過程中觀察到的策略網絡輸出策略的熵的變化情況[10]。可以看到，當訓練到500局左右時，熵已經降到了 2，但熵并不穩定，在 2左右來回波動，直到2300局之后熵才穩定了下來，一直到3050局訓練結束。

圖7 熵的變化曲線圖Fig.7 Change graph of entropy

傳統的MCTS算法需要在每一局面往下搜索很多層，之后還需要將每一個子樹的得分往上回溯更新，所以耗時嚴重，且容易陷入局部最優化的局面。圖8為一局純MCTS算法的五子棋耗時曲線圖，可以看到MCTS每一步搜索所用平均時間為7 s左右，波動最大接近1.5 s。圖9為self-paly300局對弈所

用時間，每個點表示一局比賽所用平均時間（平均時間：己方一局對弈總耗時和落子次數的比值）其中紅色曲線代表MCTS耗時，藍色曲線表示MCTS和卷積神經網絡耗時，可以看出后者極大縮短了計算機每一步落子“思考”的時間，且穩定在1 s附近。

圖8 一局中MCTS搜索時間曲線Fig.8 MCTS search time curve in one round

圖9 300局self-play的時間曲線Fig.9 300 rounds of self-play time curve

4 結果與總結

傳統的MCTS搜算算法耗時長、且效果一般，五子棋棋力較弱。運用MCTS和卷積神經網絡訓練出的策略價值網絡不僅完美的克服了以上問題，且根據驗證結果表明建立的這種模型棋力較強，對真實玩家表現出很高的挑戰性。這種基于傳統搜索算法與神經網絡結合的方式，不僅能集成傳統算法的優勢，更能發揮出人工智能的魅力，使得我們在普通PC機上也能進行相關模型的訓練。