「冷撲大師」 (Libratus) 是如何利用博弈論打德撲的？

新聞背景：國內首次德撲人機大戰明日開打，人類勝率不足10%_科技_騰訊網

「冷撲大師」是基於卡內基梅隆大學Tuomas Sandholm教授和博士生Noam Brown所開發的Libratus無限德州撲克人工智慧系統。今年1月份在美國匹茲堡的比賽中，將四位職業選手挑落馬下，贏走接近總數的籌碼。

李開復介紹，「冷撲大師」並不基於大數據、深度學習、強搜索等傳統AI方法；而是基於博弈論，結合大量的數學和概率，直接在比賽同時動態優化勝率最高的數學模型。

相關問題：

如何看待人工智慧系統 Libratus 戰勝四位德州撲克頂級選手，獲得最終勝利？

中國德州撲克龍之隊對戰「冷撲大師」Libratus 的人機大戰有哪些看點？

謝邀！

首先跟大家簡單介紹下納什均衡的概念--- 納什均衡是指一個策略組，任何玩家都無法通過單方面的改變策略來增加收益。納什均衡策略組中的每個玩家的策略都是對策略組中其他策略的最佳反應。納什均衡策略組很重要，因其在兩人零和博弈中有額外的屬性。在兩人零和博弈中,若某玩家從納什均衡策略組中選中一個策略，其他玩家改變策略不會獲得更大的收益。 而在大部分Poker AI 中都是希望求解出來的策略組跟真正的納什均衡足夠的近記為。 所以這樣策略組的exploitability 是足夠小的，在假定對手有足夠能力的來利用我的缺點（given sufficient exploitative power）的情況下，我的策略也是可行的。

介紹完納什均衡後，我們可能在想怎麼求解德州撲克中的納什均衡，接著介紹用來求解均衡的CFR(Counterfactual regret minimization) 中文名字叫：虛擬遺憾最小化演算法。CFR來源於Regret matching 演算法，然而Regret Matching 演算法只能適用於正則博弈中，對於德州撲克這類擴展式博弈中無法直接使用Regret Matching, 通過定義Counterfactual Value在每一個Information Set 上進行Regret Matching來減少每一個Information Set 上的Immediate Regert,而Immediate regret的和是小於external regret.而external regret 跟 -nash equilibrium之間是有關係的，從而可以使用CFR來求解出納什均衡解。但是CFR的空間複雜度為 ,對於二人限制性的通過一些lossless abstraction 後就可以直接求解，對於二人非限制性（遊戲空間大概為 )根本無法直接求解，故先用abstraction 然後再CFR，大致的流程如下：

然而到了13年的時候Sam(Noam 的師兄，CMU的PHD) 首次將Endgame 的思想引入到了二人非限制性中來了上圖的框架變成了如下圖所示。

在Endgame 中agent 會根據玩家的在前幾輪的action，然後根據action所反映出來的手牌信息，對Endgame 進行實時求解。實時計算需要具備強大的計算能力，這也是為什麼Librauts在實際比賽中需要Brideges的原因。

上面就是Libratus 的part one- nash equilibrium approximation before the competition 和part two-Endgame solving 的簡單介紹，在實踐中會用到很多trick, 就拿CFR的改進來說--如何Sample, Warm start, Pruning 以及Thresholding等等。在Information Set abstraction 過程中如何選擇特徵進行聚類等等。

PS：有木有公司做poker AI方面的。

卡內基梅隆（CMU）大學在NIPS2017中公布了一些關鍵技術：

德州撲克AI(Libratus)的背後：不完美信息博弈中，求解安全嵌套的子博弈, #NIPS 2017最佳論文獎