登頂Science封面、拿下NIPS最佳論文！這位CMU大神要畢業了

作者 | 陳大鑫

我已經成功完成了我的博士學位論文！在我攻讀博士學位的過程中，看到擊敗撲克界的頂尖人物的想法從科幻小說演變成現實，真是太神奇了。

昨日，Noam Brown在推特上宣布自己完成了卡耐基梅隆大學（CMU）的230頁超硬核博士論文：

《Equilibrium Finding for Large Adversarial Imperfect-Information Games》

這也差不多宣告他要畢業了，只等博士答辯結束就行了~

等下，你怎麼知道他能百分百通過答辯？

相信我，看完全文，你看誰敢把這位大神掛掉。

1 拿獎到手軟

Noam Brown，卡耐基梅隆大學（CMU）博士，Facebook 人工智慧實驗室研究科學家、AI德州撲克作者，致力於使AI在大型不完全信息多智能體交互中進行戰略推理。

Noam Brown已經將自己的研究成果應用到了第一款在無限注德州撲克中擊敗頂級人類的 AI 上。

他和他的CMU導師一起創建了AI系統Libratus和Pluribus，並在人機對抗比賽中果斷擊敗了頂尖的人類撲克職業玩家：

2017 年一月在賓夕法尼亞州匹茲堡的 Rivers 賭場，一場獎金20 萬美元的比賽正在進行，在這為期 20 天的賽程裡面 4 名人類職業玩家和 Libratus共對戰12 萬手。最終，Libratus 人工智慧系統成功擊敗了人類頂級職業玩家。

AI撲克Pluribus也因此曾登頂了《Scinec》封面：

不可不提的是，同樣在2017年 ，Noam Brown及其導師獲得了NIPS 2017最佳論文獎，獲獎論文：

2019年，同樣是和導師合作，他們二人又拿下AAAI 2019傑出論文獎，獲獎論文：

隨後Noam Brown之後的一系列成果也成為《Science》2019年年度突破的亞軍：

除此之外，Noam Brown及其團隊也因在AI方面的傑出成就獲得了馬文·明斯基獎（Marvin Minsky，人工智慧先驅）。

最後，Noam Brown本人也被《MIT科技評論》評為35歲以下35位創新者之一。

而獲得過這個獎項的大佬都有誰呢？

2 研究背景

近年來，以AlphaGo為代表的人工智慧進步有目共睹，人工智慧也再一次火遍全球。

而人工智慧的成功似乎總是和人類對抗遊戲的表現做對比體現出來。

對抗遊戲的核心就在於博弈一詞，博弈論起源於納什均衡：

大家有看過電影《美麗心靈》的都會知道一二。

而納什均衡的代表就是囚徒困境：

囚徒困境的故事講的是，兩個嫌疑犯作案後被警察抓住，分別關在不同的屋子裡接受審訊。警察知道兩人有罪，但缺乏足夠的證據。

警察告訴每個人：如果兩人都抵賴，各判刑1年；如果兩人都坦白，各判兩年；如果兩人中一個坦白而另一個抵賴，坦白的放出去，抵賴的判5年。於是，每個囚徒都面臨兩種選擇：坦白或抵賴。

然而，管同夥選擇什麼，每個囚徒的最優選擇是坦白：如果同夥抵賴、自己坦白的話放出去，抵賴的話判5年，坦白比不坦白好；如果同夥坦白、自己坦白的話判兩年，比起抵賴的判5年，坦白還是比抵賴的好。結果，兩個嫌疑犯都選擇坦白，各判刑兩年。

現在我們談遊戲，以遊戲為代表的信息博弈大致可以分為完全（完美)信息博弈和不完全(完美)信息博弈。

跳棋、西洋棋、五子棋、圍棋等都屬於完美信息博弈，即雙方都知道博弈中每一時刻的確切狀態，以及未來可能發生的所有狀態（如果算力允許）。

相反，撲克牌是不完美信息博弈：博弈狀態的一些信息是隱藏的，即博弈中存在包含多個決策點的信息集或博弈者無法預測對手的一些行動。

很顯然，在撲克牌中如果大家都互相知道對手的牌面，那四個3也就沒法當成4個2唬住對方了，這會使遊戲頓時變得索然無味~

隱藏信息在現實世界策略互動中無處不在，如交通信息、戰爭等，這使得研究不完美信息博弈的技術尤其重要。

而反觀Noam Brown這一路拿獎到手軟的歷程，其實可以看出他的研究關注點一直都在不完全信息博弈上面,這一次他在推特上介紹的也是剛剛完成的博士論文:研究大型對抗性不完全信息博弈的均衡發現，這也是他博士幾年的研究積累成果匯總。

接下來就來介紹一下這篇博士論文。

3 博士論文

論文名稱：

《Equilibrium Finding for Large Adversarial Imperfect-Information Games》

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

Noam Brown在博士論文前言有提到,除了第5.3節的ReBeL外，本文中的所有研究都是他和他的導師Tuomas Sandholm合作完成的，而在致謝中Noam Brown又說到：

首先我要感謝我的導師 Tuomas Sandholm 。Tuomas耐心地指導我完成了整個研究過程，包括幾次深夜披薩助力（ late-night pizza-fueled）的論文寫作。沒有這個指導，我的博士學位肯定不會成功。

說到這裡，我們不得不停下來問一句，Noam Brown還都幹了啥？

——帶你「打德州撲克」、帶你上Science封面、帶你拿NIPS最佳論文！帶你拿馬文.明斯基獎.......

請問這麼好的導師上哪去找？請給我來一打！

跟著這樣的導師簡直要起飛了！別問，問就是：帶你梭哈！

論文摘要

不完全信息博弈模型是指多個主體與私人信息之間的相互作用。在這種情況下，一個典型的目標是接近一個均衡，在這個平衡中，所有的智能體策略都是最優的。本文描述了大型對抗性不完全信息博弈均衡計算的若干進展。這些新技術使人工智慧智能體首次有可能在無限注撲克牌中擊敗頂尖的人類專業玩家，幾十年來，這一直是人工智慧和博弈論領域的重大挑戰問題。

我們首先介紹了對反事實後悔最小化（CFR）的改進，

這是一種在兩人零和博弈中收斂到納什均衡的迭代算法。我們描述了CFR的新變體，它使用折扣原則（discounting）來顯著加快收斂速度。

這些新的CFR變體現在是大型對抗性不完全信息博弈的SOTA均衡發現(equilibrium-finding)算法。我們還介紹了第一個熱啟動（ warm starting）CFR的通用技術。

隨後，我們介紹了理論上合理的剪枝技術，可以在大型博弈中數量級地加速收斂。

接下來，我們將描述通過自動抽象和函數近似將CFR擴展到大型遊戲的新方法。

特別地，我們介紹了第一個在不完全信息博弈中離散連續動作空間的算法。我們將其擴展到求解具有連續動作空間博弈的算法中。

之後，我們介紹了Deep CFR，一種使用神經網絡函數近似而不是基於bucketing的抽象形式。Deep CFR是第一個可擴展到大型遊戲的non-tabular形式的CFR，它使CFR能夠在幾乎沒有領域知識的情況下成功部署。

最後，我們提出了一種新的不完全信息博弈搜索技術，以確保智能體的搜索策略不會被對手利用。

這些新的搜索形式在理論上和實踐上都優於過去的方法。接下來，我們將介紹一種深度受限搜索的方法，它在計算上比以前的方法要代價要少得多。

最最後，我們提出了一種在訓練和測試時結合強化學習和搜索的算法ReBeL:

它朝著彌合完全信息遊戲和不完全信息遊戲研究之間的差距邁出了重要的一步。

論文目錄：

在致謝的最後，Noam Brown表達了對家人的感謝：

最後，我要特別感謝我的父母 Michael 和 Nurit，還有我的全家，感謝你們一直支持我，鼓勵我追求我的激情。