一文讀懂人工智能打德?lián)?，詳解阿爾法狗未來?huì)是什么樣？

攻克圍棋后，什么是AI的下一個(gè)征程？打撲克！相比信息完全可見的圍棋，能夠猜疑、虛張聲勢(shì)的德?lián)湟щy得多。冷撲大師Libratus是首個(gè)在無限手一對(duì)一德?lián)渲袘?zhàn)勝人類職業(yè)玩家的AI，相關(guān)論文也在NIPS 2017獲得了最佳論文獎(jiǎng)。不過，這篇論文不是一般的難！本文中，鄧侃博士將從納什均衡策略、反事實(shí)最佳策略等4個(gè)方面，生動(dòng)舉例，帶你讀懂人工智能如何打德?lián)洹?br />
真實(shí)的生活，（不會(huì)像圍棋那樣）可以毫無遮攔地洞察整個(gè)棋局。真實(shí)生活中充斥著虛張聲勢(shì)、欺詐、揣度對(duì)方心理。這才是我所研究的博弈。

——馮·諾依曼

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

CMU 教授 Tuomas Sandholm 及其學(xué)生 Noam Brown 所開發(fā)的人工智能德?lián)湎到y(tǒng) Libratus，被國(guó)內(nèi)同行翻譯成 “冷撲大師”。冷撲大師在 2017年1月，與四位德?lián)渎殬I(yè)高手對(duì)陣，大獲全勝，贏得了接近總數(shù)的籌碼 [1]。

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

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

1. 這篇論文非常不好懂。光數(shù)學(xué)符號(hào)的定義，就整整占了一節(jié)內(nèi)容。數(shù)學(xué)符號(hào)定義結(jié)束后，是很大篇幅的定理證明。初讀一遍，云里霧里。

2.非熱門的理論根基。當(dāng)下熱門的機(jī)器學(xué)習(xí)領(lǐng)域，是深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)。而這篇論文的理論根基，是博弈論和運(yùn)籌學(xué)。

3. 方法論的通用性。若干讀者認(rèn)為，冷撲大師的算法，可能僅僅適用于德?lián)?，或者充其量能夠擴(kuò)展到其它棋牌類游戲。應(yīng)用前景有限。

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

11月8日，Tuomas Sandholm（中）來北京參加新智元舉辦的世界人工智能大會(huì)，餐敘時(shí)與新智元?jiǎng)?chuàng)始人兼CEO楊靜（左）和本文作者鄧侃博士交流

從方法論來說，冷撲算法的理論根基是博弈論和運(yùn)籌學(xué)。而強(qiáng)化學(xué)習(xí)學(xué)習(xí)的理論根基是馬爾科夫決策過程和動(dòng)態(tài)規(guī)劃。雖然來源不同，但是終將殊途同歸。

冷撲算法與強(qiáng)化學(xué)習(xí)和深度學(xué)習(xí)殊途同歸之日，必將大放異彩。

馮·諾依曼曾經(jīng)這樣說，“真實(shí)的生活，（不會(huì)像圍棋那樣）可以毫無遮攔地洞察整個(gè)棋局。真實(shí)生活中充斥著虛張聲勢(shì)、欺詐、揣度對(duì)方心理。這才是我所研究的博弈?！?/p>

讀懂冷撲大師這篇最佳論文，關(guān)鍵是理解四個(gè)概念，

1. 納什均衡策略，

2. 反事實(shí)最佳策略，

3. 抽象，

4. 終局。

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

目前冷撲大師只會(huì)打雙人德?lián)洹．?dāng)然，把算法改進(jìn)一下，多用幾核 GPU，也可以打多人德?lián)洹?/p>

打德州撲克時(shí)，先發(fā)給每個(gè)牌手兩張暗牌，然后陸續(xù)發(fā) 5 張明牌，期間 4 輪下注，最后比大小 [3]。

德?lián)潆y在揣摩對(duì)手的兩張暗牌。公開的信息，是 5 張明牌和雙方下注的歷史。但是，對(duì)方不會(huì)嚴(yán)格按照自己手中的暗牌來下注，而是有意夾雜著各種誤導(dǎo)戰(zhàn)術(shù)，譬如虛張聲勢(shì)等等。

冷撲大師是如何識(shí)別對(duì)手的下注策略呢？

其實(shí)，冷撲大師不推測(cè)對(duì)手的下注策略。

稍微具體一點(diǎn)，冷撲大師追求的目標(biāo)，是能夠達(dá)到納什均衡（Nash Equilibrium）的策略。納什，就是著名的數(shù)學(xué)家，電影《美麗心靈》的男主角。納什均衡策略，是不讓對(duì)方占便宜的策略。

納什均衡策略是被動(dòng)的防御策略，而不是主動(dòng)的進(jìn)攻策略。也就是說，納什均衡策略不揣度對(duì)手的下注策略。

舉個(gè)例子，假如對(duì)方的策略，是不論自己手上的暗牌是什么，不動(dòng)腦子地一味跟著我方下注。打了幾手以后，即便我方發(fā)現(xiàn)了對(duì)方的策略，根據(jù)納什均衡，我方也不會(huì)趁自己牌好時(shí)，冒進(jìn)地抬高賭注，賺對(duì)方便宜。

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

理論上說，納什均衡策略能夠保證，在經(jīng)過了多次牌局?jǐn)P除了運(yùn)氣的成分后，是不存在被對(duì)方利用的漏洞的。

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

如何尋求最佳下注策略？先做一個(gè)下注對(duì)應(yīng)表

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

我們不妨做一張下注對(duì)應(yīng)表（Action Mapping），七列，若干行。

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

• 第二列：牌桌上已經(jīng)發(fā)了的明牌，最多有 5 張明牌

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

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

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

• 第五列：對(duì)方手上的兩張暗牌

• 第六列：我方?jīng)Q定馬上要下注的籌碼數(shù)量

• 第七列：對(duì)應(yīng)第六列決策的收益

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

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

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

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

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

第三列下注及其歷史，組合數(shù)量就更多了。所以，這張表的行數(shù)巨大，論文上說是 10^165 行。這個(gè)數(shù)量級(jí)太大了，即便用當(dāng)今世界最強(qiáng)大的云計(jì)算系統(tǒng)，估計(jì)也得算上幾十年。

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

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

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

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

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

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

這個(gè)問題比較復(fù)雜，因?yàn)閷?duì)方下注，不僅僅依據(jù)對(duì)方手里的暗牌和桌面的明牌，而且，對(duì)方會(huì)根據(jù)我方下注的歷史，來估算我方手里的暗牌。

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

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

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

面對(duì)各種局面（InfoSet），也就是前述的局面下注對(duì)應(yīng)表的前四列，先假設(shè)我方以隨機(jī)均等概率選擇下注策略。這樣經(jīng)過一系列發(fā)牌和下注，牌局結(jié)束，然后清點(diǎn)我方的收益或損失。

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

然后悔牌。面對(duì)某種特定局面，也就是固定住對(duì)應(yīng)表的前四列，換句話說，也就是我方有特定的兩張暗牌，桌面上有最多五張?zhí)囟ǖ拿髋?，再加上特定的下注歷史?；谂频囊馑际?，面對(duì)某種特定局面，我方不隨機(jī)選擇下注策略，而是只認(rèn)定一種下注方式，譬如跟注（call）。

悔牌以后，后續(xù)亮出的明牌，不會(huì)改變。但是我方和對(duì)方，后續(xù)下注的歷史會(huì)發(fā)生改變。

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

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

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

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

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

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

以上是第一輪模擬和悔牌，然后進(jìn)行第二輪模擬。

第二輪模擬時(shí)，先假設(shè)對(duì)方仍然按照隨機(jī)均等的概率，選擇下注策略。而我方根據(jù)第一輪更新后的下注對(duì)應(yīng)表，選擇下注決策。

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

1. 先根據(jù)當(dāng)前的局面，也就是暗牌明牌加下注歷史，找到更新后的下注對(duì)應(yīng)表中，所有相應(yīng)的行。

2. 更新后的下注對(duì)應(yīng)表中，第六列是下注策略，第七列是平均收益。根據(jù)平均收益，選擇下注策略。收益越高，相應(yīng)下注策略被選中的概率越高。

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

然后，悔牌。并再做一個(gè)下注對(duì)應(yīng)表，記錄面對(duì)各種局面時(shí)，各種下注策略的平均收益。

第三輪模擬時(shí)，我方用第二版下注對(duì)應(yīng)表，對(duì)方用第一版下注對(duì)應(yīng)表。經(jīng)過多次模擬過程，得到第三版下注對(duì)應(yīng)表。

如此重復(fù)迭代。經(jīng)過多輪模擬迭代以后，所得到的下注對(duì)應(yīng)表，將是逼近納什均衡的最佳策略。

簡(jiǎn)化牌局，降低計(jì)算負(fù)擔(dān)

如第三節(jié)所述，下注對(duì)應(yīng)表中，單單第一列和第二列的組合，就高達(dá) 57,437,016,000 種。如果在加上各種可能的下注歷史，那么下注對(duì)應(yīng)表的行數(shù)，是 10^165 數(shù)量級(jí)。

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

下注對(duì)應(yīng)表的行數(shù)太多，反事實(shí)最佳策略算法的模擬次數(shù)太多，導(dǎo)致計(jì)算量太大，難以承受。

一個(gè)顯而易見的解決辦法，是簡(jiǎn)化牌局（Abstraction），以便精簡(jiǎn)下注對(duì)應(yīng)表的行數(shù)。

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

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

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

DeepStack對(duì)牌面進(jìn)行抽象，詳見[5]

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

經(jīng)過抽象后，牌局組合的總數(shù)，被大大降低。譬如 [4] 把總數(shù)為 10^165 的牌局組合，簡(jiǎn)化到 10^12。

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

終局，誤算與精算

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

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

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

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

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

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

現(xiàn)在給定一個(gè)特定的下注歷史，我們可以通過查找下注對(duì)應(yīng)表，計(jì)算出每一步下注的概率。所謂下注歷史，就是一連串的下注，下注歷史的概率，就是一連串概率的乘積。

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

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