↑ 點(diǎn)擊藍(lán)字?關(guān)注極市平臺(tái)
我已經(jīng)答辯完成了我的博士學(xué)位論文！在我攻讀博士學(xué)位的過(guò)程中，看到擊敗撲克界的頂尖人物的想法從科幻小說(shuō)演變成現(xiàn)實(shí)，真是太神奇了。
昨日，Noam Brown在推特上宣布答辯完成了卡耐基梅隆大學(xué)（CMU）的230頁(yè)超硬核博士論文：
Equilibrium Finding for Large Adversarial Imperfect-Information Games
1 拿獎(jiǎng)到手軟
Noam Brown，卡耐基梅隆大學(xué)（CMU）博士，F(xiàn)acebook 人工智能實(shí)驗(yàn)室研究科學(xué)家、AI德州撲克作者，致力于使AI在大型不完全信息多智能體交互中進(jìn)行戰(zhàn)略推理。Noam Brown已經(jīng)將自己的研究成果應(yīng)用到了第一款在無(wú)限注德州撲克中擊敗頂級(jí)人類的 AI 上。他和他的CMU導(dǎo)師一起創(chuàng)建了AI系統(tǒng)Libratus和Pluribus，并在人機(jī)對(duì)抗比賽中果斷擊敗了頂尖的人類撲克職業(yè)玩家：2017 年一月在賓夕法尼亞州匹茲堡的 Rivers 賭場(chǎng)，一場(chǎng)獎(jiǎng)金20 萬(wàn)美元的比賽正在進(jìn)行，在這為期 20 天的賽程里面 4 名人類職業(yè)玩家和 Libratus共對(duì)戰(zhàn)12 萬(wàn)手。最終，Libratus 人工智能系統(tǒng)成功擊敗了人類頂級(jí)職業(yè)玩家。
AI撲克Pluribus也因此曾登頂了Science封面：不可不提的是，同樣在2017年 ，Noam Brown及其導(dǎo)師獲得了NIPS 2017最佳論文獎(jiǎng)，獲獎(jiǎng)?wù)撐模?/span>2019年，同樣是和導(dǎo)師合作，他們二人又拿下AAAI 2019 最佳論文提名獎(jiǎng)，獲獎(jiǎng)?wù)撐模?/span>隨后Noam Brown之后的一系列成果也成為《Science》2019年年度突破的亞軍：除此之外，Noam Brown及其團(tuán)隊(duì)也因在AI方面的杰出成就獲得了馬文·明斯基獎(jiǎng)（Marvin Minsky，人工智能先驅(qū)）。最后，Noam Brown本人也被《MIT科技評(píng)論》評(píng)為35歲以下35位創(chuàng)新者之一。而獲得過(guò)這個(gè)獎(jiǎng)項(xiàng)的大佬都有誰(shuí)呢？2 研究背景
近年來(lái)，以AlphaGo為代表的人工智能進(jìn)步有目共睹，人工智能也再一次火遍全球。
而人工智能的成功似乎總是和人類對(duì)抗游戲的表現(xiàn)做對(duì)比體現(xiàn)出來(lái)。對(duì)抗游戲的核心就在于博弈一詞，博弈論起源于納什均衡：大家有看過(guò)電影《美麗心靈》的都會(huì)知道一二。囚徒困境的故事講的是，兩個(gè)嫌疑犯作案后被警察抓住，分別關(guān)在不同的屋子里接受審訊。警察知道兩人有罪，但缺乏足夠的證據(jù)。警察告訴每個(gè)人：如果兩人都抵賴，各判刑1年；如果兩人都坦白，各判兩年；如果兩人中一個(gè)坦白而另一個(gè)抵賴，坦白的放出去，抵賴的判5年。于是，每個(gè)囚徒都面臨兩種選擇：坦白或抵賴。然而，管同伙選擇什么，每個(gè)囚徒的最優(yōu)選擇是坦白：如果同伙抵賴、自己坦白的話放出去，抵賴的話判5年，坦白比不坦白好；如果同伙坦白、自己坦白的話判兩年，比起抵賴的判5年，坦白還是比抵賴的好。結(jié)果，兩個(gè)嫌疑犯都選擇坦白，各判刑兩年。現(xiàn)在我們談?dòng)螒?，以游戲?yàn)榇淼男畔⒉┺拇笾驴梢苑譃橥耆ㄍ昝?信息博弈和不完全(完美)信息博弈。跳棋、國(guó)際象棋、五子棋、圍棋等都屬于完美信息博弈，即雙方都知道博弈中每一時(shí)刻的確切狀態(tài)，以及未來(lái)可能發(fā)生的所有狀態(tài)（如果算力允許）。相反，撲克牌是不完美信息博弈：博弈狀態(tài)的一些信息是隱藏的，即博弈中存在包含多個(gè)決策點(diǎn)的信息集或博弈者無(wú)法預(yù)測(cè)對(duì)手的一些行動(dòng)。很顯然，在撲克牌中如果大家都互相知道對(duì)手的牌面，那四個(gè)3也就沒(méi)法當(dāng)成4個(gè)2唬住對(duì)方了，這會(huì)使游戲頓時(shí)變得索然無(wú)味~隱藏信息在現(xiàn)實(shí)世界策略互動(dòng)中無(wú)處不在，如交通信息、戰(zhàn)爭(zhēng)等，這使得研究不完美信息博弈的技術(shù)尤其重要。而反觀Noam Brown這一路拿獎(jiǎng)到手軟的歷程，其實(shí)可以看出他的研究關(guān)注點(diǎn)一直都在不完全信息博弈上面,這一次他在推特上介紹的也是剛剛完成的博士論文:研究大型對(duì)抗性不完全信息博弈的均衡發(fā)現(xiàn)，這也是他博士幾年的研究積累成果匯總。接下來(lái)就來(lái)介紹一下這篇博士論文。3?博士論文
《Equilibrium Finding for Large Adversarial Imperfect-Information Games》http://www.cs.cmu.edu/~noamb/thesis.pdf? ??Noam Brown在博士論文前言有提到,除了第5.3節(jié)的ReBeL外，本文中的所有研究都是他和他的導(dǎo)師Tuomas Sandholm合作完成的，而在致謝中Noam Brown又說(shuō)到：首先我要感謝我的導(dǎo)師 ?Tuomas Sandholm 。Tuomas耐心地指導(dǎo)我完成了整個(gè)研究過(guò)程，包括幾次深夜披薩助力（ late-night pizza-fueled）的論文寫(xiě)作。沒(méi)有這個(gè)指導(dǎo)，我的博士學(xué)位肯定不會(huì)成功。
說(shuō)到這里，我們不得不停下來(lái)問(wèn)一句，Noam Brown還都干了啥？——帶你“打德州撲克”、帶你上Science封面、帶你拿NIPS最佳論文！帶你拿馬文.明斯基獎(jiǎng).......請(qǐng)問(wèn)這么好的導(dǎo)師上哪去找？請(qǐng)給我來(lái)一打！跟著這樣的導(dǎo)師簡(jiǎn)直要起飛了！別問(wèn)，問(wèn)就是：帶你梭哈！不完全信息博弈模型是指多個(gè)主體與私人信息之間的相互作用。在這種情況下，一個(gè)典型的目標(biāo)是接近一個(gè)均衡，在這個(gè)平衡中，所有的智能體策略都是最優(yōu)的。本文描述了大型對(duì)抗性不完全信息博弈均衡計(jì)算的若干進(jìn)展。這些新技術(shù)使人工智能智能體首次有可能在無(wú)限注撲克牌中擊敗頂尖的人類專業(yè)玩家，幾十年來(lái)，這一直是人工智能和博弈論領(lǐng)域的重大挑戰(zhàn)問(wèn)題。我們首先介紹了對(duì)反事實(shí)后悔最小化（CFR）的改進(jìn)，這是一種在兩人零和博弈中收斂到納什均衡的迭代算法。我們描述了CFR的新變體，它使用折扣原則（discounting）來(lái)顯著加快收斂速度。這些新的CFR變體現(xiàn)在是大型對(duì)抗性不完全信息博弈的SOTA均衡發(fā)現(xiàn)(equilibrium-finding)算法。我們還介紹了第一個(gè)熱啟動(dòng)（ warm starting）CFR的通用技術(shù)。隨后，我們介紹了理論上合理的剪枝技術(shù)，可以在大型博弈中數(shù)量級(jí)地加速收斂。接下來(lái)，我們將描述通過(guò)自動(dòng)抽象和函數(shù)近似將CFR擴(kuò)展到大型游戲的新方法。特別地，我們介紹了第一個(gè)在不完全信息博弈中離散連續(xù)動(dòng)作空間的算法。我們將其擴(kuò)展到求解具有連續(xù)動(dòng)作空間博弈的算法中。之后，我們介紹了Deep CFR，一種使用神經(jīng)網(wǎng)絡(luò)函數(shù)近似而不是基于bucketing的抽象形式。Deep CFR是第一個(gè)可擴(kuò)展到大型游戲的non-tabular形式的CFR，它使CFR能夠在幾乎沒(méi)有領(lǐng)域知識(shí)的情況下成功部署。
最后，我們提出了一種新的不完全信息博弈搜索技術(shù)，以確保智能體的搜索策略不會(huì)被對(duì)手利用。這些新的搜索形式在理論上和實(shí)踐上都優(yōu)于過(guò)去的方法。接下來(lái)，我們將介紹一種深度受限搜索的方法，它在計(jì)算上比以前的方法要代價(jià)要少得多。最最后，我們提出了一種在訓(xùn)練和測(cè)試時(shí)結(jié)合強(qiáng)化學(xué)習(xí)和搜索的算法ReBeL:它朝著彌合完全信息游戲和不完全信息游戲研究之間的差距邁出了重要的一步。在致謝的最后，Noam Brown表達(dá)了對(duì)家人的感謝：最后，我要特別感謝我的父母 Michael 和 Nurit，還有我的全家，感謝你們一直支持我，鼓勵(lì)我追求我的激情。
推薦閱讀
來(lái)測(cè)一測(cè)你是幾級(jí)的煉丹師？添加極市小助手微信（ID : cvmart2），備注：姓名-學(xué)校/公司-研究方向-城市（如：小極-北大-目標(biāo)檢測(cè)-深圳），即可申請(qǐng)加入極市目標(biāo)檢測(cè)/圖像分割/工業(yè)檢測(cè)/人臉/醫(yī)學(xué)影像/3D/SLAM/自動(dòng)駕駛/超分辨率/姿態(tài)估計(jì)/ReID/GAN/圖像增強(qiáng)/OCR/視頻理解等技術(shù)交流群：每月大咖直播分享、真實(shí)項(xiàng)目需求對(duì)接、求職內(nèi)推、算法競(jìng)賽、干貨資訊匯總、與?10000+來(lái)自港科大、北大、清華、中科院、CMU、騰訊、百度等名校名企視覺(jué)開(kāi)發(fā)者互動(dòng)交流~
△長(zhǎng)按關(guān)注極市平臺(tái)，獲取最新CV干貨覺(jué)得有用麻煩給個(gè)在看啦~??
