面向多智能體博弈的并行蒙特卡洛樹搜索算法研究*

管延霞,劉遜韻,劉運韜,謝 旻，徐新海

(1.國防科技大學計算機學院，湖南 長沙 410073；2.軍事科學院戰爭研究院，北京 100091)

1 引言

計算機博弈是衡量人工智能發展水平的重要測試平臺之一[1]，已在象棋、圍棋等棋類博弈的決策問題上取得了優異的成果[2,3]。計算機博弈目前的研究重點在于多智能體博弈。

多智能體會導致博弈過程中的動態空間和狀態空間呈指數級增長，使得決策的搜索和選擇過程需要消耗一定的時間和計算資源[4]。計算機資源的并行協作可以有效降低多智能體博弈中的維度災難等問題。但是，該方法的主要難點在于如何有效利用計算資源并行加速搜索過程，以及如何實現信息的有效傳遞。

本文選取Pommerman[5]作為研究平臺，針對多智能體博弈問題中的蒙特卡洛樹搜索算法展開研究。Pommerman是一種通過放置炸彈來淘汰敵人的多智能體博弈環境。博弈過程中的搜索算法優化是博弈性能提升的關鍵，針對原有蒙特卡洛樹搜索算法搜索耗時過長的問題，本文借鑒蒙特卡洛樹搜索常用的并行方法，對博弈中的搜索階段進行并行優化，旨在充分利用有限的計算機資源，縮短搜索算法收斂到近似最優決策策略的學習時間。本文具體工作如下所示：

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

(2)將構建的并行算法應用于Pommerman的不同游戲模式，并分別與對應的原始搜索算法進行了性能對比，定量分析了本文算法的優勢。

2 蒙特卡洛樹搜索算法并行優化現狀

Pommerman博弈平臺采用蒙特卡洛樹搜索MCTS(Monte Carlo Tree Search)算法[6-9]做出博弈策略，該搜索算法將蒙特卡洛算法應用于博弈樹搜索過程中。圍棋中的AlphaGo[2,3]即是以MCTS算法為基礎進行研發的。

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

Figure 1 Mainstream parallelization methods of Monte Carlo tree search algorithm

在對MCTS進行并行優化設計時，不僅要考慮如何跟蹤得到正確的統計數據，還要盡量減少進程之間的通信開銷。

MCTS算法依賴當前游戲狀態之前的采樣信息[15]來保持未知領域的探索和已有經驗的利用之間的平衡。當使用多個工作程序并行化蒙特卡洛樹搜索算法部署時，要確保每個工作程序都能獲得最新的統計信息。在并行化過程中，本文想要盡可能實現如圖2a所示的理想并行化，減少如圖2b所示真實并行化可能會出現的進程沖突等問題。

Figure 2 Parallelization of Monte Carlo tree search algorithm

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

3.1 算法設計

基于多個進程根節點回報值匯總的思想，本文提出了一種基于勝率估值傳遞的并行蒙特卡洛樹搜索算法。算法借鑒Root Parallelization[7]的思路，如圖3所示，在進行MCTS搜索之前主進程將當前的游戲狀態及游戲策略傳遞給各子進程，并將探索任務平均分配到各子進程中，使多個子進程基于同一個根節點狀態獨立并行執行搜索過程。每個子進程完成探索任務后，將回報信息傳遞給主進程，主進程依據最終的匯總信息進行決策并更新搜索策略。主進程將更新后的信息再次傳遞給子進程，循環反復直至游戲狀態滿足結束條件。

Figure 3 Parallelization of search process

只在進程的開始和結束時進行算法進程之間的信息交互，以最小化子進程之間的信息交互。相比于采用樹并行化實現的Ary[16]來說減少了進程交互；相比于葉并行化的實現，避免了節點頻繁加解鎖；相較于根并行化的實現，本文設計的算法各子進程的搜索耗時相當，減少了子進程信息收集的等待時差。本文設計的算法能夠有效利用計算資源，縮短搜索時間，提高MCTS的搜索效率。

圖4給出了實現并行化的搜索過程，主要分為4步：

(1)游戲開局，參數初始化，主進程給子進程分配任務，并行執行子進程；

(2)各子進程根據 MCTS算法完成規定次數的迭代，產生根節點下所有合法行動的勝率估值，得到該子進程下的勝率估值向量，并將其發送給主進程;

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

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

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

(1)

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

Figure 4 Flow chart of multi-process game search

3.2 并行蒙特卡洛樹搜索算法的實現

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

算法1并行MCTS算法

輸入：當前游戲狀態(非游戲終態)。

輸出：基于當前游戲狀態做出的決策行動。

步驟1構建多個子進程進行搜索:

每個進程均以當前游戲狀態作為根節點，獨立并行執行步驟2～步驟7。

步驟2判斷子進程博弈模擬局數是否達到要求：

if滿足條件

執行步驟8,輸出決策行動；

else

執行步驟3；

步驟3判斷當前游戲狀態是否符合終止狀態：

if符合

執行步驟7；

else

執行步驟4；

步驟4選擇節點：

if當前狀態在博弈樹中不存在

執行步驟5，拓展當前游戲狀態；

else

執行步驟6，選擇最佳的子節點;

記錄節點狀態、action和環境reward;

步驟5拓展節點:

將當前狀態添加到博弈樹中，同時初始化當前狀態下的所有動作節點所對應的游戲狀態，執行步驟4。

步驟6狀態更新：

按照式(2)計算每個節點的value值，選擇值最大的節點的狀態并將其更新為當前游戲狀態:

(2)

假設智能體進行決策時共有m種行動可供選擇，即當前節點有m個子節點，第j個節點具有參數yj，cj(j∈[1,m]),cj表示到該次模擬為止第j個節點被選中的次數，yj表示第j個節點在cj次的模擬中模擬獲勝的次數。yj/cj表示第j個節點的勝率。

步驟7獎勵回溯:

根據步驟3記錄的節點、action和環境reward，反向更新沿途節點reward和訪問次數。完善博弈樹構建;

游戲狀態回到當前狀態，執行步驟2。

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

根據式(1)合并各子進程根節點下的勝率估值向量，根據式(2)計算當前狀態根節點下適合的決策行動。

步驟9輸出基于當前游戲狀態作出的決策行動。

將待決策的當前游戲局面作為根節點，子進程并行進行蒙特卡洛樹搜索，得到子進程勝率估值，由主進程進行合并得到最終的勝率估值向量，算法根據勝率估值向量，選取決策行動。

4 模型測試與數據分析

4.1 非零和多智能體博弈平臺-Pommerman簡介

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

Figure 5 Game interface of Pommerman

Table 1 Legal actions of agent in Pommerman

另外，競賽中還存在不同的競爭模式，在團隊模式(2V2)中，當一個團隊的2個智能體都被摧毀時，游戲結束，獲勝隊伍為幸存智能體所在隊伍；在4個智能體的單人模式(FFA)和2個智能體的單人模式(1V1)中，最多只有1個智能體存活時游戲結束，幸存者即為獲勝者。

4.2 實驗環境

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

Table 2 Experimental environment(software conditions)

Table 3 Experimental environment(hardware conditions)

4.3 測試指標

在對蒙特卡洛樹搜索算法進行測試之前，為了方便對比并分析并行版本與串行版本的蒙特卡洛樹搜索算法的性能，本文使用以下2個測試指標進行性能分析:

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

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

Table 4 Comparative experiment design

4.4 性能分析

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

4.4.1 對局耗時

本次實驗的實驗對象是表4中的實驗1、實驗2和實驗4、實驗5，串行MCTS與并行MCTS分別運行相同的時間(24 h)。記錄實驗1、實驗2和實驗4、實驗5完成的對弈局數，FFA模式和2V2模式的結果如圖6和圖7所示。

Figure 6 Number of games(FFA)

Figure 7 Number of games(2V2)

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

4.4.2 對弈勝率

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

本節按照表4中實驗3的配置進行設計，在博弈局數相同的情況下，不同迭代次數的串行MCTS與不同子進程下并行MCTS智能體進行對弈，實驗結果如圖8所示。本文將子進程數為2、迭代次數為200的并行MCTS與迭代次數為150的串行MCTS進行對弈。統計結果如表5所示，數據變化曲線如圖8所示。通過圖8可以得出，隨著博弈局數的增加，并行MCTS勝率在數據0.5上下波動，并行智能體與串行智能體的博弈能力不相上下，兩者對弈勝率相近。

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

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

Table 5 Parallel MCTS vs serial MCTS

本文通過對弈耗時與對弈勝率2個指標值的分析，驗證了本文設計的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法是可行且有效的，提高了MCTS中博弈樹的搜索效率。

5 結束語

基于Pommerman博弈平臺，本文在蒙特卡洛樹搜索算法的并行優化的理論基礎上，設計并實現了基于勝率估值傳遞的并行蒙特卡洛樹搜索算法，并給出了算法的詳細步驟。本文通過一系列的對比實驗來對優化的并行蒙特卡洛樹搜索算法進行測試并評估其性能，實驗結果表明，本文設計的基于勝率估值傳遞的并行蒙特卡洛樹搜索算法在與原有博弈算法保持相同博弈勝率的情況下，能夠至少縮短20%的搜索時間。

未來的研究重點將集中于嘗試將蒙特卡洛樹搜索與深度強化學習策略相結合，例如葉子節點第1次展開時可以用策略網絡獲得先驗評分；探索一種CPU與GPU異步工作的方案，在提高算法在博弈樹中搜索效率的同時，更加充分地調用計算資源，避免GPU資源的浪費。