攻克圍棋后，什么是AI的下一個征程？打撲克！相比信息完全可見的圍棋，能夠猜疑、虛張聲勢的德撲要困難得多。冷撲大師Libratus是首個在無限手一對一德撲中戰勝人類職業玩家的AI，相關論文也在NIPS 2017獲得了最佳論文獎。不過，這篇論文不是一般的難！本文中，鄧侃博士將從納什均衡策略、反事實最佳策略等4個方面，生動舉例，帶你讀懂人工智能如何打德撲。

真實的生活，（不會像圍棋那樣）可以毫無遮攔地洞察整個棋局。真實生活中充斥著虛張聲勢、欺詐、揣度對方心理。這才是我所研究的博弈。

——馮·諾依曼

冷撲大師 Libratus 與“冷門” NIPS 2017 最佳論文

CMU 教授 Tuomas Sandholm 及其學生 Noam Brown 所開發的人工智能德撲系統 Libratus，被國內同行翻譯成 “冷撲大師”。冷撲大師在 2017年1月，與四位德撲職業高手對陣，大獲全勝，贏得了接近總數的籌碼 [1]。

2017年11月，Noam Brown 與 Tuomas Sandholm 合著的論文，“Safe and Nested Endgame Solving for Imperfect-Information Games”，獲得 NIPS 2017 最佳論文獎 [2]。

但是這篇最佳論文，在國內業界引起的討論，似乎不算特別熱烈。原因可能有三條，

1. 這篇論文非常不好懂。光數學符號的定義，就整整占了一節內容。數學符號定義結束后，是很大篇幅的定理證明。初讀一遍，云里霧里。

2.非熱門的理論根基。當下熱門的機器學習領域，是深度學習和強化學習。而這篇論文的理論根基，是博弈論和運籌學。

3. 方法論的通用性。若干讀者認為，冷撲大師的算法，可能僅僅適用于德撲，或者充其量能夠擴展到其它棋牌類游戲。應用前景有限。

11月8日，Tuomas Sandholm 來北京參加新智元舉辦的世界人工智能大會AI World 2017，并做主題演講。餐敘時，Sandholm 教授對筆者說，從應用前景來說，冷撲大師的算法，不僅可以用于賭博，也可以用于談判，拍賣定價，投資決策等等。

11月8日，Tuomas Sandholm（中）來北京參加新智元舉辦的世界人工智能大會，餐敘時與新智元創始人兼CEO楊靜（左）和本文作者鄧侃博士交流

從方法論來說，冷撲算法的理論根基是博弈論和運籌學。而強化學習學習的理論根基是馬爾科夫決策過程和動態規劃。雖然來源不同，但是終將殊途同歸。

冷撲算法與強化學習和深度學習殊途同歸之日，必將大放異彩。

馮·諾依曼曾經這樣說，“真實的生活，（不會像圍棋那樣）可以毫無遮攔地洞察整個棋局。真實生活中充斥著虛張聲勢、欺詐、揣度對方心理。這才是我所研究的博弈。”

讀懂冷撲大師這篇最佳論文，關鍵是理解四個概念，

1. 納什均衡策略，

2. 反事實最佳策略，

3. 抽象，

4. 終局。

冷撲大師的算法與納什均衡策略：不讓對方占便宜

目前冷撲大師只會打雙人德撲。當然，把算法改進一下，多用幾核 GPU，也可以打多人德撲。

打德州撲克時，先發給每個牌手兩張暗牌，然后陸續發 5 張明牌，期間 4 輪下注，最后比大小 [3]。

德撲難在揣摩對手的兩張暗牌。公開的信息，是 5 張明牌和雙方下注的歷史。但是，對方不會嚴格按照自己手中的暗牌來下注，而是有意夾雜著各種誤導戰術，譬如虛張聲勢等等。

冷撲大師是如何識別對手的下注策略呢？

其實，冷撲大師不推測對手的下注策略。

稍微具體一點，冷撲大師追求的目標，是能夠達到納什均衡（Nash Equilibrium）的策略。納什，就是著名的數學家，電影《美麗心靈》的男主角。納什均衡策略，是不讓對方占便宜的策略。

納什均衡策略是被動的防御策略，而不是主動的進攻策略。也就是說，納什均衡策略不揣度對手的下注策略。

舉個例子，假如對方的策略，是不論自己手上的暗牌是什么，不動腦子地一味跟著我方下注。打了幾手以后，即便我方發現了對方的策略，根據納什均衡，我方也不會趁自己牌好時，冒進地抬高賭注，賺對方便宜。

納什均衡策略，不揣度對方的策略。但是，對方會不會尋找納什均衡策略的漏洞？

理論上說，納什均衡策略能夠保證，在經過了多次牌局擯除了運氣的成分后，是不存在被對方利用的漏洞的。

問題是，冷撲大師的算法，是不是嚴格意義上的納什均衡策略？這篇論文，之所以大段大段證明數學定理，目的就是為了證明，至少在一對一的情況下，冷撲大師的算法，是逼近納什均衡策略的。

如何尋求最佳下注策略？先做一個下注對應表

既然納什均衡策略不揣度對手的下注策略，那么就可以用機器自我博弈的辦法，盡可能枚舉各種可能的牌局，尋求最佳的下注策略。

我們不妨做一張下注對應表（Action Mapping），七列，若干行。

• 第一列：我方手中的兩張暗牌

• 第二列：牌桌上已經發了的明牌，最多有 5 張明牌

• 第三列：雙方下注的歷史

• 第四列：我方手上剩下的籌碼

其實，可以通過第三列（雙方下注的歷史）來推算第四列（我方手上剩下的籌碼）。設置第四列的目的，是為了方便。

• 第五列：對方手上的兩張暗牌

• 第六列：我方決定馬上要下注的籌碼數量

• 第七列：對應第六列決策的收益

前四列是輸入，論文中被稱為局面（Information Set，InfoSet）。后三列是輸出，分別是推測、決策和收益。

假如我們有足夠的計算能力，我們枚舉各種可能的局面（InfoSet）。

第一列，我方手上兩張暗牌（pre-flop），總共有 (52 * 51) / (2 * 1) = 1,326 種組合。

第二列，先發三張明牌（flop），總共有 (50 * 49 * 48) / (3 * 2 * 1) = 19600 種組合。然后，再兩次發單牌（turn、river）。加起來，總共有 19600 + 19600 * 47 + 19600 * 47 * 46 = 43,316,000 種組合。

如果把第一列和第二列的所有組合加在一起，那么總數是 1,326 * 43,316,000 = 57,437,016,000。

第三列下注及其歷史，組合數量就更多了。所以，這張表的行數巨大，論文上說是 10^165 行。這個數量級太大了，即便用當今世界最強大的云計算系統，估計也得算上幾十年。

不過，假如我們有足夠的計算能力，能夠遍歷出這張表，那么我們就可以計算出面對特定的牌局，各種下注決策對應的平均收益。

譬如，發完全部 5 張明牌之后（river），對方手里的兩張暗牌，總共有 (45 * 44) / (2 * 1) = 990 種組合。又假如，前三輪下注（pre-flop, flop, turn），總共有 N 種下注歷史。這時候如果輪到我方下注，每一種下注策略，譬如下注手頭剩下的全部籌碼（all in），將面臨 990 * N 種可能的收益。這 990 * N 種收益的平均值，就是這種下注策略的平均收益。

面對特定的牌局，我們計算出了各種下注決策對應的平均收益以后，就可以找出平均收益最高的那種下注決策。

平均收益最高的那種下注決策，是否就是納什均衡策略？不是。

原因是，當對方手里的暗牌的牌力很低時，譬如對方手里的兩張暗牌是一張紅桃三一張梅花六（3h6c），對方大金額下注的概率很低。

那么，如何估算對方下注策略的概率？

這個問題比較復雜，因為對方下注，不僅僅依據對方手里的暗牌和桌面的明牌，而且，對方會根據我方下注的歷史，來估算我方手里的暗牌。

反事實最佳策略：尋找納什均衡策略的流行算法

反事實最佳策略（Counterfactual Best Response, CBR )，是一種近年來比較流行的，尋找納什均衡策略的算法 [4]。

反事實最佳策略有三大要素：1. 模擬，2. 悔牌（regret），3. 迭代（iteration）。

面對各種局面（InfoSet），也就是前述的局面下注對應表的前四列，先假設我方以隨機均等概率選擇下注策略。這樣經過一系列發牌和下注，牌局結束，然后清點我方的收益或損失。

這樣模擬幾億次牌局，大致覆蓋各種可能的局面。

然后悔牌。面對某種特定局面，也就是固定住對應表的前四列，換句話說，也就是我方有特定的兩張暗牌，桌面上有最多五張特定的明牌，再加上特定的下注歷史。悔牌的意思是，面對某種特定局面，我方不隨機選擇下注策略，而是只認定一種下注方式，譬如跟注（call）。

悔牌以后，后續亮出的明牌，不會改變。但是我方和對方，后續下注的歷史會發生改變。

把剛才幾億次牌局，重新模擬一遍。重新模擬時，雙方暗牌和桌面上的明牌不變，發牌順序不變，悔牌以前的下注歷史不變，但是悔牌以后的下注歷史改變。每次下注時，除了悔牌那個特定策略，其余的下注策略不變。

這樣重新模擬了一次以后，就可以計算出悔牌的策略，平均收益是多少。

然后換一種悔牌策略，也就是面對同樣局面，只認定另一種下注方式。譬如前一次悔牌的策略是跟注（call），這一次模擬的悔牌策略，改為加碼（raise），然后把剛才幾億次牌局，重新模擬第二遍。這樣就可以計算出第二種悔牌策略的平均收益。

模擬了若干次以后，就可以估算出，面對同樣的局面，各種可能的悔牌策略，及其平均收益。

重復以上模擬過程，確定各種局面的各種策略，及其平均收益。

然后，更新下注對應表（Action Mapping）。先清空表中第五列，也就是不枚舉對方手上的兩張暗牌。然后在第七列，填入每一種下注策略的平均收益。

以上是第一輪模擬和悔牌，然后進行第二輪模擬。

第二輪模擬時，先假設對方仍然按照隨機均等的概率，選擇下注策略。而我方根據第一輪更新后的下注對應表，選擇下注決策。

面對同樣一個局面，也就是表中的前四列，我方按以下方式選擇下注策略。

1. 先根據當前的局面，也就是暗牌明牌加下注歷史，找到更新后的下注對應表中，所有相應的行。

2. 更新后的下注對應表中，第六列是下注策略，第七列是平均收益。根據平均收益，選擇下注策略。收益越高，相應下注策略被選中的概率越高。

這樣，確定了第二輪模擬的暗牌明牌，發牌順序，以及我方和對方最初下注歷史。

然后，悔牌。并再做一個下注對應表，記錄面對各種局面時，各種下注策略的平均收益。

第三輪模擬時，我方用第二版下注對應表，對方用第一版下注對應表。經過多次模擬過程，得到第三版下注對應表。

如此重復迭代。經過多輪模擬迭代以后，所得到的下注對應表，將是逼近納什均衡的最佳策略。

簡化牌局，降低計算負擔

如第三節所述，下注對應表中，單單第一列和第二列的組合，就高達 57,437,016,000 種。如果在加上各種可能的下注歷史，那么下注對應表的行數，是 10^165 數量級。

另外，用反事實最佳策略算法，來尋找納什均衡策略，需要經過幾十億次模擬。

下注對應表的行數太多，反事實最佳策略算法的模擬次數太多，導致計算量太大，難以承受。

一個顯而易見的解決辦法，是簡化牌局（Abstraction），以便精簡下注對應表的行數。

譬如，一個對子，紅桃八和黑桃八（8h8s），與另一個對子，方片八和梅花八（8d8c），這兩個對子的牌力，是相似的。所以，可以把兩個八的對子，總共 (4 * 3) / (2 * 1) = 6 種組合，都簡化成下注對應表中的一行。

但是牌力的計算，需要很仔細，譬如一對八，與一個八一個九，哪一種組合的牌力大？假如 5 張明牌分別是七、十、勾、外加兩張散牌，那么一個八一個九可以與明牌組合成從七到勾的順子，而一對八與五張明牌的最大組合，仍然是一對八。

所以，牌力的計算，不僅要看牌面本身的大小，而且要枚舉兩張暗牌，與 5 張明牌的各種可能的組合。[5] 詳細講述了牌力的計算方法。另外，也講述了如何根據牌力，對牌面進行抽象的做法（Card Abstraction）。

DeepStack對牌面進行抽象，詳見[5]

不僅對牌面要進行抽象，而且對下注也要進行抽象，譬如只允許四種下注方式，棄牌（fold）、跟注（call）、加碼（raise）、孤注一擲（all in）。

經過抽象后，牌局組合的總數，被大大降低。譬如 [4] 把總數為 10^165 的牌局組合，簡化到 10^12。

牌局組合總數降低后，反事實最佳策略模擬迭代，就可行了。

終局，誤算與精算

但是，簡化牌局，會導致誤算。譬如根據牌力，我們把一對七與一對八，歸為同一種局面。但是，假如雙方一路對賭到底，誰也不中途棄牌（fold），只好最后亮牌（showdown）。

亮牌的時候，我方一對七，對方一對八，雖然牌力區別微小，但是卻決定最終勝負。這就是所謂誤算（Off-tree Problem）。

解決誤算的辦法，是用精算（re-solving）來替代抽象（abstraction）。

精算的核心，是通過擬合雙方下注歷史，來反向推算對方手里的兩張暗牌，及其概率。

假設我方的兩張暗牌是 h1，對方的兩張暗牌是 h2。又假設我方和對方，都按照反事實最佳策略來下注，那么就可以通過查找下注對應表，推算出各種下注策略的概率。

譬如，pre-flop 時，我方的暗牌是一對八，對方的暗牌是一對 A。假如首次下注由我方開始，我方加碼（raise）的概率很大，但是 all-in 的概率幾乎為 0。但是對方 all-in 的概率，會比 0 大很多。

現在給定一個特定的下注歷史，我們可以通過查找下注對應表，計算出每一步下注的概率。所謂下注歷史，就是一連串的下注，下注歷史的概率，就是一連串概率的乘積。

通過計算下注歷史的概率，我們不僅可以估算對方手里的暗牌，而且還可以估算對方背離正常的下注策略的幅度和波動，也就是說，我們能夠估算得出對方虛張聲勢（bluffing）的概率。

估算出了對方的暗牌，以及對方 bluffing 的概率，終局的精算，就比較容易了。無非是把對方的暗牌，與我方的暗牌相比較，推算出我方勝出的概率，以此決定下注的金額。