Martin Müller：深度學習時代的啟發式搜索

5 月 28 日，機器之心全球機器智能峰會（GMIS 2017）進入第二天，全天議程中最受關注的是多位重要嘉賓出席的領袖峰會，包括《人工智慧：一種現代方法》的作者 Stuart Russell、第四範式聯合創始人兼首席科學家楊強、科大訊飛執行總裁兼消費者事業群總裁胡郁、阿爾伯塔大學教授及計算機圍棋頂級專家 Martin Müller、Element AI 聯合創始人 Jean-Sebastien Cournoyer 等。

下午，大會迎來又一位引人關注的學者。阿爾伯塔大學計算機科學教授，計算機圍棋專家 Martin Müller 發表了主題為《深度學習時代的啟發式搜索》的演講。昨天，AlphaGo 與柯潔的系列比賽剛剛結束，而此前大會其他嘉賓在演講中也紛紛提到了這場比賽。Martin 作為 AlphaGo 開發者們的導師，對計算機圍棋及其背後的技術進行了深度解讀。

作為計算機圍棋研究的先驅，Martin Müller 教授所帶領的團隊在博弈樹搜索和規劃的蒙特卡洛方法、大規模並行搜索和組合博弈論方面頗有建樹。在此前 AlphaGo 與柯潔烏鎮人機交鋒的比賽期間，機器之心曾與他共同觀戰。圍棋程序 AlphaGo 的設計研發的 David Silver 和黃士傑（Aja Huang）（分別是 DeepMind AlphaGo 發表在 Nature 上的論文的兩位並列第一作者）都曾師從於他。

「啟發式搜索不是搜索引擎式的搜索，」Martin 說道。「在真實情況下，由於可能性過多，很多時候你是不能搜索全部信息的。在圍棋中，這種情況尤為突出。」

多年來，人工智慧研究者們一直以攻克各類遊戲為目標，因為這些任務規則簡單，可以為真實世界的應用鋪平道路。人工智慧研究者們不僅在國際象棋上，也在跳棋、雙陸棋等棋盤遊戲中有過很多研究。在圍棋之前，人工智慧領域的一個里程碑事件是 IBM 的「深藍」擊敗世界國際象棋冠軍卡斯帕羅夫（剛剛過去 20 周年）。在 20 年前，IBM 的系統已經使用了深度搜索與並行計算，大大提升了效率。

在棋類遊戲中，最引人注目的自然是被認為最具複雜性的圍棋了。深度學習是近幾年來科技界火熱的話題，但它並不是人工智慧的全部。「如果你只關注深度學習，那你就會錯過很多東西，」Martin 說道。

AlphaGo 的學習過程是線下的。它通常是先發展出若干神經網路以待比賽中使用。蒙特卡洛樹搜索（MCTS）是其主要的決策演算法，用於決定一局比賽中每一步棋。MCTS 結合了博弈樹搜索、機器學習到的知識和模擬的全局遊戲來決定每一步。這些知識中最重要的部分是上面提到的深度神經網路。其中有一個網路（策略網路）選擇搜索中最有希望的落子位置，另一個網路（價值網路）可以評估其在搜索中遇到的數千乃至數百萬個棋盤局面。

在獲取棋局信息後，AlphaGo 的策略網路會探索哪些位置具備潛在價值，在分配的搜索時間結束時，模擬過程中被系統最繁瑣考察的位置將成為 AlphaGo 的最終選擇。在經過先期的全盤探索和過程中對最佳落子的不斷揣摩後，高效的演算法與強大的計算能力實現了超越人類的直覺判斷。

除了備受關注的圍棋以外，阿爾伯塔大學在計算機德州撲克等方面的研究也處於領先地位。在今年 1 月，阿爾伯塔大學、捷克布拉格查理大學和捷克理工大學共同發布了論文《DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker》，展示了他們在人工智慧打德州撲克方面的研究。在論文中，研究人員表示 DeepStack 已經在無限制撲克（No-Limit Poker）遊戲上達到了專家級的水平。

大多數棋盤遊戲都屬於完美信息（perfect information）遊戲，針對它們的研究難以應用到真實世界中；而撲克是一個典型的不完美信息（imperfect information）遊戲，一直以來都是人工智慧領域內的一個挑戰。DeepStack 是適用於德州撲克這種不完美信息環境的新演算法。

DeepStack 結合了回歸推理來處理信息不對稱性，還結合了分解（decomposition）來將計算集中到相關的決策上，以及一種形式的關於任意牌的直覺——該直覺可以使用深度學習進行自我玩牌而自動學習到。在一項涉及到數十位參與者和 44000 手撲克的研究中，DeepStack 成為了世界上第一個在一對一無限制德州撲克（heads-up no-limit Texas hold"em）上擊敗了職業撲克玩家的計算機程序。

撲克遊戲的狀態可以被分成玩家的私有信息（兩張牌面朝下的手牌）和公共狀態（包括牌面朝上的牌和玩家採取的下注動作序列）。遊戲中的公開狀態的可能序列構成一個公開樹（public tree），其中每一個公開狀態都有一個相關的公開子樹（public subtree）。

HUNL 中公開樹的一部分。紅色和天藍色的邊表示玩家動作。綠色邊表示公開的公共牌。帶有籌碼的葉節點表示遊戲結束，其中，如果一個玩家根據之前的動作和玩家手牌的聯合分布而棄牌或做出決定，那麼收益就可能是固定的。

DeepStack 架構概覽（見 a）。對於每一個公開狀態，DeepStack 都要重新計算它需要的動作，這會用到一個深度有限的向前預測——其中子樹值（subtree value）會通過一個訓練好的深度神經網路 Neural net（見 b）來計算，該深度神經網路 Neural net 是比賽前通過隨機生成的撲克情境（見 c）來訓練的。Martin 表示，它的成功之處在於第一次將啟發式搜索應用於不完美信息遊戲中，並獲得成功。

啟發式方法雖然已經在多種應用中獲得成功，但仍然面臨一些挑戰。「在自動駕駛、醫療等性命攸關的應用上，人類不能允許深度學習和啟發式搜索可能出現的小概率偏差，」Martin 說道。「這意味著我們還有很長一段路要走。我們目前還面臨著兩個挑戰，如何把啟發式搜索和精準的確切法聯結在一起；以及當不知道全局規則的時候，如何讓機器解決問題。」

啟發式學習經歷過三四十年的發展，它是 AlphaGo 背後的動力，也可以在未來應用於其他領域。「通過與深度學習相結合，同時有了新演算法與硬體，啟發式學習可以讓計算機系統學會真正的知識，」Martin 說道。「它能讓我們的搜索變得更加有效，能夠讓計算機幫助我們做出越來越好的決策。」

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