結(jié)合神經(jīng)網(wǎng)絡(luò)的改進(jìn)UCT在國際跳棋中的應(yīng)用

王亞杰，祁冰枝，張云博，丁傲冬

（沈陽航空航天大學(xué) 工程訓(xùn)練中心，沈陽 110135）

人工智能是當(dāng)前最具有挑戰(zhàn)性的研究課題，早期人工智能的發(fā)展從機(jī)器博弈開始［1］，它是讓計算機(jī)程序模仿人類思維對弈，是檢驗人工智能發(fā)展水平和計算機(jī)技術(shù)的一個重要方法。如何提高計算機(jī)程序的智能水平是機(jī)器博弈研究的核心所在［2］。2016年谷歌程序AlphaGo［3］擊敗了人類世界圍棋大師，引起了全世界的關(guān)注，這極大地激發(fā)了人們的挑戰(zhàn)熱情和創(chuàng)新精神。近年來，國內(nèi)外舉辦的各類計算機(jī)博弈比賽促進(jìn)了計算機(jī)博弈理論和方法的研究，也給機(jī)器博弈領(lǐng)域注入了新鮮血液。

國際跳棋歷史悠久，是計算機(jī)博弈領(lǐng)域的早期研究對象［4－5］。國際跳棋有兵棋和王棋兩類棋子，開局只有雙方各自的兵棋，當(dāng)一方的棋子到達(dá)對方的底線之后則升變?yōu)橥跗濉Ｍ跗蹇梢韵蚱渌谖恢玫?個斜線方向（左前方、右前方、左下方、右下方）上任意移動，且斜線上的連續(xù)空位均可成為王棋的落子點；兵棋每次只能單步向左前方或者右前方移動，兵棋和王棋均存在連續(xù)跳吃策略。

在國際跳棋機(jī)器博弈研究中，傳統(tǒng)博弈算法側(cè)重于有效的搜索和精確的評估，例如：極大極小算法（minimax）［5－6］、alpha-beta剪枝算法（alphabeta，α-β）［7］、蒙特卡洛模擬（monte carlo，MC）、上限置信區(qū)間（upper confidence bound apply to tree，UCT）算法［8］和啟發(fā)式搜索算法等。

許多研究學(xué)者將傳統(tǒng)博弈算法進(jìn)行結(jié)合，軍棋［9］、2 048［10］等博弈游戲在傳統(tǒng)博弈算法中結(jié)合了蒙特卡洛樹搜索，并通過剪枝以及調(diào)整蒙特卡洛模擬次數(shù)實現(xiàn)對高價值節(jié)點的關(guān)注，取得了較好的對弈效果；郭曉霞等［11］利用知識庫方法存儲專家知識提升棋力，焦尚斌等［12］利用置換表提高博弈系統(tǒng)搜索效率。

近年來，深度學(xué)習(xí)算法受到國內(nèi)外學(xué)者的廣泛關(guān)注。深度學(xué)習(xí)在機(jī)器博弈中的應(yīng)用主要通過神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)現(xiàn)有的經(jīng)驗知識，以此改進(jìn)其中的參數(shù)，最終輸出勝率最大的策略［13］。谷歌程序Alpha-Go學(xué)習(xí)了大量人類圍棋專家的經(jīng)驗知識，并在對弈過程中模擬人類專家進(jìn)行決策；AlphaGo Zero以圍棋的規(guī)則知識為基礎(chǔ)，使用純粹的深度強(qiáng)化學(xué)習(xí)技術(shù)和蒙特卡羅樹搜索，經(jīng)過3 d自我對弈以100∶0擊敗了上一版本的AlphaGo；AlphaZero在AlphaGo Zero的基礎(chǔ)上，同時實現(xiàn)了國際象棋、日本將棋和圍棋3種游戲的突破，在這3種游戲上均達(dá)到了超人類大師的水平。

傳統(tǒng)博弈算法中的UCT算法，通過模擬雙方走步預(yù)測棋局走勢，并回溯更新信息。搜索過程中要經(jīng)過大量模擬和搜索才能得到較優(yōu)策略，所以占用較多的計算資源和花費(fèi)較長的時間。結(jié)合神經(jīng)網(wǎng)絡(luò)的傳統(tǒng)UCT算法（UCT-NN）雖然極大地提升了棋力，但是存在著搜索節(jié)點質(zhì)量偏低的問題［14］。本文根據(jù)國際跳棋特點，結(jié)合神經(jīng)網(wǎng)絡(luò)模型，對傳統(tǒng)UCT方法進(jìn)行改進(jìn)，提出了分次搜索算法。

1 UCT算法介紹

1.1 傳統(tǒng)UCT算法

Kocsia等［15］構(gòu)建了蒙特卡洛樹搜索（monte carlo tree search，MCTS）算法并通過擴(kuò)展UCB（up-per confidence bound，UCB）公式到樹搜索，將其命名為UCT算法。UCT算法又稱上限置信區(qū)間算法，是由蒙特卡羅樹搜索與UCB公式相結(jié)合得到的算法［16］。UCT算法思想來源于解決多臂老虎機(jī)問題模型，老虎機(jī)的每個手臂提供隨機(jī)的獎勵，賭徒根據(jù)一定的策略決定拉動哪個手臂，以及拉動多少次才能獲得最大收益。該問題解決的方法是根據(jù)現(xiàn)有的探索結(jié)果選擇評價值較高的節(jié)點。其核心計算過程如式（1）所示［17］：

UCT算法能夠有效掌握探索和收益之間的平衡，盡量使玩家的收益最大化。該算法從根節(jié)點開始，每次選擇UCB值最大的節(jié)點，直到搜索到其葉子節(jié)點為止，可以增加最優(yōu)節(jié)點被選擇的概率，因而在機(jī)器博弈領(lǐng)域得到廣泛應(yīng)用。

1.2 結(jié)合神經(jīng)網(wǎng)絡(luò)的傳統(tǒng)UCT算法

近幾年，傳統(tǒng)博弈算法與神經(jīng)網(wǎng)絡(luò)結(jié)合的方式，在博弈程序的智能性上取得了顯著的提高。以AlphaGo Zero［18］為例，它以強(qiáng)化學(xué)習(xí)和蒙特卡羅樹搜索為核心，兩者共同決策選擇最優(yōu)節(jié)點［19］，以使游戲獲得最終勝利。其中，蒙特卡羅樹搜索部分主要采用了UCB公式與神經(jīng)網(wǎng)絡(luò)估值相結(jié)合。AlphaGO Zero中的蒙特卡洛樹搜索過程分為選擇、擴(kuò)展、模擬和回溯更新4個階段，如圖1所示。

圖1中的fθ代表神經(jīng)網(wǎng)絡(luò)，P代表子節(jié)點的先驗概率P（s，a），V代表子節(jié)點的價值v（sL），Q代表平均行動價值Q（s，a），U代表節(jié)點的UCB值U（s，a）。

第1步選擇階段：從博弈樹的根節(jié)點開始執(zhí)行樹搜索策略進(jìn)行分支選擇，直到搜索到葉子節(jié)點為止，其中博弈樹搜索過程利用式（2）進(jìn)行策略選擇，博弈樹每個節(jié)點（s，a）的信息簡化為｛N（s，a），W（s，a），Q（s，a），P（s，a）｝，如式（2）和式（3）所示：

其中，N（s，a）表示該邊的搜索次數(shù)，W（s，a）是節(jié)點總收益，Q（s，a）是每一步的平均行動價值，P（s，a）是執(zhí)行樹搜索策略時的先驗概率，U（s，a）表示該節(jié)點的UCB值，C是一個常量參數(shù)，s代表是節(jié)點狀態(tài)，a代表所選擇的動作。

最后，U（st，a）＋Q（st，a）值最大的子分支被選擇成為下一步的搜索分支，沿著該子分支一直走到當(dāng)前節(jié)點的葉子節(jié)點處。

第2步擴(kuò)展階段：如果此時的子節(jié)點不是棋局結(jié)束狀態(tài)，要對該節(jié)點進(jìn)行擴(kuò)展。根據(jù)當(dāng)前節(jié)點的棋局狀態(tài)，生成所有合法策略即該節(jié)點的子節(jié)點，對每一個子節(jié)點創(chuàng)建一個新的葉子節(jié)點，并與當(dāng)前節(jié)點連接起來，構(gòu)成整體博弈樹的一個分支。將擴(kuò)展得到的新子節(jié)點上的初始信息設(shè)置如式（5）所示：

第3步模擬階段：此時利用神經(jīng)網(wǎng)絡(luò)對當(dāng)前的葉子節(jié)點的狀態(tài)sL做出預(yù)測，輸出當(dāng)前葉子節(jié)點的各個子節(jié)點位置sL的落子概率p，以及對應(yīng)的價值v（sL）。經(jīng)過模擬之后，先前的葉子節(jié)點sL成為博弈樹的一個子節(jié)點。

第4步回溯更新：擴(kuò)展和模擬完成后，需要進(jìn)行回溯，向上更新祖先節(jié)點的信息。新葉子節(jié)點分支的信息被回溯累積到祖先節(jié)點，從每個葉子節(jié)點一直回溯到根節(jié)點，上層分支數(shù)據(jù)也依次被更新。更新的數(shù)據(jù)以及更新方式如式（6）（7）和（8）所示：

在一次真正行棋前，一般會進(jìn)行上千次搜索，每次搜索都會進(jìn)行上述4個階段。搜索完畢后，最后根據(jù)公式（9）選擇落子位置。

其中，π（a｜s）是在當(dāng)前節(jié)點下，通過蒙特卡洛樹搜索得到的每種策略被選擇的實際概率；N（s，b）是當(dāng)前節(jié)點被選擇的次數(shù)；τ是實際行棋過程中控制探索程度的參數(shù)。在博弈的過程中，確定最終落子點之后，落子位置節(jié)點會變成根節(jié)點，而之前在該節(jié)點下的子樹的搜索數(shù)據(jù)會被繼續(xù)沿用，落子位置節(jié)點的其他兄弟節(jié)點將被丟棄。

2 結(jié)合神經(jīng)網(wǎng)絡(luò)的改進(jìn)UCT算法

2.1 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計

針對傳統(tǒng)UCT算法僅僅利用UCB值來選擇搜索節(jié)點，不能有效對高潛力節(jié)點進(jìn)行充分搜索的問題。本文將神經(jīng)網(wǎng)絡(luò)方法引入UCT算法中，利用UCB值和已訓(xùn)練好的網(wǎng)絡(luò)模型輸出每一步的平均行動價值Q，共同決定搜索的節(jié)點數(shù)量，盡量保留高潛力節(jié)點，并對其充分展開搜索，以此提高對弈獲勝的概率。

本文的神經(jīng)網(wǎng)絡(luò)參考AlphaGo Zero，基于Tensorflow框架實現(xiàn)，神經(jīng)網(wǎng)絡(luò)主體由輸入層、隱藏層以及輸出層3個模塊構(gòu)成，神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。輸入數(shù)據(jù)為10×10×5的張量，前4個10×10的張量為當(dāng)前黑方兵棋分布、黑方王棋分布、白方兵棋分布、白方王棋分布。最后一個是當(dāng)前行棋方的顏色代碼，置1代表黑方，置0代表白方。中間隱藏層由14個殘差塊組成，原始AlphaGo Zero在19×19×17的張量做卷積運(yùn)算后，使用19層或者39層的深度殘差網(wǎng)絡(luò)，本文因在單機(jī)上實現(xiàn)100格國際跳棋程序，計算能力有限，設(shè)置為14個。輸出數(shù)據(jù)是每種策略對應(yīng)的被選擇的概率值p和動作價值v（sL）。

圖2 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)示意圖

損失函數(shù)如式（10）所示：

其中：z是自對弈過程中的勝負(fù)情況，取值為｛－1，0，1｝；v為神經(jīng)網(wǎng)絡(luò)輸出的勝負(fù)情況，取值為｛－1，0，1｝；π是每種策略被選到的實際概率；p是神經(jīng)網(wǎng)絡(luò)預(yù)測每種策略被選到的概率；λ是控制L2正則化項權(quán)重調(diào)整的參數(shù)，防止過擬合；θ是神經(jīng)網(wǎng)絡(luò)的參數(shù)。

訓(xùn)練的樣本數(shù)據(jù)是經(jīng)過30 000局自對弈產(chǎn)生，優(yōu)化器是隨機(jī)梯度下降（stochastic gradient descent，SGD），學(xué)習(xí)率從0.001開始動態(tài)調(diào)整，batch size為256，迭代次數(shù)為3，激活函數(shù)選用線性整流函數(shù)（rectified linear unit，ReLU），實驗中因算力有限分別設(shè)置為500次和1 000次，并作對比。

2.2 分次搜索在UCT中的應(yīng)用

傳統(tǒng)UCB公式在搜索前期由于數(shù)據(jù)較少，不能準(zhǔn)確地評估節(jié)點潛力，需要大量的搜索結(jié)果才能較準(zhǔn)確地評估節(jié)點，這導(dǎo)致搜索大量低潛力節(jié)點造成了計算資源的浪費(fèi)。所以，有必要在對節(jié)點進(jìn)行初次搜索之后，利用剪枝操作去除一些低潛力節(jié)點，然后側(cè)重搜索高潛力節(jié)點。改進(jìn)UCT算法的搜索過程主要分為3步：初次搜索、剪枝操作、二次搜索。具體流程如圖3所示。

圖3 改進(jìn)UCT算法的搜索流程示意圖

2.2.1 初次搜索

根據(jù)式（4）中U（st，a）＋Q（st，a）的計算方法，利用神經(jīng)網(wǎng)絡(luò)與UCB公式對搜索節(jié)點進(jìn)行初次選擇。首先，根據(jù)已訓(xùn)練的神經(jīng)網(wǎng)絡(luò)提供的每個節(jié)點的先驗概率P（s，a），計算U（st，a）＋Q（st，a）的值，選擇U（st，a）＋Q（st，a）值最大的節(jié)點進(jìn)行模擬；其次，本文算法利用UCB公式中的常量參數(shù)C控制搜索的廣度，它的范圍在0～1之間，C越大就越偏向于廣度搜索，C越小就越偏向于深度搜索，盡可能使每個節(jié)點都能被選擇到，因此實驗中設(shè)置為1；然后，通過擴(kuò)展、模擬，到達(dá)葉子節(jié)點之后將預(yù)測結(jié)果回溯更新至該節(jié)點，同時繼續(xù)計算每個節(jié)點的U（st，a）＋Q（st，a）值，并回溯更新每個節(jié)點的評估值。

2.2.2 剪枝操作

為探究國際跳棋對弈過程中博弈樹的規(guī)模大小，對每個狀態(tài)的子節(jié)點數(shù)量進(jìn)行了統(tǒng)計，圖4是對弈過程中平均每步可選策略數(shù)量的統(tǒng)計結(jié)果。由圖4可知，對弈中每一步可選擇的策略分支通常為1～2個或7～15個。1～2個分支的情況容易選擇，但在7～15個分支的情況下，每一步的子節(jié)點較多會導(dǎo)致展開的博弈樹規(guī)模較大，較高價值的節(jié)點被搜索到的概率也會降低。

圖4 國際跳棋平均每步可選策略數(shù)量統(tǒng)計直方圖

對一些節(jié)點進(jìn)行初次搜索之后，可以證明其不屬于表現(xiàn)較好的節(jié)點，因此需要對其進(jìn)行剪枝操作。在傳統(tǒng)算法中，剪枝策略包括剪枝算法、啟發(fā)式算法和一些輔助剪枝手段。本文搜索節(jié)點的選擇通過計算U（st，a）＋Q（st，a）的值確定，初次搜索完成后，統(tǒng)計每個節(jié)點被訪問的次數(shù)，對訪問頻率較低的節(jié)點進(jìn)行剪枝操作，通過壓縮搜索空間以提高算法搜索效率。

圖5統(tǒng)計了保留節(jié)點的搜索次數(shù)之和占總體搜索次數(shù)的比例。由圖5可知：多數(shù)情況下前3個分支集中了超過95%的搜索次數(shù)，被選擇的概率較大；其他子節(jié)點搜索次數(shù)占比總和低于5%，被選到的概率微乎其微。因此在初次搜索之后，將節(jié)點保留數(shù)量因子R的值設(shè)置為3，并在后面通過實驗驗證R對勝率的影響。

圖5 保留節(jié)點搜索次數(shù)之和占總體搜索次數(shù)比例曲線

2.2.3 二次搜索

當(dāng)保留節(jié)點的被選擇次數(shù)占比超過80%之后，其余的節(jié)點不可能再成為搜索次數(shù)最多的節(jié)點，到此時直接選擇該節(jié)點，本次搜索結(jié)束。根據(jù)式（9）可知搜索次數(shù)最多的節(jié)點是最終落子的位置。經(jīng)過初次搜索和剪枝操作后，得到獲勝潛力較高的部分節(jié)點，再結(jié)合神經(jīng)網(wǎng)絡(luò)，繼續(xù)對這些節(jié)點進(jìn)行二次搜索。保留下來的節(jié)點通過神經(jīng)網(wǎng)絡(luò)得到平均行動價值Q（st，a）和UCB值U（st，a），選擇兩者加和最大值的節(jié)點繼續(xù)搜索。

初次搜索選擇出獲勝潛力較高的節(jié)點，二次搜索側(cè)重于對剪枝后保留下來的高潛力節(jié)點進(jìn)行重點搜索。當(dāng)初次搜索次數(shù)過少時，各個節(jié)點被選擇次數(shù)整體偏少，無法區(qū)分潛力節(jié)點；當(dāng)初次搜索次數(shù)過多時，二次搜索次數(shù)有限，可能造成對高潛力節(jié)點搜索的不充分，導(dǎo)致勝率降低。因此，初次搜索和二次搜索之間的比例因子P需要根據(jù)實驗獲得最優(yōu)值。在實驗部分中，本文對比例因子的具體值進(jìn)行了相關(guān)研究。

3 實驗與分析

通過實驗探究了剪枝操作節(jié)點保留數(shù)量因子R和初次搜索與二次搜索比例因子P兩個參數(shù)對勝率的影響，得出兩個因子當(dāng)前情況下的最佳取值，并與其他博弈算法進(jìn)行了對比實驗。實驗環(huán)境是Pycharm2019，使用Python3.7實現(xiàn)本文方法，在一臺Inter（R）Core（TM）i7-4720HQ 2.6 GHz，內(nèi)存為16GB，顯卡為NVIDIA GeForce GTX 950M4GB的Window 10操作系統(tǒng)上運(yùn)行博弈程序。

3.1 節(jié)點保留數(shù)量的確定

為探究節(jié)點保留數(shù)量因子R與勝率之間的關(guān)系，本文設(shè)計了不同搜索次數(shù)S和節(jié)點保留數(shù)量因子R的組合。每種組合分別與UCT-NN算法對弈1 000局，蒙特卡洛搜索次數(shù)S分別為500和1 000次，兩次搜索比例因子P取1∶1，并使用相同的神經(jīng)網(wǎng)絡(luò)訓(xùn)練模型。實驗結(jié)果如表1所示。

表1 不同搜索次數(shù)S與節(jié)點保留數(shù)量因子R組合下的實驗結(jié)果

表1的實驗結(jié)果表明：節(jié)點保留數(shù)量因子R對勝率有著較大的影響。在相同的搜索次數(shù)下，R設(shè)置不同的值，勝率隨之不同。當(dāng)R＝2時，保留的節(jié)點過少，漏掉了一些有潛力的節(jié)點，造成勝率較低；當(dāng)R＝4時，保留的節(jié)點過多，對高潛力節(jié)點搜索次數(shù)不足，同樣造成勝率較低。經(jīng)過多次試驗發(fā)現(xiàn)，當(dāng)R＝3時，對高潛力節(jié)點的搜索足夠充分，計算資源分配合理，勝率較高。

3.2 兩次搜索比例的確定

為了研究初次搜索與二次搜索比例因子P對勝率的影響，進(jìn)行了如下實驗。其中，每組實驗搜索次數(shù)S設(shè)置為500和1 000次，節(jié)點保留數(shù)量因子R＝3，對每種組合分別與UCT-NN算法進(jìn)行對弈1 000局，實驗結(jié)果如表2所示。

表2 不同搜索次數(shù)S與兩次搜索比例因子P組合下的實驗結(jié)果

表2中的實驗結(jié)果表明：當(dāng)搜索次數(shù)為500時，比例因子P設(shè)置為1∶1時，勝率最高；當(dāng)搜索次數(shù)為1 000時，比例因子P設(shè)置為1∶3時，勝率最高。隨著搜索次數(shù)的改變，最優(yōu)比例也在隨之調(diào)整。

3.3 與其他博弈算法的對比

為了驗證結(jié)合神經(jīng)網(wǎng)絡(luò)的改進(jìn)UCT算法的性能，將本文算法與Minimax算法、α-β算法以及UCT-NN算法進(jìn)行對比。在對比實驗中，取節(jié)點保留數(shù)量因子R＝3、搜索比例因子P為1∶1、搜索次數(shù)均為500次的情況下，對弈1 000局，得到實驗結(jié)果如表3所示。

表3 實驗結(jié)果

由表3可知：結(jié)合神經(jīng)網(wǎng)絡(luò)的改進(jìn)UCT算法分別與其他3種算法對比，勝率依次為93.8%、87.4%、65.9%。由此證明：采用分次搜索的方法是可行且有效的，通過對比驗證，本文算法的獲勝率明顯高于其他博弈算法。

4 結(jié)論

將結(jié)合神經(jīng)網(wǎng)絡(luò)的改進(jìn)UCT算法應(yīng)用到國際跳棋中，將原來單一的搜索方式改進(jìn)為“初次搜索－剪枝操作－二次搜索”的組合方式。在搜索過程中結(jié)合已訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)模型輸出動作價值和落子概率，選擇高潛力節(jié)點。并通過實驗獲得較優(yōu)的節(jié)點保留數(shù)量因子R和兩次搜索比例因子P，側(cè)重搜索高潛力節(jié)點，提高搜索過程中節(jié)點的平均價值，進(jìn)而提升博弈程序的棋力。

本文算法僅在固定的搜索模式中獲得了較優(yōu)的參數(shù)，沒有探究不同神經(jīng)網(wǎng)絡(luò)模型和搜索次數(shù)對上述參數(shù)和博弈程序棋力的影響，未來將在這一方面進(jìn)行深入的研究和優(yōu)化，為解決機(jī)器博弈問題提供更加廣闊的思路和方法。