攜Science封面、NIPS最佳論文，CMU大神Noam博士畢業，論文已公開

還記得在雙人無限****和多人無限****中戰勝人類頂級玩家的游戲 AI 系統冷撲大師（Libratus）和 Pluribus 嗎？近日，這兩個 AI 系統的開發者之一、CMU 大神宣布其完成博士論文，并即將從 CMU 畢業。

當地時間 9 月 21 日，FAIR 研究科學家 Noam Brown 在推特宣布其順利完成了 CMU 博士論文答辯，并公開了長達 230 頁的超硬核博士論文《Equilibrium Finding for Large Adversarial Imperfect-Information Games》以及 101 頁的 slides。

Noam 在論文前言中表示，除了章節 5.3 中描述的 ReBel 算法，論文中所有其他研究都是與其導師 Tuomas Sandholm 合作完成的。在整個研究過程中，Tuomas 給了 Noam 耐心指導。Noam 表示，如果沒有導師的悉心指導，他肯定不會順利地完成博士學位。

Noam Brown 與其導師 Tuomas Sandholm 教授（左）。

Noam Brown 的博士論文題目為《大型對抗性不完美信息博弈的均衡發現》。不完美信息博弈模擬了多個智能體與私人信息之間的交互。在這一設置下，一個典型的目標是近似一個均衡，其中所有智能體的策略都能達到最優。

完美信息博弈（Perfect-information Games）和不完美信息博弈（Imperfect-information Games）是游戲中信息博弈的兩種主要形式。在游戲中，完美信息博弈的前提是所有玩家都知道關于游戲的信息，如規則等；而不完美信息博弈中的玩家對正在玩的游戲沒有共同知識，如其他玩家是誰、哪些策略或行動是可行的、結果如何取決于行動等。就難度而言，信息的不完美增加了玩家決策選擇的難度，因而博弈分析的難度也更大。

圍棋、國際象棋、跳棋等棋類游戲屬于完美信息博弈。****牌則屬于典型的不完美信息博弈，這也是 Noam Brown 一直以來的研究重心。從 2017 年的 AI 系統 Libratus 到 2019 年的新算法 Pluribus，它們都屬于不完美信息博弈的范疇。

在論文中，Noam Brown 對博士期間的一系列研究成果進行了匯總。機器之心對該論文的核心內容進行了簡要介紹，感興趣的讀者可以閱讀原論文。

論文地址：http://www.cs.cmu.edu/~noamb/thesis.pdf

Slides 地址：http://www.cs.cmu.edu/~noamb/thesis_slides.pdf

博士論文簡介

這篇博士論文詳述了大型對抗性不完美信息博弈中均衡計算的一系列進展。這些新技術使得 AI 智能體首次有可能在無限注****游戲中擊敗頂級職業玩家，而這正是幾十年來 AI 和博弈論領域一直存在的重大挑戰性難題。

反事實遺憾最小化（CFR）的改進

作者首先介紹了對反事實遺憾最小化（counterfactual regret minimization, CFR）做出的改進，這是一種在雙人零和博弈中收斂至納什均衡的迭代算法。此外還描述了 CFR 的新變體，它們利用折扣原則（discounting）來顯著加快收斂速度。

CFR 方法。

然后，作者介紹了理論上合理的剪枝（pruning）技術，這些技術可以在大型博弈中呈數量級地加快收斂速度。

CFR 中的剪枝流程。

將 CFR 擴展至大型博弈

作者描述了通過自動抽象和函數近似算法將 CFR 擴展至大型博弈的新方法。

具體而言，作者介紹了首個在不完美信息博弈中離散化連續動作空間的算法，該算法被證明局部最優。但是，這種算法需要大量的領域知識，并且難以擴展至其他博弈中。

以往方法的局限性。

所以，作者提出了 CFR 的一種變體 Deep CFR，它使用了神經網絡函數近似，而沒有使用基于 bucketing 的抽象。Deep CFR 是首個可以擴展至大型博弈的 non-tabular 形式的 CFR，并且使得 CFR 在幾乎沒有領域知識的設置下實現部署。

利用 Deep CFR 擴展至大型博弈中。

不斷改進的搜索技術

作者提出了一種新的不完美信息博弈搜索技術，該技術確保智能體的搜索策略不被對手利用。這些新的搜索形式在理論和實踐兩方面均優于以往方法。

此外，作者介紹了一種深度受限（depth-limited）搜索方法，它的計算成本顯著低于以往方法。

Pluribus 算法中的深度受限搜索。

最后，作者提出了一種新型 ReBel 算法，它在訓練和測試時結合強化學習和搜索，并為縮小完美信息博弈和不完美信息博弈研究的差距邁出了關鍵一步。

在雙人無限注德州****中的結果對比。

以下是博士論文的章節目錄：

致力于德撲游戲 AI 研究的 CMU 大神 Noam Brown

Noam Brown，Facebook 人工智能實驗室的研究科學家，他致力于結合計算博弈論和機器學習來開發能夠在不完美信息多智能體環境中進行策略推理的 AI 系統，其研究成果應用到了首個分別在在雙人無限****和多人無限****中戰勝人類頂級玩家的 Libratus 和 Pluribus。這兩個游戲 AI 系統為 Noam Brown 帶來了巨大的榮譽。

2017 年，Noam Brown 與其導師 Tuomas Sandholm 開發的 AI 系統 Libratus 在賓夕法尼亞州匹茲堡 Rivers ****場持續 20 天 1 對 1 無限制德撲比賽中成功戰勝了 4 名全球頂級職業玩家。該研究登上了《科學》雜志，與研究相關的另一篇論文《Safe and Nested Subgame Solving for Imperfect-Information Games》也獲得了 NIPS 2017 最佳論文獎。

此外，Noam 團隊還因此獲得了 IJCAI 頒發的第二枚馬文 · 明斯基獎章（Marvin Minsky Medal）。

Noam 在 IJCAI 2019 大會上領取馬文 · 明斯基獎章證書。

2019 年，Noam Brown 與其導師 Tuomas Sandholm 在 Libratus 的基礎上，開發出了所需算力更少的新算法 Pluribus。在為期 12 天、超過 10000 手牌的比賽中，Pluribus 擊敗了 15 名人類頂級玩家。

這是 AI 首次在玩家人數（或隊伍）大于 2 的大型基準游戲中擊敗頂級職業玩家。Pluribus 不僅登上了《科學》雜志的封面，還被該雜志列為 2019 年度十大突破科研成就之一。

Pluribus 登上了《科學雜志》封面。

此外，Noam 還曾獲得 2017 年度 Allen Newell「卓越研究獎」，也曾被 MIT 科技評論評選為 2019 年度「35 歲以下科技精英」（MIT TR35）。2019 年，Noam Brown 與其導師 Tuomas Sandholm 合著的論文《Solving Imperfect-Information Games via Discounted Regret Minimization》獲得了 AAAI 杰出論文榮譽提名獎。

參考鏈接：

https://mp.weixin.qq.com/s/IoaSWYvBn_M2Io5EGcDWOA

https://www.cs.cmu.edu/~noamb/