NIPS 最佳論文視頻解讀！德州撲克背後的不完全信息博弈

4 人贊了文章

美國時間， 2017 年 12 月 4 日 8:00。

全球機器學習頂級會議 NIPS 在美國長灘開幕了。

本年度 NIPS 將持續一周，你現在才想參加肯定來不及，因為票早就賣光了。

為了讓你隔著太平洋都能跟上 NIPS 的節奏，今天帶你搶先看 NIPS 2017 的最佳論文。這篇 NIPS Talk 的時間是美國時間 12 月 5 日下午 2:50。

Safe and Nested Subgame Solving for Imperfect-Information Games

安全和嵌套子遊戲解決不完全的信息博弈

不跨洋不翻牆，點擊觀看視頻，輕鬆解讀 NIPS 2017 最佳論文！

那些關注過人機大戰的朋友們，你們肯定知道這篇論文在講什麼。

不方便打開視頻的朋友們，可以看看簡版圖文：

今年年初，4 位頂尖德州撲克選手，在為期 20 天賽程里，與卡耐基梅隆大學（CMU）研發的人工智慧系統 Libratus 對決 12 萬手，爭奪 20 萬美元獎金池。

最終，Libratus 擊潰了這組職業選手。Libratus 人工智慧系統所用到的策略技巧，就是這篇論文的重點內容。

論文將德州撲克之類的遊戲所運用的技巧，定義為一種不完美的信息博弈互動策略。這種互動策略不僅可以應用於遊戲中，還能應用在談判、拍賣、網路安全以及人身安全上。

為什麼不能將 Alphago 或者 DeepBlue2 的技術應用在德州撲克上呢？

這裡有幾個原因，其中最重要的一個原因是，所有的完美遊戲（例如五子棋、國際象棋）都有一種特性，那就是，當你採取一些行動時，你的對手也採取了一些行動，當你發現自己身處一個特別的子博弈環境時，完全可以忽略其它不相關的情況，決策點與最佳策略直接相關，你唯一需要做的事情就是，確定當前的決策點。

但是德州撲克是一種不完美遊戲，當你處在一個特定的子博弈中時，隨即又會出現其他的子博弈，你不能從這個決策點出發，因為其他子博弈會影響你當前子博弈的最佳策略。換句話說，當在不完美的信息博弈中進行決策時，你必須考慮到這個博弈的全局策略，而並非子博弈的最佳策略。

過去，我們的策略都是預先計算出來的，2015 年有人就在小型的德州撲克程序庫中簡單預先計算了整個博弈的最佳策略。但情況不總是這麼簡單，一旦遇到計算量龐大的遊戲就最佳策略失靈了。

研究者針對不限注德州撲克做了相關的研究，針對整個遊戲的玩法做了近似計算，在真實的不限注德州撲克中，發現了針對性的子博弈策略，這個技術叫做「嵌套的子博弈」。

在博弈樹下重複這個過程，會發現我們還處在另一個子博弈中，再次找到一個更好的針對性的子博弈策略。通過這個技術，能夠和已經計算出的全局藍圖進行很好的擬合。

所以你看，相比於之前的方法，不完美信息博弈的子博弈求解技術，有著更強的理論保證和更好的實際表現。同時，作者還展示了安全與非安全的子博弈求解技術，以及為嵌套子博弈求解引入了新方法。

Poker AI Libratus幕後的研究者：

卡耐基梅隆大學(MCU)Tuomas Sandholm 教授和他的學生 Noam Brown 是本篇論文的作者。更多幕後故事可以看 AI 科技評論報道德州撲克演算法幕後研發者CMU博士Brown專訪：AI如何打敗頂級人類牌手？

Tuomas Sandholm 是 CMU 計算機科學系教授，他在人工智慧和自動談判領域，研究超過 28 年。最早的成績要追溯到 1989 年前後，他做了一套自動為卡車司機談判並分配任務的系統。

近年來，Sandholm 和他的團隊成績顯赫，多次在國際機器學習會議（ICML）、人工智慧會議（AAAI）獲獎，現在 Sandholm 還拿到 NSF(美國國家科學基金會)一筆為期三年的新投資，用以資助他繼續基於 AI Libratus 展開相關研究。

Noam Brown 是 Sandholm 的博士生，他的研究將強化學習和博弈論結合起來，在大量不完美信息多智能體交互中，做出能夠進行戰略推理的 AI。

Brown 把他的研究應用導 AI Libratus 身上，AI Libratus 在不限注的撲克中擊敗頂級人類選手。他還曾創建了 Libratus 的前身 Claudico 以及 Baby Tartanian8、Tartanian7，都在近兩年的計算機撲克大賽中獲勝。

11 月 29 日，Noam Brown 在自己的 Twitter 上炫耀了一波，說拿了最佳論文，NIPS Talk 的時間是 12 月 5 日下午 2:50，邀請大家來跟 Poker AI Libratus 一決高下。

學霸們想了解更多，可以打開更新版的論文原文：

https://www.cs.cmu.edu/~sandholm/safeAndNested.aaa17WS.pdf

翻譯 / 餘杭

整理 / 吳璇

微信：AI 科技評論（ID：aitechtalk）

推薦閱讀 ：

德州撲克演算法幕後研發者CMU博士Noam Brown專訪：AI如何打敗頂級人類牌手？

CMU 邢波教授團隊最新成果：利用 AI 自動生成醫學影像報告

CMU風頭被搶，新型DeepStack演算法搶先攻克德州撲克圖靈測試

推薦閱讀：