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

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

當(dāng)?shù)貢r間 9 月 21 日，F(xiàn)AIR 研究科學(xué)家 Noam Brown 在推特宣布其順利完成了 CMU 博士論文答辯，并公開了長達(dá) 230 頁的超硬核博士論文《Equilibrium Finding for Large Adversarial Imperfect-Information Games》以及 101 頁的 slides。

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

Noam Brown 與其導(dǎo)師 Tuomas Sandholm 教授（左）。

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

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

圍棋、國際象棋、跳棋等棋類游戲?qū)儆谕昝佬畔⒉┺摹?***牌則屬于典型的不完美信息博弈，這也是 Noam Brown 一直以來的研究重心。從 2017 年的 AI 系統(tǒng) Libratus 到 2019 年的新算法 Pluribus，它們都屬于不完美信息博弈的范疇。

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

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

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

博士論文簡介

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

反事實遺憾最小化（CFR）的改進(jìn)

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

CFR 方法。

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

CFR 中的剪枝流程。

將 CFR 擴(kuò)展至大型博弈

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

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

以往方法的局限性。

所以，作者提出了 CFR 的一種變體 Deep CFR，它使用了神經(jīng)網(wǎng)絡(luò)函數(shù)近似，而沒有使用基于 bucketing 的抽象。Deep CFR 是首個可以擴(kuò)展至大型博弈的 non-tabular 形式的 CFR，并且使得 CFR 在幾乎沒有領(lǐng)域知識的設(shè)置下實現(xiàn)部署。

利用 Deep CFR 擴(kuò)展至大型博弈中。

不斷改進(jìn)的搜索技術(shù)

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

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

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

最后，作者提出了一種新型 ReBel 算法，它在訓(xùn)練和測試時結(jié)合強(qiáng)化學(xué)習(xí)和搜索，并為縮小完美信息博弈和不完美信息博弈研究的差距邁出了關(guān)鍵一步。

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

以下是博士論文的章節(jié)目錄：

致力于德?lián)溆螒?AI 研究的 CMU 大神 Noam Brown

Noam Brown，F(xiàn)acebook 人工智能實驗室的研究科學(xué)家，他致力于結(jié)合計算博弈論和機(jī)器學(xué)習(xí)來開發(fā)能夠在不完美信息多智能體環(huán)境中進(jìn)行策略推理的 AI 系統(tǒng)，其研究成果應(yīng)用到了首個分別在在雙人無限****和多人無限****中戰(zhàn)勝人類頂級玩家的 Libratus 和 Pluribus。這兩個游戲 AI 系統(tǒng)為 Noam Brown 帶來了巨大的榮譽(yù)。

2017 年，Noam Brown 與其導(dǎo)師 Tuomas Sandholm 開發(fā)的 AI 系統(tǒng) Libratus 在賓夕法尼亞州匹茲堡 Rivers ****場持續(xù) 20 天 1 對 1 無限制德?lián)浔荣愔谐晒?zhàn)勝了 4 名全球頂級職業(yè)玩家。該研究登上了《科學(xué)》雜志，與研究相關(guān)的另一篇論文《Safe and Nested Subgame Solving for Imperfect-Information Games》也獲得了 NIPS 2017 最佳論文獎。

此外，Noam 團(tuán)隊還因此獲得了 IJCAI 頒發(fā)的第二枚馬文 · 明斯基獎?wù)拢∕arvin Minsky Medal）。

Noam 在 IJCAI 2019 大會上領(lǐng)取馬文 · 明斯基獎?wù)伦C書。

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

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

Pluribus 登上了《科學(xué)雜志》封面。

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

參考鏈接：

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

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