王亞杰,祁冰枝,張云博,丁傲冬
(沈陽航空航天大學(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)橥跗濉M跗蹇梢韵蚱渌谖恢玫?個斜線方向(左前方、右前方、左下方、右下方)上任意移動,且斜線上的連續(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),提出了分次搜索算法。
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)用。
近幾年,傳統(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é)點將被丟棄。
針對傳統(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次,并作對比。
傳統(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)研究。
通過實驗探究了剪枝操作節(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)行博弈程序。
為探究節(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é)點的搜索足夠充分,計算資源分配合理,勝率較高。
為了研究初次搜索與二次搜索比例因子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)整。
為了驗證結(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%。由此證明:采用分次搜索的方法是可行且有效的,通過對比驗證,本文算法的獲勝率明顯高于其他博弈算法。
將結(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ī)器博弈問題提供更加廣闊的思路和方法。