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

2020-09-27 機器之心Pro

機器之心報導

作者：杜偉

還記得在雙人無限撲克和多人無限撲克中戰勝人類頂級玩家的遊戲 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/

相關焦點

  • 攜Science封面,CMU大神Noam博士畢業,論文已公開
    近日，這兩個 AI 系統的開發者之一、CMU 大神宣布其完成博士論文，並即將從 CMU 畢業。當地時間 9 月 21 日，FAIR 研究科學家 Noam Brown 在推特宣布其順利完成了 CMU 博士論文答辯，並公開了長達 230 頁的超硬核博士論文《Equilibrium Finding for Large Adversarial Imperfect-Information Games》以及 101 頁的 slides。
  • 登頂Science封面、拿下NIPS最佳論文！這位CMU大神要畢業了
    這也差不多宣告他要畢業了，只等博士答辯結束就行了~等下，你怎麼知道他能百分百通過答辯？相信我，看完全文，你看誰敢把這位大神掛掉。1 拿獎到手軟Noam Brown，卡耐基梅隆大學（CMU）博士，Facebook 人工智慧實驗室研究科學家、AI德州撲克作者，致力於使AI在大型不完全信息多智能體交互中進行戰略推理。
  • AlphaZero誕生一周年:登上Science封面,完整論文首次公開
    大數據文摘出品作者：魏子敏、蔣寶尚阿爾法元（AlphaZero）誕生一周年之際，《自然（Science）》雜誌今天以封面文發布了阿爾法元（AlphaZero）經過同行審議的完整論文，Deepmind創始人兼CEO哈薩比斯親自執筆了這一論文。
  • Science封面:三元鋰電池安全性差、壽命短問題已解決,來自美國能源...
    這項鋰離子電池的重要研究工作，發表在今天的Science封面上。Yujing Bi在中科院寧波材料技術與工程研究所獲得博士學位，2018年進入PNNL。她2008年畢業於紐約州立大學賓漢姆頓分校，之後加入PNNL，擔任博士後研究助理，目前是電池和材料系統的首席科學家兼小組負責人。她還是Clarivate Analytics統計的前1%的高引學者。
  • Science封面：三元鋰電池安全性差、壽命短問題已解決
    這項鋰離子電池的重要研究工作，發表在今天的Science封面和許多「紙上談兵」的論文不同Yujing Bi在中科院寧波材料技術與工程研究所獲得博士學位她2008年畢業於紐約州立大學賓漢姆頓分校論文地址：https://science.sciencemag.org/content
  • 劍橋大學公開霍金博士論文,朝聖粉絲擠垮網站
    10月23日，劍橋大學首次公開了霍金在1966年發表的博士論文，任何人都可以免費下載閱讀。這對於物理迷來說無疑是個重大的好消息，論文公開不到24小時，就得到了超過6萬次下載。而副作用是，劍橋大學資源庫網頁因此一度癱瘓而無法訪問。
  • CMU出品,計算機圖形學秋季課程已上線,B站同步字幕視頻
    該領域的研究者也越來越多，如計算機圖形學大神 & 太極（Taichi）作者胡淵鳴、「為可微計算機圖形學奠定基礎」榮獲 SIGGRAPH 最佳博士論文獎的太極二作李子懋等等。讓計算機圖形學進一步走入大眾視線的裡程碑事件是，ACM 將 2019 年圖靈獎授予了兩位皮克斯聯合創始人、計算機圖形學專家 Patrick M. Hanrahan 和 Edwin E. Catmull。
  • 霍金公開博士論文解密黑洞理論 劍橋大學伺服器癱瘓
    想知道史蒂芬·霍金還在讀博士時，他是如何看待宇宙的，以及他的黑洞理論是怎樣形成的嗎？現在，你可以直接獲得答案——不過前提是，你能順利打開劍橋大學的網頁。2008年，霍金在劍橋。
  • 中國學者Science封面論文:甲蟲胸節上的角與翅膀系列同源
    這項研究對思考如何更好地定義進化新徵（evolutionary novelty）有著重要意義，於 11 月 22 日登上Science封面。 圖片來源：Science封面圖 撰文 胡永剛博士
  • 24歲博士剛畢業受聘「雙一流」大學副教授
    近日，一則題為「他24歲北航博士畢業受聘211高校副教授」的消息迅速在微博、知乎等網絡平臺受到關注。消息主人公是北京航空航天大學2020屆博士畢業生侯濤剛，1996年出生的他不僅拿下博士畢業證，還受聘211高校北京交通大學，成為電子信息工程學院副教授。
  • 翟天臨之後:畢業論文變成hard模式了嗎?
    文|庫洛醬圖| 流螢 封面|IYE還記得數月前，苦肝論文的翟天臨嗎？翟博士被全民打假後，最近又火了，不少畢業學生排著隊在翟天臨微博打卡，除了咒罵翟天臨害人不淺，還有人來許願還願：畢業生和翟博士間的愛恨恩仇，據報導是因為在翟天臨事件後，多所高校發布通知要求嚴查本科生論文，部分學校的畢業論文「查重率」從原來的30%以內，降低到20%，更嚴格的甚至降到了8%以下。還有學校將對已畢業學生的論文開展質量跟蹤監控。
  • 西交大碩士生畢業擬授博士學位?國內外早有先例,來看看幾位大神
    個人覺得，單就發論文這一項，就足以證明孫同學的理論功底、科研能力，已超過不少畢業博士研究生。今年上半年，曹雪濤多篇公開發表的論文，被國外學者質疑造假，一度鬧得沸沸揚揚。很多網友都知道他是南開大學校長，知道他是大科學家，卻不知道他是以碩士論文獲得博士學位的罕見破格者。
  • 知網可以查到所有碩士博士的畢業論文嗎?很多人都不知道
    網友一： 現在一般碩博畢業時學校會要求學生籤署畢業論文上網的許可。知網上找不到畢業論文可能是因為幾種情況：年代久遠當時並未集中要求，時間比較近的論文（論文上需要時間一年左右），涉密，學生未籤許可等。
  • 如何選擇博士畢業論文題目
    WOSCI沃斯編輯：如何選擇一個好的博士畢業論文題目呢？不知道該寫些什麼？因為無論選擇什麼樣的題目，自己今後的博士研究及職業生涯都將離不開這個主題。在畢業論文的寫作過程中，選擇題目對很多學生而言是一個很大的問題。
  • 霍金博士論文首次公開免費下載 網站資料庫被擠爆
    霍金博士論文首次公開你也許沒有看過《時間簡史》，但你一定知道它的作者史蒂芬·霍金（Stephen Hawking）。 這位輪椅上的「宇宙之王」雖然被疾病徹底剝奪了行走和說話的能力，但他的每次「發聲」都會成為話題引燃器。
  • 孔夫子網公開出售清北博士論文被舉報後照賣不誤
    畢業季臨近，又是「論文搞事情」的高發期。近日，澎湃新聞記者接到清華大學博士畢業生張明（化名）舉報，稱孔夫子舊書網上有不法商家售賣高校博士學位論文：「我師兄師姐師弟師妹的論文都在被賣，他們很慌。我們在去年十月就有和商家反映過，曾下線過一段時間。現在還是照賣。」
  • 霍金24歲博士論文首次公開免費下載
    當地時間23日，劍橋大學宣布首次公開霍金1966年的博士畢業論文《宇宙膨脹的性質》，任何人都可以登錄網站免費下載。學生時代的霍金腦子裡在想些什麼？所有人都想知道，於是劍橋大學資料庫開放不到一天，便被擠爆了。
  • 如何在知網下載PDF格式碩博士畢業論文
    當需要比較全面了解某一方面的研究概況時，碩博士畢業論文的文獻綜述部分或者緒論部分，是一個不錯的選擇。另外，碩博士畢業論文中試驗方法和試驗方案描述的相對比較詳細，這對於廣大研究人員了解實驗細節和實際實驗具有較大的幫助。
  • 蔡英文論文造假再現風波 未畢業便寫完升等論文
    海外網9月19日電臺灣地區領導人蔡英文「論文造假」事件在島內不斷發酵，媒體人彭文正多日來指稱蔡英文偽造學歷，甚至將組團赴倫敦拜訪蔡英文母校，「尋找圍觀」蔡英文論文。此外律師童文薰也指出，蔡英文1983年數篇論文作者介紹為「博士」，然而蔡於1984年才畢業，還未畢業就已寫完副教授升等論文。
  • 畢業論文存在抄襲、剽竊、代寫?教育部:應撤銷已授予學位
    封面新聞記者 粟裕1月7日，封面新聞記者從教育部獲悉，近日教育部印發《本科畢業論文（設計）抽檢辦法（試行）》（簡稱《辦法》）。《辦法》明確，對涉嫌存在抄襲、剽竊、偽造、篡改、買賣、代寫等學術不端行為的畢業論文，高校應按照相關程序進行調查核實，對查實的應依法撤銷已授予學位，並註銷學位證書。《辦法》指出，教育部建立全國本科畢業論文抽檢信息平臺，面向省級教育行政部門提供學術不端行為檢測、畢業論文提取和專家評審等定製功能，對各省級教育行政部門開展本科畢業論文抽檢工作實行全過程監督。