並行蒙卡樹搜索，性能無損，線性加速，勇闖「消消樂」1000關！

• 2020 年 2 月 24 日
• 筆記

作者 | 快手

責編 | 賈偉

AAAI 2020 已經於 2月 7日 – 12 日在紐約舉辦，對於 AI 領域的研究者來講，接下來最近的一個盛會將是4月26日在非洲埃塞俄比亞（亞斯亞貝巴）舉辦的 ICLR 2020。

ICLR會議是由深度學習三巨頭之二的 Yoshua Bengio 和 Yann LeCun 牽頭於2013年創辦，旨在關注有關深度學習各個方面的前沿研究。儘管ICLR 2020也不過是第九屆會議，但這個會議卻已經成為業界人士心目中的頂級會議。特別是在前段時間清華發佈的新版AI頂會評級中，ICLR更是被評為A級會議。

本屆ICLR 會議共有 2594篇投稿，其中 687篇論文被接收（48篇oral論文，107篇spotlight論文和531篇poster論文），接收率為26.5%。本文為 快手 實習生劉安吉完成並發表在ICLR 2020上的 Oral 論文，該論文在OpenReview網站上的評分為 8-6-8。

作者對文章的簡介為：我們開發了一種有效的並行UCT算法，該算法在線性加速的同時，性能損失很小。

We developed an effective parallel UCT algorithm that achieves linear speedup and suffers negligible performance loss.

論文鏈接：https://openreview.net/forum?id=BJlQtJSKDB

蒙特卡洛搜索樹（Monte Carlo Tree Search，MCTS）是一種基於模型的強化學習算法（model-based reinforcement learning algorithm）。利用已知或訓練出來的環境模型，MCTS將最優優先搜索樹和蒙特卡洛方法結合，通過大量在環境模型中進行嘗試、規劃（planning），找到更優的策略。MCTS在視頻遊戲、圍棋等領域取得了驚人的突破（如大家熟知的AlphaGo）。

與其出眾的表現相對應，MCTS對計算資源的需求十分巨大。這主要體現在其需要與環境進行大量的交互。AlphaGo在與人類棋手對弈時就使用了大量計算資源，否則它無法在給定的時間內完成落子。因此，並行MCTS就顯得十分必要，尤其在對反饋時間要求較高的任務場景中。

然而，蒙特卡洛搜索樹本身是一個串行的算法（每一步迭代需要所有當前已知信息），這導致對其並行將帶來不可避免的性能損失。因此，如何最小化並行帶來的性能損失就顯得十分重要。

如上圖(a)所示，MCTS在不斷地重複選擇（selection）、擴展（expansion）、仿真（simulation）、反向傳播（backpropagation）的過程。其中「選擇」步驟通過搜索樹選擇一個節點（對應環境中的一個狀態state），「擴展」為搜索樹增加一個節點，「仿真」通過環境模型對此節點的回報進行估計，「反向傳播」更新得到的回報估計值。

具體而言，在「選擇」步驟中，我們通過下式不斷選擇最優孩子節點：

其中 V_s 是節點 s 的回報平均估值，N_s 是節點 s 的訪問次數，C(s) 是 s 的所有孩子節點的集合。

並行 MCTS 的難點可以通過上圖中 (b)-(c) 展示。因為有多個 worker 在同時執行上述選擇->擴展->仿真->反向傳播過程，某一個 worker 在進行「選擇」的時候，其他 worker 未結束的仿真結果是無法獲取的，這導致大量 worker 只能看到過時且類似的信息，嚴重影響了搜索樹選擇節點的好壞，破壞了串行狀態下的探索-利用平衡（exploration-exploitation balance）。

為解決這一問題，我們提出了 WU-UCT 算法（Watch the Unobserved in UCT）。這個算法借用了異步並行算法的思想 [2]。WU-UCT 算法的核心在於維護一個額外的統計量用於記錄每個節點上有多少個正在對其進行仿真的 worker，並用其對選擇算法進行調整：

其中 O_s 是如上所述節點 s 的未返回訪問次數統計（unobserved samples）。

此外，根據上面的核心想法，為最大化算法的效率，我們設計了一個並行 MCTS 系統 (a)。我們使用了主-從工作模式的系統。由主進程維護一個完整的搜索樹，並進行選擇（selection）和反向傳播（backpropagation）操作。同時，主進程負責將擴展（expansion）和仿真（simulation）的任務分配給對應的子進程，由子進程完成後將結果返還主進程。這樣做的好處在於很好地保證了統計信息對於每次選擇都是完整的，同時避免了進程間共享內存和訪問衝突等問題。

這一系統在 Atari 遊戲和快手「點消快樂城」遊戲中進行了測試，發現其加速比能很好地保持線性。

在標準測試環境 Atari 下，WU-UCT 在相同 worker 數和總仿真次數的情況下，在 13/15 個遊戲中取得了最好的表現。

此外，隨着仿真 worker 數的增大，WU-UCT 基本達到了線性加速比，且其性能損失明顯小於對比算法。

最後，WU-UCT 算法已被用於對快手自研的「點消快樂城」遊戲進行自動關卡難度測試，並達到了 8.6% 預測誤差（Mean Absolute Error，MAE）的表現。

具體而言，我們通過 AI 取代傳統人工測試，對大量關卡（超過 1000 關）進行自動難度驗證。在 WU-UCT 的幫助下，我們的系統可以準確地預測某一關卡上線後玩家的預期通關率，為關卡設計師提供了很好的指導，達到了不需要人工測試即可得到反饋。此外，我們的測試系統準確率比人工更高，在大幅提高了遊戲設計效率的同時，大幅降低了開發成本，也改變遊戲製作方式。

感謝

該工作是實習生劉安吉在快手遊戲中台和 YTech 的遊戲 AI 聯合實驗室完成。同時感謝騰訊 AI Lab 的陳建樹老師對論文的深入參與和建設性的意見。

[1] Anji Liu, Jianshu Chen, Mingze Yu, Yu Zhai, Xuewen Zhou, and Ji Liu,「Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search,」ICLR 2020 (oral 2%) (url: https://openreview.net/forum?id=BJlQtJSKDB)

[2] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu,「Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization,」NIPS 2015 (spotlight 4%)

（url: https://arxiv.org/abs/1506.08272）