AI賭神稱霸德撲的秘密，剛剛被《科學》「曝光」了

夏乙 問耕 發自 凹非寺

量子位 出品 | 公眾號 QbitAI

稱霸德州撲克賽場的賭神Libratus，是今年最矚目的AI明星之一。

剛剛，《科學》最新發布的預印版論文，詳細解讀了AI賭神背後系統的全貌。此前的NIPS 2017大會上，最佳論文就頒給了Libratus團隊，不過那篇會議論文只是重點講述這個德撲AI中的子博弈求解演算法。

在最新論文Superhuman AI for heads-up no-limit poker: Libratus beats top professionals中，卡內基梅隆大學（CMU）的博士生Noam Brown和教授Tuomas Sandholm，詳細介紹了德撲AI如何通過將遊戲分解為可計算、可管理的部分，來實現超越人類的表現，而且AI還能根據對手情況，修正潛在的戰略弱點。

Libratus所用到的技術既不需要領域專家知識，也沒有使用人類數據，甚至不是專門為撲克設計的。換句話說，這些技術適用於多種不完美信息博弈。

不完美博弈正是德撲的一個主要特徵。圍棋、國際象棋、跳棋等棋類遊戲，屬於完美信息博弈，對戰的雙方，清楚每一時刻局面上的全部情況。相比之下，德州撲克存在大量的隱藏信息，包括：對手持有什麼牌，對手是否在詐唬？

詳解Libratus

據最新論文介紹，Libratus主要包括三個模塊。

第一個模塊負責對牌面進行簡化計算，將包含10161種情況的一對一無限注德撲抽象成一個比較簡單的博弈。然後，這個模塊為前兩輪制定詳細的策略，並為後兩輪制定一個粗略的策略。這個抽象簡化版博弈的解決方法稱為藍圖策略（blueprint strategy）。

這種抽象體現在兩個方面，一是下注金額上，二是牌面上。

在下注金額上，100美元和101美元其實幾乎沒有差別，因此，演算法可以對不到100美元的差異進行四捨五入。同時，將類似的牌面視為同一類，也能降低計算的複雜度。

需要說明的是，Libratus在後兩輪遊戲中並不會按照抽象版的解決方法來玩，藍圖策略在這兩輪中的作用，只是用來估算玩家在子遊戲中每一首牌應該得到的獎勵，然後參考這個估算值，在真正的牌局中做出更精確的策略。

這個「更精確的策略」，也就是第二個模塊：嵌套安全子博弈求解(Nested safe subgame solving)。在博弈後期，這個模塊會基於當前的牌面，構建一個全新的、更精細的抽象，而且對這個子博弈的策略進行實時計算。

△ Subgame solving

上圖是Libratus的子博弈求解過程。頂部表示在對局過程中出現了一個子博弈，中間部分表示演算法為這個子博弈制定了更詳細的策略，每次迭代中，對手隨機發放一手牌，可選的期望值可能來自舊的抽象（紅色），也可以來自新的、更精細的抽象（綠色）。如果期望值來自新的抽象，兩個玩家的策略都會改變。這就迫使Libratus制定更精細的策略。上圖底部表示用新的策略替代舊策略。

△ nested subgame solving圖解

Libratus的子博弈策略計算和那些完美信息博弈不太一樣，它需要確保這些子博弈的精細解決方法與整個博弈的大藍圖策略不衝突，而不能孤立地解決它。

第三個模塊的意義，是隨著比賽的進行，改進自身的藍圖策略。Sandholm教授表示，通常AI使用機器學習來發現對手的戰略錯誤並加以利用。但這也會讓AI暴露自身的弱點，並被對手加以利用。

不同之處在於，Libratus的自我改進模塊分析對手賭注大小，以檢測自身藍圖戰略中潛在的漏洞，然後彌補自身的不足之處。

在與人類高手對戰之前，Sandholm和Brown為了測試Libratus中所用的各項技術，先用簡化版的撲克對整體流程進行了測試，然後把AI用到了完整版的一對一無限注德州撲克上，和他們自己之前開發的Baby Tartanian8進行比賽。

2016年，Baby Tartanian8曾經贏得電腦德撲大賽冠軍，不過Libratus以63±28大盲注/千手(mbb/hand)的戰績擊敗了它。

「我們研發的技術在很大程度上是獨立於領域的，因此可以應用於其他不完美信息策略應用，不僅限於遊戲領域」，Sandholm和Brown總結說：現實世界的戰略交鋒中，隱藏信息無處不在，Libratus引入的範式對AI未來的發展和引用至關重要。

目前，這項技術已經授權給Sandholm創辦的公司。

論文地址

http://science.sciencemag.org/content/early/2017/12/15/science.aao1733

獨家對話

今年3月，量子位前往CMU專程拜訪過Sandholm和Brown。當時，他們就曾談及Libratus的理念，包括三個模塊的設計思路。

這裡也把量子位之前報道的內容摘錄如下。

無師自通

在德撲這件事上，Libratus沒有師父。

Sandholm和Brown只告訴AI基本的德州撲克規則，然後Libratus就開始通過「左右手互搏」的方式學習這個撲克遊戲。和AlphaGo不同，在人機大戰之前Libratus沒有研究過人類如何打德州撲克，也沒有和人類職業玩家有過交手。

在投入實戰之前，Libratus自己對戰了幾百萬手牌，其中有不少是帶有特定目的的殘局，真正機器和機器之間的交手，大約是幾十萬手。

所以，AI形成了一種與人類迥然不同的牌風。

「在德撲比賽中，頂級高手會嘗試尋找對手的弱點，並展開攻擊」，創新工場AI工程院技術VP李天放說。李天放既有技術背景，也是一名德撲高手。

Dong Kim是今年1月德撲人機大戰中的一位人類選手，這位28歲的韓裔美國人回憶說，每一天Libratus都會進步，人類選手很難找到它的弱點或漏洞。即便找到一個，第二天就會消失不見。這讓他感到絕望。

但也許他根本就感覺錯了。「有人類玩家說找到了漏洞，其實不一定」，Brown對量子位說：「這可能是Libratus的一種戰術，去攪亂對手的策略」。

△ Brown身後是他的電腦

不能用人類的思維去衡量AI。讓Sandholm記憶猶新的是，1月的德撲人機大戰進行到尾聲，當時AI早已遙遙領先，所有人都認為Libratus會趨近於保守。

「但它反而越來越激進」，Sandholm說特別是最後幾局，非常出人意料。

比方，為了一個很小的底池推了All in，或者下注額只有底池的十分之一。「有時候Libratus的策略會被認為是臭手」，但事後復盤Sandholm說這個德撲AI嘗試了很多令人叫絕的方法，其中包括各種策略的詐唬。

詐唬也不是人教的，而是機器自己學會的。

怎麼學？「詐唬是特別重要的技能，系統在學習中發現，如果有一手爛牌，直接詐唬能贏更多，所以它就學會了」，Brown告訴量子位。

「這就是AI特別奇妙的地方」，Brown坐在自己CMU標配的上一代Aeron座椅上說，「很多人看到Libratus能詐唬，覺得很了不起」，但在這位博士的眼中，詐唬這種看似與心理有關的人類技能，機器是可以通過演算法學會的。

三個模塊

為什麼Libratus能比前代更厲害，進步在何處？Brown舉了兩個例子。

比如，對於K-High Flush(最大牌為K的同花)和Q-High Flush(最大牌為Q的同花)，這兩手牌對於Claudico來說是等值的，而Libratus則會做一個精確的區分。實際上，Libratus會對每一手牌進行單獨的處理，根據不同的牌面制訂出不同的戰略。

再比如，對於250元的下注，是當成200元還是300元來計算？那麼249或者251呢？實際上，Libratus不會嘗試聚類，而是馬上實時計算，得出勝算最大的策略。

△ Sandholm講解冷撲大師

Sandholm則從全局的角度，打開Libratus的大腦，向量子位逐一講解了構成這個撲克AI的三個主要模塊。其中一個用於賽前，兩個用於賽中。

模塊一：Nash equilibrium approximation before competition(賽前納什均衡近似)

這個模塊把最重要的博弈信息進行抽取，比如針對某一手牌對應的戰略，然後再應用強化學習等方法，繼續尋求提高和改進。這裡使用了一個新的演算法：蒙特卡洛反事實遺憾最小化。在這個模型的幫助下，Libratus自己學會了德撲，而且比以前速度更快。

模塊二：Endgame solving(殘局解算)

這是Libratus最重要的部分，Sandholm說。實際上Claudico也有這個模塊，但那個版本幾乎不起作用。而新的版本不會再給對手留下漏洞，這個過程不斷進行，對手新出一招後，會繼續展開新的殘局解算，這被稱為Nested Endgame Solving。

德撲這類不完美信息博弈，不能拆解為可以獨立解決的子博弈。所以Libratus採用的殘局解算的方法應對，想進一步深究，可以查看Brown和Sandholm的論文。

模塊三：Continual self-improvement(持續自我強化)

比賽中人類高手會尋找Libratus的漏洞，並展開有針對性的攻擊。這個模塊的作用就是發現問題所在，找到更多細節進行自我強化，然後得到一個更好的納什均衡。

「三個模塊都用了新的演算法」，Sandholm說第一個模塊的新演算法能夠抽取更多的細節，而且比原來的演算法更快；第二個模塊的演算法是全新的；而第三個模塊則有一個全新的理念，有點類似於：防守是最好的進攻。

Libratus不再尋求發現並利用人類對手的漏洞，相反，這個AI開始觀察人類發現了它什麼弱點，然後有針對性的彌補和提升。於是Libratus的弱點越來越少，直到人類玩家沮喪的發現，想要贏下比賽變成一件幾乎不可能完成的任務。

不主動進攻就很少露出破綻，李天放說跟Libratus對戰就像打一堵牆，最好的結果可能就是打個平手，基本不可能獲勝。納什均衡本身，追求的就是一種平衡。

Libratus是一個防守大師。

深度學習不是唯一

與圍棋大師AlphaGo相比，Libratus有很多不同之處。其中就包括：Libratus並沒有使用目前相當火熱的深度學習技術。

「深度學習是個非常好的技術，但我們沒有在這個項目應用，是因為深度學習不能給出絕對的保證。比方識別貓的圖像，對於給定的圖片能得出95%是貓，但也不是絕對的保證，而我們的演算法，能夠保證最優異的結果」，Sandholm說。

當然也有團隊在用深度學習來搞德撲AI。

來自加拿大阿爾伯塔大學、捷克布拉格查理大學和捷克理工大學的研究人員，基於深度學習技術開發出德州撲克人工智慧DeepStack。

對於兩個德撲AI來說，還沒有更好的比較方法，目前只能說Libratus擊敗的對手，要比DeepStack的對手水平更高。其他這裡不展開討論了，這個團隊也發表了相關的論文。

「對這一類型的任務，我們的方案比深度學習更好」，Sandholm對量子位表示，目前深度學習的方案實際上沒有解決問題，而Libratus這個系統「時間越長，越能接近完美」。

對於這個問題，我們詢問了CMU機器學習系的邢波教授，他指出還不應過早的下結論說：深度學習就是機器學習的未來。

「Sandholm教授其實不是做深度學習的，他用的方法實際上被認為是是傳統的AI，但是可以達到這麼強大的功能」，邢波對量子位表示這是一個有力的證明：人工智慧並不等於深度學習，很多新的方法需要探索和了解。

Libratus戰績回顧

今年1月，在匹茲堡河流賭場舉辦了一場為期20天的Brains vs. AI比賽，Libratus在一對一、無限注的德撲人機大戰中，擊敗四位頂級人類玩家，累計贏得176.6萬美元籌碼。按照德撲的術語，Libratus與人類高手的差距是147大盲注/千手(mbb/hand)，也就是場均14.7個大盲注。

今年4月，創新工場董事長兼CEO、創新工場人工智慧工程院院長李開復，邀請Libratus和團隊來到中國，以「冷撲大師」之名與「龍之隊」展開對決。

這場為期五天的對決中，冷撲大師以領先792327記分牌、每百手領先15.8大盲注的成績擊敗人類對手。贏得200萬獎金。

當時李開復表示，AI在征服了以不完美信息博弈為內核的德州撲克後，AI在遊戲領域比人類更強已經沒有任何懸念了。人機大戰的結果證明AI比我們想像中來的更快，接下來要關注的應該就是AI在商業、醫療等領域的應用。

— 完 —

歡迎大家關注我們的專欄：量子位 - 知乎專欄

誠摯招聘

量子位正在招募編輯/記者，工作地點在北京中關村。期待有才氣、有熱情的同學加入我們！相關細節，請在量子位公眾號(QbitAI)對話界面，回復「招聘」兩個字。

量子位 QbitAI · 頭條號簽約作者

?? ? 追蹤AI技術和產品新動態

推薦閱讀：