基于MCTS和卷積神經(jīng)網(wǎng)絡(luò)的五子棋策略研究

歐俊臣，沙 玲，楊淞文

（上海工程技術(shù)大學(xué) 機(jī)械與汽車工程學(xué)院，上海 201620）

0 引言

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

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

1 背景介紹

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

MCTS是一種通過(guò)在決策空間中獲取隨機(jī)樣本并根據(jù)結(jié)果構(gòu)建搜索樹(shù)來(lái)在給定域中查找最優(yōu)決策的方法。它已經(jīng)對(duì)人工智能（AI）方法產(chǎn)生了深遠(yuǎn)的影響，這些方法可以表示為連續(xù)決策樹(shù)，特別是游戲和規(guī)劃問(wèn)題。在搜索空間狹小的情況下存在盲目搜索。盲目搜索的意思就是，以當(dāng)前局勢(shì)為根節(jié)點(diǎn)，按照博弈樹(shù)展開(kāi)的形式，直到遍歷完整個(gè)搜索空間。這樣的遍歷方式有兩種，如圖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的主要概念是搜索，即沿著博弈樹(shù)向下的一組遍歷過(guò)程。單次遍歷的路徑會(huì)從根節(jié)點(diǎn)（當(dāng)前博弈狀態(tài)）延伸到?jīng)]有完全展開(kāi)的節(jié)點(diǎn)，未完全展開(kāi)的節(jié)點(diǎn)表示其子節(jié)點(diǎn)至少有一個(gè)未訪問(wèn)到。遇到未完全展開(kāi)的節(jié)點(diǎn)時(shí)，它的一個(gè)未訪問(wèn)子節(jié)點(diǎn)將會(huì)作為單次模擬的根節(jié)點(diǎn)，隨后模擬的結(jié)果將會(huì)反向傳播回當(dāng)前樹(shù)的根節(jié)點(diǎn)并更新博弈樹(shù)的節(jié)點(diǎn)統(tǒng)計(jì)數(shù)據(jù)。一旦搜索受限于時(shí)間或計(jì)算力而終止，下一步行動(dòng)將基于收集到的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行決策[5]。MCTS分為四個(gè)步驟：

（1）選擇（Selection）：在初始狀態(tài)下，棋盤狀態(tài)為空，以當(dāng)前狀態(tài) 為根節(jié)點(diǎn)隨機(jī)選擇一個(gè)未被展開(kāi)過(guò)的節(jié)點(diǎn)進(jìn)行訪問(wèn)。

（2）擴(kuò)展（Expansion）在此過(guò)程中，將一個(gè)新的子節(jié)點(diǎn)添加到樹(shù)中，并將其添加到在選擇過(guò)程中最優(yōu)到達(dá)的節(jié)點(diǎn)。

（3）模擬（Simulation）在這個(gè)過(guò)程中，通過(guò)選擇動(dòng)作或策略進(jìn)行模擬，直到達(dá)到結(jié)果或預(yù)定義的狀態(tài)。

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

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

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

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

2 訓(xùn)練框架搭建

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

在 self-play中，相應(yīng)的 s為當(dāng)前狀態(tài)，z是self-play的結(jié)果，在描述時(shí)二者都基于當(dāng)前游戲者視角進(jìn)行，一般通過(guò)兩個(gè)二值矩陣來(lái)對(duì)當(dāng)前兩個(gè)游戲者棋子的位置進(jìn)行描述。不過(guò)在實(shí)際的對(duì)局中，一局中每一個(gè)中的z需要在對(duì)局結(jié)束后才可確定出，如判斷發(fā)現(xiàn)最后勝者是 s局面對(duì)應(yīng)的當(dāng)前游戲者，則z=1，而若敗者是，則z=–1，在平局情況下，z=0。

圖3 Self-play過(guò)程示意圖Fig.3 Self-play process diagram

我們首先將棋盤信息定義為矩陣T，分別用0、1、–1來(lái)填充。其中 0代表空位，即未有落子的點(diǎn)位，令1代表黑棋落子點(diǎn)，–1代表白棋落子點(diǎn)。再將矩陣T當(dāng)作CNN的訓(xùn)練數(shù)據(jù)。

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

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

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

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

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

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

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

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

我們?cè)?x8的棋盤上與MCTS算法進(jìn)行五子棋對(duì)弈，其每一下一步所進(jìn)行的搜索信息如圖5所示。MCTS會(huì)對(duì)計(jì)算機(jī)每一個(gè)落子點(diǎn)位所進(jìn)行的搜索，其中包括每一個(gè)點(diǎn)位的概率和對(duì)應(yīng)的勝率。從圖中可知，總共進(jìn)行了 4701次搜索，最大搜索深度為41層，最終得出的坐標(biāo)為[6,6]。正因?yàn)镸CTS搜索算法需要從當(dāng)前局面開(kāi)始往下遍歷一定深度，所以耗時(shí)時(shí)間長(zhǎng)。

圖5 MCTS搜索點(diǎn)位信息圖Fig.5 MCTS search point infographic

當(dāng)對(duì)MCTS&CNN的模型進(jìn)行訓(xùn)練時(shí)，相應(yīng)的函數(shù)值和self-play局?jǐn)?shù)的相關(guān)性如圖6所示，在此實(shí)驗(yàn)過(guò)程中開(kāi)展了3000局對(duì)局，此函數(shù)的值也最終降低到2.2。

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

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

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

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

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

用時(shí)間，每個(gè)點(diǎn)表示一局比賽所用平均時(shí)間（平均時(shí)間：己方一局對(duì)弈總耗時(shí)和落子次數(shù)的比值）其中紅色曲線代表MCTS耗時(shí)，藍(lán)色曲線表示MCTS和卷積神經(jīng)網(wǎng)絡(luò)耗時(shí)，可以看出后者極大縮短了計(jì)算機(jī)每一步落子“思考”的時(shí)間，且穩(wěn)定在1 s附近。

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

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

4 結(jié)果與總結(jié)

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