管延霞,劉遜韻,劉運(yùn)韜,謝 旻，徐新海

(1.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073；2.軍事科學(xué)院戰(zhàn)爭(zhēng)研究院，北京 100091)

1 引言

計(jì)算機(jī)博弈是衡量人工智能發(fā)展水平的重要測(cè)試平臺(tái)之一[1]，已在象棋、圍棋等棋類博弈的決策問(wèn)題上取得了優(yōu)異的成果[2,3]。計(jì)算機(jī)博弈目前的研究重點(diǎn)在于多智能體博弈。

多智能體會(huì)導(dǎo)致博弈過(guò)程中的動(dòng)態(tài)空間和狀態(tài)空間呈指數(shù)級(jí)增長(zhǎng)，使得決策的搜索和選擇過(guò)程需要消耗一定的時(shí)間和計(jì)算資源[4]。計(jì)算機(jī)資源的并行協(xié)作可以有效降低多智能體博弈中的維度災(zāi)難等問(wèn)題。但是，該方法的主要難點(diǎn)在于如何有效利用計(jì)算資源并行加速搜索過(guò)程，以及如何實(shí)現(xiàn)信息的有效傳遞。

本文選取Pommerman[5]作為研究平臺(tái)，針對(duì)多智能體博弈問(wèn)題中的蒙特卡洛樹搜索算法展開研究。Pommerman是一種通過(guò)放置炸彈來(lái)淘汰敵人的多智能體博弈環(huán)境。博弈過(guò)程中的搜索算法優(yōu)化是博弈性能提升的關(guān)鍵，針對(duì)原有蒙特卡洛樹搜索算法搜索耗時(shí)過(guò)長(zhǎng)的問(wèn)題，本文借鑒蒙特卡洛樹搜索常用的并行方法，對(duì)博弈中的搜索階段進(jìn)行并行優(yōu)化，旨在充分利用有限的計(jì)算機(jī)資源，縮短搜索算法收斂到近似最優(yōu)決策策略的學(xué)習(xí)時(shí)間。本文具體工作如下所示：

(1)建立了適合并行搜索策略的Pommerman博弈算法——基于勝率估值傳遞的并行蒙特卡洛樹搜索算法，實(shí)現(xiàn)了搜索策略框架并行化，構(gòu)建了多個(gè)子進(jìn)程的并行機(jī)制，有效縮短了決策時(shí)間，提高了決策效率。

(2)將構(gòu)建的并行算法應(yīng)用于Pommerman的不同游戲模式，并分別與對(duì)應(yīng)的原始搜索算法進(jìn)行了性能對(duì)比，定量分析了本文算法的優(yōu)勢(shì)。

2 蒙特卡洛樹搜索算法并行優(yōu)化現(xiàn)狀

Pommerman博弈平臺(tái)采用蒙特卡洛樹搜索MCTS(Monte Carlo Tree Search)算法[6-9]做出博弈策略，該搜索算法將蒙特卡洛算法應(yīng)用于博弈樹搜索過(guò)程中。圍棋中的AlphaGo[2,3]即是以MCTS算法為基礎(chǔ)進(jìn)行研發(fā)的。

MCTS算法是在搜索空間巨大的情況下仍然有效的算法。與MCTS算法出眾的表現(xiàn)相對(duì)應(yīng)，龐大的搜索空間使得MCTS算法在決策時(shí)耗費(fèi)了更長(zhǎng)的時(shí)間[10]。因此，研究蒙特卡洛樹搜索算法的并行優(yōu)化十分必要[11-13]。文獻(xiàn)[14]表明，蒙特卡洛樹搜索算法可以使用如圖1所示的葉并行化(Leaf Parallelization)、樹并行化(Tree Parallelization)和根并行化(Root Parallelization)3種不同的方法進(jìn)行并行化。3種并行方法的優(yōu)劣不同，葉并行化實(shí)現(xiàn)簡(jiǎn)單但缺乏節(jié)點(diǎn)探索性;樹并行化可以最小化通信開銷但會(huì)導(dǎo)致節(jié)點(diǎn)的過(guò)度開發(fā);根并行化雖然減少了進(jìn)程通信但同時(shí)也減少了每個(gè)進(jìn)程的博弈模擬次數(shù)，也在一定程度上降低了決策的準(zhǔn)確性。

Figure 1 Mainstream parallelization methods of Monte Carlo tree search algorithm

在對(duì)MCTS進(jìn)行并行優(yōu)化設(shè)計(jì)時(shí)，不僅要考慮如何跟蹤得到正確的統(tǒng)計(jì)數(shù)據(jù)，還要盡量減少進(jìn)程之間的通信開銷。

MCTS算法依賴當(dāng)前游戲狀態(tài)之前的采樣信息[15]來(lái)保持未知領(lǐng)域的探索和已有經(jīng)驗(yàn)的利用之間的平衡。當(dāng)使用多個(gè)工作程序并行化蒙特卡洛樹搜索算法部署時(shí)，要確保每個(gè)工作程序都能獲得最新的統(tǒng)計(jì)信息。在并行化過(guò)程中，本文想要盡可能實(shí)現(xiàn)如圖2a所示的理想并行化，減少如圖2b所示真實(shí)并行化可能會(huì)出現(xiàn)的進(jìn)程沖突等問(wèn)題。

Figure 2 Parallelization of Monte Carlo tree search algorithm

3 基于勝率估值傳遞的并行蒙特卡洛樹搜索算法

3.1 算法設(shè)計(jì)

基于多個(gè)進(jìn)程根節(jié)點(diǎn)回報(bào)值匯總的思想，本文提出了一種基于勝率估值傳遞的并行蒙特卡洛樹搜索算法。算法借鑒Root Parallelization[7]的思路，如圖3所示，在進(jìn)行MCTS搜索之前主進(jìn)程將當(dāng)前的游戲狀態(tài)及游戲策略傳遞給各子進(jìn)程，并將探索任務(wù)平均分配到各子進(jìn)程中，使多個(gè)子進(jìn)程基于同一個(gè)根節(jié)點(diǎn)狀態(tài)獨(dú)立并行執(zhí)行搜索過(guò)程。每個(gè)子進(jìn)程完成探索任務(wù)后，將回報(bào)信息傳遞給主進(jìn)程，主進(jìn)程依據(jù)最終的匯總信息進(jìn)行決策并更新搜索策略。主進(jìn)程將更新后的信息再次傳遞給子進(jìn)程，循環(huán)反復(fù)直至游戲狀態(tài)滿足結(jié)束條件。

Figure 3 Parallelization of search process

只在進(jìn)程的開始和結(jié)束時(shí)進(jìn)行算法進(jìn)程之間的信息交互，以最小化子進(jìn)程之間的信息交互。相比于采用樹并行化實(shí)現(xiàn)的Ary[16]來(lái)說(shuō)減少了進(jìn)程交互；相比于葉并行化的實(shí)現(xiàn)，避免了節(jié)點(diǎn)頻繁加解鎖；相較于根并行化的實(shí)現(xiàn)，本文設(shè)計(jì)的算法各子進(jìn)程的搜索耗時(shí)相當(dāng)，減少了子進(jìn)程信息收集的等待時(shí)差。本文設(shè)計(jì)的算法能夠有效利用計(jì)算資源，縮短搜索時(shí)間，提高M(jìn)CTS的搜索效率。

圖4給出了實(shí)現(xiàn)并行化的搜索過(guò)程，主要分為4步：

(1)游戲開局，參數(shù)初始化，主進(jìn)程給子進(jìn)程分配任務(wù)，并行執(zhí)行子進(jìn)程；

(2)各子進(jìn)程根據(jù) MCTS算法完成規(guī)定次數(shù)的迭代，產(chǎn)生根節(jié)點(diǎn)下所有合法行動(dòng)的勝率估值，得到該子進(jìn)程下的勝率估值向量，并將其發(fā)送給主進(jìn)程;

(3)主進(jìn)程匯總各子進(jìn)程的勝率估值向量，選擇獲勝概率最大的行動(dòng)，并以此為依據(jù)，做出決策行動(dòng)；

(4)待對(duì)方智能體決策執(zhí)行后，再重復(fù)進(jìn)行步驟(2)操作,直到博弈終止。

本文提出的蒙特卡洛樹并行搜索算法的典型特征是當(dāng)各子進(jìn)程得到各自根狀態(tài)下的所有行動(dòng)的勝率估值，并將該子進(jìn)程的勝率估值向量傳遞給主進(jìn)程后，主進(jìn)程采用式(1)匯總所有子進(jìn)程的勝率估值向量。

(1)

其中,X表示匯總的勝率估值向量;n表示劃分的子進(jìn)程數(shù)量;wi表示第i個(gè)子進(jìn)程所占比重，在本文中每個(gè)子進(jìn)程分配的迭代次數(shù)相同，所以假設(shè)每個(gè)子進(jìn)程對(duì)應(yīng)的貢獻(xiàn)度相同，即wi=1/n;xi表示第i個(gè)子進(jìn)程計(jì)算所得的勝率估值向量。智能體依據(jù)匯總的勝率估值向量X選取對(duì)當(dāng)前局面最有利的決策行動(dòng)。

Figure 4 Flow chart of multi-process game search

3.2 并行蒙特卡洛樹搜索算法的實(shí)現(xiàn)

本文提出的蒙特卡洛樹并行搜索算法流程如算法1所示。

算法1并行MCTS算法

輸入：當(dāng)前游戲狀態(tài)(非游戲終態(tài))。

輸出：基于當(dāng)前游戲狀態(tài)做出的決策行動(dòng)。

步驟1構(gòu)建多個(gè)子進(jìn)程進(jìn)行搜索:

每個(gè)進(jìn)程均以當(dāng)前游戲狀態(tài)作為根節(jié)點(diǎn)，獨(dú)立并行執(zhí)行步驟2～步驟7。

步驟2判斷子進(jìn)程博弈模擬局?jǐn)?shù)是否達(dá)到要求：

if滿足條件

執(zhí)行步驟8,輸出決策行動(dòng)；

else

執(zhí)行步驟3；

步驟3判斷當(dāng)前游戲狀態(tài)是否符合終止?fàn)顟B(tài)：

if符合

執(zhí)行步驟7；

else

執(zhí)行步驟4；

步驟4選擇節(jié)點(diǎn)：

if當(dāng)前狀態(tài)在博弈樹中不存在

執(zhí)行步驟5，拓展當(dāng)前游戲狀態(tài)；

else

執(zhí)行步驟6，選擇最佳的子節(jié)點(diǎn);

記錄節(jié)點(diǎn)狀態(tài)、action和環(huán)境reward;

步驟5拓展節(jié)點(diǎn):

將當(dāng)前狀態(tài)添加到博弈樹中，同時(shí)初始化當(dāng)前狀態(tài)下的所有動(dòng)作節(jié)點(diǎn)所對(duì)應(yīng)的游戲狀態(tài)，執(zhí)行步驟4。

步驟6狀態(tài)更新：

按照式(2)計(jì)算每個(gè)節(jié)點(diǎn)的value值，選擇值最大的節(jié)點(diǎn)的狀態(tài)并將其更新為當(dāng)前游戲狀態(tài):

(2)

假設(shè)智能體進(jìn)行決策時(shí)共有m種行動(dòng)可供選擇，即當(dāng)前節(jié)點(diǎn)有m個(gè)子節(jié)點(diǎn)，第j個(gè)節(jié)點(diǎn)具有參數(shù)yj，cj(j∈[1,m]),cj表示到該次模擬為止第j個(gè)節(jié)點(diǎn)被選中的次數(shù)，yj表示第j個(gè)節(jié)點(diǎn)在cj次的模擬中模擬獲勝的次數(shù)。yj/cj表示第j個(gè)節(jié)點(diǎn)的勝率。

步驟7獎(jiǎng)勵(lì)回溯:

根據(jù)步驟3記錄的節(jié)點(diǎn)、action和環(huán)境reward，反向更新沿途節(jié)點(diǎn)reward和訪問(wèn)次數(shù)。完善博弈樹構(gòu)建;

游戲狀態(tài)回到當(dāng)前狀態(tài)，執(zhí)行步驟2。

步驟8勝率估值向量合并：

根據(jù)式(1)合并各子進(jìn)程根節(jié)點(diǎn)下的勝率估值向量，根據(jù)式(2)計(jì)算當(dāng)前狀態(tài)根節(jié)點(diǎn)下適合的決策行動(dòng)。

步驟9輸出基于當(dāng)前游戲狀態(tài)作出的決策行動(dòng)。

將待決策的當(dāng)前游戲局面作為根節(jié)點(diǎn)，子進(jìn)程并行進(jìn)行蒙特卡洛樹搜索，得到子進(jìn)程勝率估值，由主進(jìn)程進(jìn)行合并得到最終的勝率估值向量，算法根據(jù)勝率估值向量，選取決策行動(dòng)。

4 模型測(cè)試與數(shù)據(jù)分析

4.1 非零和多智能體博弈平臺(tái)-Pommerman簡(jiǎn)介

Pommerman游戲界面如圖5所示，每局游戲有4個(gè)智能體，每個(gè)智能體以網(wǎng)格4角為起始位置。每個(gè)智能體的目標(biāo)就是存活到最后，通過(guò)炸彈的放置以及躲避炸彈等博弈策略來(lái)淘汰敵人，保全自己。在Pommerman競(jìng)賽中，智能體只能做出如表1所示的行動(dòng)之一，不能做出其他多余動(dòng)作。

Figure 5 Game interface of Pommerman

Table 1 Legal actions of agent in Pommerman

另外，競(jìng)賽中還存在不同的競(jìng)爭(zhēng)模式，在團(tuán)隊(duì)模式(2V2)中，當(dāng)一個(gè)團(tuán)隊(duì)的2個(gè)智能體都被摧毀時(shí)，游戲結(jié)束，獲勝隊(duì)伍為幸存智能體所在隊(duì)伍；在4個(gè)智能體的單人模式(FFA)和2個(gè)智能體的單人模式(1V1)中，最多只有1個(gè)智能體存活時(shí)游戲結(jié)束，幸存者即為獲勝者。

4.2 實(shí)驗(yàn)環(huán)境

本文的軟件與硬件實(shí)驗(yàn)環(huán)境分別如表2和表3所示。本文基于表2和表3的實(shí)驗(yàn)環(huán)境，進(jìn)行對(duì)比實(shí)驗(yàn)的設(shè)計(jì)與實(shí)現(xiàn)，所有的實(shí)驗(yàn)都是基于相同的運(yùn)行時(shí)間(24 h)采用不同搜索算法的智能體進(jìn)行博弈，測(cè)試博弈性能并進(jìn)行數(shù)據(jù)分析。

Table 2 Experimental environment(software conditions)

Table 3 Experimental environment(hardware conditions)

4.3 測(cè)試指標(biāo)

在對(duì)蒙特卡洛樹搜索算法進(jìn)行測(cè)試之前，為了方便對(duì)比并分析并行版本與串行版本的蒙特卡洛樹搜索算法的性能，本文使用以下2個(gè)測(cè)試指標(biāo)進(jìn)行性能分析:

(1)對(duì)局耗時(shí)：即在相同的MCTS迭代次數(shù)之下，測(cè)試不同并行進(jìn)程蒙特卡洛樹搜索算法的平均每局耗時(shí)，即對(duì)同一個(gè)任務(wù)需要消耗的時(shí)間的對(duì)比。平均對(duì)局耗時(shí)可以反映不同進(jìn)程的蒙特卡洛樹搜索算法在搜索過(guò)程中的耗時(shí)情況。

(2)對(duì)弈勝率：對(duì)弈勝率用于度量搜索算法的性能，即智能體使用不同版本的博弈算法進(jìn)行對(duì)弈，記錄使用本文設(shè)計(jì)的優(yōu)化算法的智能體獲勝的概率。在本文中不同版本的博弈算法對(duì)弈的設(shè)計(jì)如表4所示。將不同版本的博弈算法運(yùn)用至不同的博弈模型(FFA,2V2和1V1)，分析博弈效果。

Table 4 Comparative experiment design

4.4 性能分析

為了有效對(duì)比分析不同版本蒙特卡洛樹搜索算法的性能，實(shí)驗(yàn)設(shè)置中串行版本和并行版本的MCTS迭代次數(shù)均設(shè)置為400，并且為了使并行版本的MCTS迭代平均分布到不同子進(jìn)程中，并行版本設(shè)置的子進(jìn)程數(shù)量分別為2,4和8。這樣能夠在充分利用有限計(jì)算機(jī)資源的同時(shí)，均衡實(shí)現(xiàn)子進(jìn)程的MCTS搜索。

4.4.1 對(duì)局耗時(shí)

本次實(shí)驗(yàn)的實(shí)驗(yàn)對(duì)象是表4中的實(shí)驗(yàn)1、實(shí)驗(yàn)2和實(shí)驗(yàn)4、實(shí)驗(yàn)5，串行MCTS與并行MCTS分別運(yùn)行相同的時(shí)間(24 h)。記錄實(shí)驗(yàn)1、實(shí)驗(yàn)2和實(shí)驗(yàn)4、實(shí)驗(yàn)5完成的對(duì)弈局?jǐn)?shù)，F(xiàn)FA模式和2V2模式的結(jié)果如圖6和圖7所示。

Figure 6 Number of games(FFA)

Figure 7 Number of games(2V2)

通過(guò)圖6和圖7固定時(shí)間博弈局?jǐn)?shù)的數(shù)據(jù)分析本文設(shè)計(jì)的算法的耗時(shí)。在FFA模式下，子進(jìn)程數(shù)量為2的情況下，對(duì)局完成的時(shí)間約為串行完成時(shí)間的40%。2V2模式下，子進(jìn)程數(shù)量為2的情況下，對(duì)局完成的時(shí)間約為串行完成時(shí)間的25%。這驗(yàn)證了本文設(shè)計(jì)的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法可以有效縮減博弈樹的搜索時(shí)間。

4.4.2 對(duì)弈勝率

由4.4.1節(jié)的數(shù)據(jù)分析可以得到,在FFA模式下，本文設(shè)計(jì)的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法會(huì)將搜索時(shí)間大約縮短為原來(lái)的1/n(n為并行的子進(jìn)程數(shù)量)，在大幅縮短搜索時(shí)間的同時(shí)也降低了勝率。為了探索勝率不變的情況下，搜索時(shí)間最多能夠縮短多長(zhǎng)時(shí)間，本節(jié)實(shí)驗(yàn)選取了迭代次數(shù)不同的串行智能體與并行智能體進(jìn)行對(duì)抗。

本節(jié)按照表4中實(shí)驗(yàn)3的配置進(jìn)行設(shè)計(jì)，在博弈局?jǐn)?shù)相同的情況下，不同迭代次數(shù)的串行MCTS與不同子進(jìn)程下并行MCTS智能體進(jìn)行對(duì)弈，實(shí)驗(yàn)結(jié)果如圖8所示。本文將子進(jìn)程數(shù)為2、迭代次數(shù)為200的并行MCTS與迭代次數(shù)為150的串行MCTS進(jìn)行對(duì)弈。統(tǒng)計(jì)結(jié)果如表5所示，數(shù)據(jù)變化曲線如圖8所示。通過(guò)圖8可以得出，隨著博弈局?jǐn)?shù)的增加，并行MCTS勝率在數(shù)據(jù)0.5上下波動(dòng)，并行智能體與串行智能體的博弈能力不相上下，兩者對(duì)弈勝率相近。

Figure 8 Winning rate of parallel MCTS agents vs serial MCTS agents when playing chess

本文對(duì)表5和圖8的數(shù)據(jù)分析，驗(yàn)證了本文設(shè)計(jì)的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法的有效性?；诒?中實(shí)驗(yàn)3的實(shí)驗(yàn)配置，本文設(shè)計(jì)的并行MCTS算法在有效縮短約20%搜索時(shí)間的情況下，與串行MCTS智能體對(duì)抗獲勝的勝率約為50%。進(jìn)一步驗(yàn)證了在有效縮短搜索時(shí)間的情況下，本文設(shè)計(jì)的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法未對(duì)博弈性能造成影響。

Table 5 Parallel MCTS vs serial MCTS

本文通過(guò)對(duì)弈耗時(shí)與對(duì)弈勝率2個(gè)指標(biāo)值的分析，驗(yàn)證了本文設(shè)計(jì)的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法是可行且有效的，提高了MCTS中博弈樹的搜索效率。

5 結(jié)束語(yǔ)

基于Pommerman博弈平臺(tái)，本文在蒙特卡洛樹搜索算法的并行優(yōu)化的理論基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了基于勝率估值傳遞的并行蒙特卡洛樹搜索算法，并給出了算法的詳細(xì)步驟。本文通過(guò)一系列的對(duì)比實(shí)驗(yàn)來(lái)對(duì)優(yōu)化的并行蒙特卡洛樹搜索算法進(jìn)行測(cè)試并評(píng)估其性能，實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法在與原有博弈算法保持相同博弈勝率的情況下，能夠至少縮短20%的搜索時(shí)間。

未來(lái)的研究重點(diǎn)將集中于嘗試將蒙特卡洛樹搜索與深度強(qiáng)化學(xué)習(xí)策略相結(jié)合，例如葉子節(jié)點(diǎn)第1次展開時(shí)可以用策略網(wǎng)絡(luò)獲得先驗(yàn)評(píng)分；探索一種CPU與GPU異步工作的方案，在提高算法在博弈樹中搜索效率的同時(shí)，更加充分地調(diào)用計(jì)算資源，避免GPU資源的浪費(fèi)。