還記得在雙人無限撲克和多人無限撲克中戰(zhàn)勝人類頂級(jí)玩家的游戲 ai 系統(tǒng)冷撲大師（libratus）和 pluribus 嗎？近日，這兩個(gè) ai 系統(tǒng)的開發(fā)者之一、cmu 大神宣布其完成博士論文，并即將從 cmu 畢業(yè)。
當(dāng)?shù)貢r(shí)間 9 月 21 日，fair 研究科學(xué)家 noam brown 在推特宣布其順利完成了 cmu 博士論文答辯，并公開了長(zhǎng)達(dá) 230 頁的超硬核博士論文《equilibrium finding for large adversarial imperfect-information games》以及 101 頁的 slides。
noam 在論文前言中表示，除了章節(jié) 5.3 中描述的 rebel 算法，論文中所有其他研究都是與其導(dǎo)師 tuomas sandholm 合作完成的。在整個(gè)研究過程中，tuomas 給了 noam 耐心指導(dǎo)。noam 表示，如果沒有導(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ì)正在玩的游戲沒有共同知識(shí)，如其他玩家是誰、哪些策略或行動(dòng)是可行的、結(jié)果如何取決于行動(dòng)等。就難度而言，信息的不完美增加了玩家決策選擇的難度，因而博弈分析的難度也更大。
圍棋、國(guó)際象棋、跳棋等棋類游戲?qū)儆谕昝佬畔⒉┺摹淇伺苿t屬于典型的不完美信息博弈，這也是 noam brown 一直以來的研究重心。從 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 智能體首次有可能在無限注撲克游戲中擊敗頂級(jí)職業(yè)玩家，而這正是幾十年來 ai 和博弈論領(lǐng)域一直存在的重大挑戰(zhàn)性難題。
反事實(shí)遺憾最小化（cfr）的改進(jìn)
作者首先介紹了對(duì)反事實(shí)遺憾最小化（counterfactual regret minimization, cfr）做出的改進(jìn)，這是一種在雙人零和博弈中收斂至納什均衡的迭代算法。此外還描述了 cfr 的新變體，它們利用折扣原則（discounting）來顯著加快收斂速度。
cfr 方法。
然后，作者介紹了理論上合理的剪枝（pruning）技術(shù)，這些技術(shù)可以在大型博弈中呈數(shù)量級(jí)地加快收斂速度。
cfr 中的剪枝流程。
將 cfr 擴(kuò)展至大型博弈
作者描述了通過自動(dòng)抽象和函數(shù)近似算法將 cfr 擴(kuò)展至大型博弈的新方法。
具體而言，作者介紹了首個(gè)在不完美信息博弈中離散化連續(xù)動(dòng)作空間的算法，該算法被證明局部最優(yōu)。但是，這種算法需要大量的領(lǐng)域知識(shí)，并且難以擴(kuò)展至其他博弈中。
以往方法的局限性。
所以，作者提出了 cfr 的一種變體 deep cfr，它使用了神經(jīng)網(wǎng)絡(luò)函數(shù)近似，而沒有使用基于 bucketing 的抽象。deep cfr 是首個(gè)可以擴(kuò)展至大型博弈的 non-tabular 形式的 cfr，并且使得 cfr 在幾乎沒有領(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)鍵一步。
在雙人無限注德州撲克中的結(jié)果對(duì)比。
以下是博士論文的章節(jié)目錄：
致力于德?lián)溆螒?ai 研究的 cmu 大神 noam brown
noam brown，facebook 人工智能實(shí)驗(yàn)室的研究科學(xué)家，他致力于結(jié)合計(jì)算博弈論和機(jī)器學(xué)習(xí)來開發(fā)能夠在不完美信息多智能體環(huán)境中進(jìn)行策略推理的 ai 系統(tǒng)，其研究成果應(yīng)用到了首個(gè)分別在在雙人無限撲克和多人無限撲克中戰(zhàn)勝人類頂級(jí)玩家的 libratus 和 pluribus。這兩個(gè)游戲 ai 系統(tǒng)為 noam brown 帶來了巨大的榮譽(yù)。
2017 年，noam brown 與其導(dǎo)師 tuomas sandholm 開發(fā)的 ai 系統(tǒng) libratus 在賓夕法尼亞州匹茲堡 rivers 賭場(chǎng)持續(xù) 20 天 1 對(duì) 1 無限制德?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書。
2019 年，noam brown 與其導(dǎo)師 tuomas sandholm 在 libratus 的基礎(chǔ)上，開發(fā)出了所需算力更少的新算法 pluribus。在為期 12 天、超過 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)。