歐俊臣，沙 玲，楊淞文

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

0 引言

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

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

1 背景介紹

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

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

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

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

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

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

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

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

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

1.2 卷積神經(jīng)網(wǎng)絡（Convolutional Neural Network，CNN）

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

2 訓練框架搭建

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

在 self-play中，相應的 s為當前狀態(tài)，z是self-play的結(jié)果，在描述時二者都基于當前游戲者視角進行，一般通過兩個二值矩陣來對當前兩個游戲者棋子的位置進行描述。不過在實際的對局中，一局中每一個中的z需要在對局結(jié)束后才可確定出，如判斷發(fā)現(xiàn)最后勝者是 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的訓練數(shù)據(jù)。

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

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

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

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

圖4 ReLU和tanh函數(shù)圖像Fig.4 ReLU and tanh function images

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

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

3 數(shù)據(jù)分析

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

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

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

圖6 損失函數(shù)Fig.6 Loss function

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

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

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

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

用時間，每個點表示一局比賽所用平均時間（平均時間：己方一局對弈總耗時和落子次數(shù)的比值）其中紅色曲線代表MCTS耗時，藍色曲線表示MCTS和卷積神經(jīng)網(wǎng)絡耗時，可以看出后者極大縮短了計算機每一步落子“思考”的時間，且穩(wěn)定在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 結(jié)果與總結(jié)

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