專訪AAAI 2018最佳論文作者，記憶增強蒙特卡洛樹搜索細節解讀

AAAI 2018 大會已於 2 月 2 日在美國新奧爾良開幕。在此之前，大會獲獎論文的結果已經放出，阿爾伯塔大學提交的論文《Memory-Augmented Monte Carlo Tree Search》獲得了 AAAI 2018 大會的傑出論文獎。該論文作者分別為博士生 Chenjun Xiao、梅勁騁與教授 Martin Müller。

Chenjun Xiao 碩士與博士階段均就讀於阿爾伯塔大學，師從 Martin Müller 教授。

梅勁騁本科畢業於華南理工大學，研究生赴上海交通大學，師從計算機系呂寶糧教授。2015 年起，他來到阿爾伯塔大學攻讀博士，導師為 Dale Schuurmans 教授。

該論文的導師，阿爾伯塔大學教授 Martin Müller 則因計算機圍棋而聞名於世。Müller 教授所帶領的團隊在博弈樹搜索和規劃的蒙特卡洛方法、大規模並行搜索和組合博弈論方面頗有建樹。圍棋程序 AlphaGo 的設計研發主導人物 David Silver 和黃士傑（Aja Huang）（他們分別是 AlphaGo Nature 論文的第一作者和第二作者，也名列於最近的 AlphaGo Zero 論文中）都來自於 Müller 門下。

這篇論文提出了記憶增強的蒙特卡洛樹搜索（M-MCTS）方法，M-MCTS 的核心思想是將 MCTS 結合一種記憶結構，其中每一項記錄包含一個特定狀態的信息。通過結合相似狀態的估計，這些記憶被用於生成一個近似值估計。研究人員在圍棋中評估了 M-MCTS，實驗結果表明 M-MCTS 的性能優於原始蒙特卡洛方法。

在得知獲獎信息後，機器之心第一時間聯繫到了 Martin Müller 教授，並對論文的三位作者共同對論文中的內容、未來研究方向以及一些感興趣的問題進行了交流。

對於論文的兩名中國作者而言，得知獲獎後的第一反應是驚訝和幸運。不過，在國際人工智慧重要會議的最佳論文獎項上，中國人名字的出現早已成為常態，華人正在 AI 領域扮演著越來越重要的角色。阿爾伯塔大學裡，Martin Müller 教授帶領的博士生中有很多來自國內。「在阿爾伯塔大學，我們幸運地擁有很多世界級的學生前來攻讀學位。」Müller 介紹道，「經我指導已經畢業的中國博士包括 Fan Xie（現為谷歌軟體工程師），正在帶的博士生有 Gaojian Fan、Chao Gao 和 Chenjun Xiao。他們都是在中國接受本科或研究生教育之後來到阿爾伯塔的，他們在理論背景上訓練有素，同時也具備相關領域工作的實踐經驗。」

作為阿爾伯塔大學的博士生，Chenjun Xiao 等人可以說和 David Silver 和黃士傑師出同門。他們也對 DeepMind 最新的 AlphaGo Zero 發表了一番看法。

「這是我們目前已知的最佳啟發式方法了。」Chenjun Xiao 說道。

Martin Müller 教授則認為 AlphaGo Zero 還未到達演算法的極限：「但它仍然是一個啟發式方法，非常強大，但並不完美……」

梅勁騁也指出了 AlphaGo 目前存在的限制：「當狀態、模型和轉換是完美已知的時候，這種方法才能展現能力。」

隨著人工智慧技術逐漸走向實用化，越來越多的科技巨頭開始參與其中，業界的學術影響力也在日益提升。在 ICLR 2018 的論文中，來自谷歌的被接收論文數量高達四十餘篇，是第二名 UC Berkeley 的四倍之多。目前大學中的人工智慧研究或許正因為計算資源的不足而逐漸落後於科技巨頭。但 Martin Müller 認為，在大學環境中，學者們仍然可以進行有意義的研究。最佳論文也對這種觀點給出了有力的證明。

在圍棋之外，阿爾伯塔大學的研究者們也把蒙特卡洛方法應用在了六貫棋上（Hex，一種在六邊形格棋盤上進行的桌游），Martin Müller 博士生 Chao Gao 和 Ryan Hayward 教授正在共同研究這一方向。此外，研究人員們已經在把眼光投向了更為複雜的強化學習任務，如即時戰略遊戲上。

深度學習作為近期人工智慧發展的標誌性技術，引出了無數的新方法和新應用，卻也因為使用場景受限而遭到越來越多人的詬病。近日，Gary Marcus、Yann LeCun 等人對深度學習的局限性展開了很多探討。Martin Müller 也對此表達了自己的態度：「深度學習對於學習非常複雜的函數而言非常有用，但搜索會始終在這一過程中扮演重要的角色。搜索永遠不會被「純粹的知識」取代。AlphaGo Zero 就是最好的例子，神經網路加上搜索的 Elo 得分超過了單獨的神經網路高達 2000 分！這是一個非常大的差距，隨著機器獲取的知識越來越多，這個差距只會越來越大。」

AlphaGo Zero 的論文中指出，未使用蒙特卡洛樹搜索的網路（Raw Network）其 Elo 評分低於完整的 AlphaGo Zero 達 2000 分之多。

因當時最佳論文還未公開，在文章《學界 | AAAI 2018 獲獎論文提前揭曉：兩大獎項花落阿爾伯塔、牛津》中我們無法介紹更多技術細節。如今，該論文已經放出，機器之心編譯介紹如下：

蒙特卡洛樹搜索（MCTS）的核心思想是構建一個搜索樹，且搜索樹的狀態由快速蒙特卡洛模擬（Coulom 2006）評估。若從給定博弈狀態開始，並通過隨機 Self-play 在觀察到最終結果前模擬成千上萬次博弈，然後我們就可以將模擬的平均輸出作為狀態值的估計。同時，MCTS 在模擬中會維護一個搜索樹，因而藉助它指導模擬的方向，其中我們可以使用老虎機演算法（bandit algorithm）來權衡利用（exploitation）和探索（exploration）（Kocsis and Szepesvari 2006）。然而，MCTS 不能有效保證「大型狀態空間」的價值估計準確度，因為在相對有限的搜索時間內，狀態的平均值作為估計會有較高的方差。因此，不準確的估計會誤導搜索樹的構建，並嚴重降低程序的性能。

最近，已經有學者提出幾種機器學習方法來克服 MCTS 的這種缺點。例如深度神經網路可以用來學習領域知識和逼近狀態值的函數。這些方法和與 MCTS 相結合可以提供啟發式的方法以提高搜索樣本的效率（Silver et al. 2016; Tian and Zhu 2015）。

機器學習方法的成功可以很大程度上歸因於模型的泛化性能，即類似的狀態共享相似的信息。泛化空間的領域知識一般由函數近似表徵，例如深度網路通過一般數據集或自生成的模擬數據集來離線訓練（Silver et al. 2016）。

與從離線學習過程中探索泛化的研究相比，在線實時搜索並沒有過多關注利用泛化的優勢。本論文提出和評估了一種增強記憶的 MCTS 演算法，它提供了一種利用在線泛化優勢的替代型方法。我們設計了一種記憶，其中每個元素（entry）都包含特定狀態的信息，並可作為構建在線值近似的基礎。我們利用圍棋的實驗證明這種基於記憶的框架對於提升 MCTS 的性能十分有效，不論是在理論還是實踐中。

論文：Memory-Augmented Monte Carlo Tree Search

論文鏈接：https://webdocs.cs.ualberta.ca/~mmueller/ps/2018/Chenjun-Xiao-M-MCTS-aaai18-final.pdf

摘要：我們在本文中提出記憶增強的蒙特卡洛樹搜索（Memory-Augmented Monte Carlo Tree Search，M-MCTS）並對其進行了評估，提供了利用在線實時搜索的泛化能力的新方法。M-MCTS 的核心思想是將 MCTS 結合一種記憶結構，其中每一項記錄包含一個特定狀態的信息。通過結合相似狀態的估計，這些記憶被用於生成一個近似值估計。我們在本文中表明基於記憶的值逼近在溫和條件下高概率地優於原始的蒙特卡洛評估方法。我們在圍棋中評估了 M-MCTS。實驗結果表明 M-MCTS 在相同的模擬次數下優於原始的 MCTS。

蒙特卡洛樹搜索

MCTS 構建樹以評估狀態並進行快速模擬（Coulom 2006）。樹中的每個節點對應一個具體的狀態 s∈S，並包含模擬統計 V (s) hat 和 N(s)。在演算法的每一次迭代中，一個模擬從一個初始狀態 s_0 狀態開始，之後進入兩個階段： in-tree 和 rollout。在當前的搜索樹表徵了狀態 s_t 時，會應用樹策略選擇一個動作，以達到下一個狀態。樹策略的最常用選擇是使用老虎機演算法，例如 UCB1（Kocsis and Szepesvari 2006）。對於樹之外的策略，樹將應用 roll-out 策略模擬一場博弈直到結束，其中被訪問的狀態的軌跡為 T = {s_0, s_1, . . . , s_T }，並在最後獲得返回值 R。樹中的 s∈T 的統計根據下式進行更新：

此外，樹也同時在生長。在最簡單的方案中，第一個被訪問的尚未在樹中的節點會被添加到樹上。

MCTS 結合記憶

我們現在介紹記憶增強 MCTS（M-MCTS）演算法。圖（1）提供了簡要的圖示。M-MCTS 和常規的 MCTS 的主要區別在於，M-MCTS 搜索樹的每一個節點都會存儲統計的一個擴展集合：

這裡，N_M 是近似記憶值 V_M(s) hat 的估計次數。在 MCTS 的 in-tree 樹搜索期間，我們使用

取代 V(s) hat 作為狀態 s 的值，用於 in-tree 選擇，例如在 UCB 公式中。λ_s 是一個延遲參數，確保不存在非對稱的偏差。

圖 1：M-MCTS 的簡要圖示。當搜索到一個葉狀態時，會生成一個特徵表徵φ（s），然後其被用於詢問（query）基於記憶的值近似 V_M(s) hat。V_M(s) hat 被用於根據下式更新 s 和 s 的所有過去狀態，如圖中的紅色箭頭所示。

我們在圍棋遊戲中評估了 M-MCTS，我們的基線結果是基於開源的圍棋程序 Fuego（Enzenberger and Muller 2008 2017），但是添加了 DCNN 以提升性能。下圖展示了實驗結果：

圖 2：(a)-(c) 展示了測試 M 的不同值的結果。(d) 展示了測試不同記憶規模的結果。在所有的圖中，x 軸是每次落子（s 到達下一個狀態）的模擬數量，y 軸是與基線方法博弈的勝率。

我們每次落子從 {1000, 5000, 10000} 使用不同的模擬次數，實驗結果展示在上圖 2(a)-(c) 中。在我們使用設定 {M = 50, τ = 0.1} 時獲得了最好的結果，它以每次落子進行 10000 次模擬對抗基線演算法並實現了 71% 的勝率。此外，我們也探索了不同記憶大小 {1000, 5000, 10000} 的影響。M 和 τ 分別設置為 50 和 0.1，實驗結果在上圖的 2(d) 中展示。直觀上，我們會認為較大的記憶會有更好的性能，因為 query 會包含更多的候選狀態，以上的實驗結果也證明了這一點。

結論和未來工作

在本論文中，我們提出了一個有效的方法來利用實時搜索的在線泛化。我們的方法，記憶增強的蒙特卡洛樹搜索（M-MCTS），將原始的 MCTS 演算法與存儲框架相結合，來提供基於存儲的在線數值近似。未來，我們計劃探索以下兩個方向。首先，我們想探索是否可以通過結合離線學習的數值近似來讓我們的在線存儲框架獲得更好的泛化性能；其次，讓 M-MCTS 的特徵表示重用一個神經網路來預測下一步。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！