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

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

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

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

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

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

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

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

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

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

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

博士論文簡(jiǎn)介

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

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

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

CFR 方法。

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

CFR 中的剪枝流程。

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

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

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

以往方法的局限性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考鏈接：

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

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