作者丨王曲苑

學校丨西南大學博士生

研究方向丨人工智能、邊緣計算

近些年來，AI 取得長足進步的同時，游戲一直伴隨其左右，不論是Dota、星際、圍棋還是德州撲克都成為檢驗其發展程度的驗金石。2005 年 Michael Bowling 等人就在《Science》上發表《Heads-up limit hold’em poker is solved》，2018 年 Noam Brown 等人在《Science》發表《Superhuman AI for heads-up no-limit poker: Libratus beats top professionals》的論文研討如何用 AI 打德撲?[1-2]。
但是在以往工作中往往聚焦于只有兩位玩家的牌局，這在現實牌局中往往是不現實的，于是 Noam Brown 等人繼續研究如何用 AI 應對德撲多人牌局，其成果題為《Superhuman AI for multiplayer poker》發表于《Science》[3]，本文即對這篇論文進行簡要分析與解讀。

引言

撲克能作為 AI 和博弈論領域挑戰問題的原因很簡單：沒有別的休閑游戲能像撲克一樣要求人們優雅且高效地捕捉隱藏信息。雖然撲克僅僅被看為衡量 AI 和博弈論發展的驗金石，但是策略設置中隱藏信息帶來的挑戰絕不僅局限于這些休閑游戲中。
但是過去的 20 年間，所有利用 AI 打撲克的系統都只設置了 2 名玩家。設計一種針對多人牌局的超人類 AI 被普遍看做是 AI 發展的下一個關鍵節點。作者在這篇文章中描述了?Pluribus，一種能夠在 6 人牌局中打敗頂尖人類選手的新型 AI 系統。值得注意的是，這個系統是 18 年提出的 Libratus 系統的改進升級版。

多人博弈中的理論和實際挑戰

正如前文所說，目前 AI 在游戲領域取得的成績基均是基于雙人零和博弈模型，簡單來說就是兩人或兩隊“你贏我輸，我輸你贏”的模式。由于模型特性和納什均衡性質，我們可以證明：在雙人零和博弈模型中，倘若應用納什均衡策略則至少可以保證不輸，換言之，在雙人零和博弈模型中應用納什均衡策略是不可擊敗的（例如兩人進行石頭剪刀布游戲的納什均衡就是等概率出石頭剪刀布）。這也是之前那些 AI 算法取得成功的原因：不遺余力尋找納什均衡。

但是面對更復雜的問題，納什均衡就心有余而力不足了。目前還沒有一種能在多項式時間內找到雙人非零和博弈納什均衡的算法。就算是零和博弈，想找到 3 人或更多玩家零和博弈的納什均衡也是十分困難的。

即使在多人博弈中每個玩家都得到了納什均衡策略，這樣執行下來的結果未必是納什均衡的，Lemonade stand game?就是一個典型例子[4]。在 Lemonade stand game 中多個玩家同時在一個圓環上選擇位置，目標是距離別人越遠越好。這個博弈的納什均衡是每個玩家在圓環上均勻分布，能達到這樣效果的策略有無數多種，倘若每個玩家獨立計算一種，則產生的聯合策略不一定是納什均衡，如圖 1 所示。

納什均衡的短板引發了眾多科學家的思考：面對此類博弈問題，我們該如何解決。因此，作者認為在?6 人牌局中，我們的目標不應該是去尋找某一種特定的博弈理論求解，而是創建一個能夠以經驗為主的可以持續擊敗人類的 AI 系統。

因此作者提出了 Pluribus 系統，盡管在理論上作者無法保證最后的策略一定是納什均衡的，但是通過觀察實驗發現，所設計的 AI 系統能夠穩定地以某種強策略擊敗頂級人類玩家。雖然這樣的技術沒有足夠的理論支撐，但是仍然都夠在更為廣闊的領域產生更多超人策略。

Pluribus描述

Pluribus 策略核心是持續不斷地進行自學習自博弈，也就是說在這樣的訓練方式中，AI 系統之和自己的鏡像進行對抗，而不獲取任何人類游戲數據或先前的 AI 游戲數據。起初，AI 隨機選擇玩法，然后逐步改變其行動并確定行動的概率分布，最終，AI 的表現會取得明顯提升。

作者稱 Pluribus 利用自學習制定的離線策略為“藍圖策略”，隨著真實游戲的進行，Pluribus 通過在比賽中自己的實際情況實時搜索更好的策略來改進藍圖策略。

大規模不完全信息博弈抽象

無限制的德州撲克中有太多的決策點可以單獨推理。為了降低游戲的復雜性，作者消除了一些考慮因素并且將類似的決策點放在一起，這個過程稱之為抽象。在抽象之后，劃分的決策點被視為相同決策。作者在 Pluribus 中使用了兩種抽象：動作抽象和信息抽象。

動作抽象減少了 AI 所需要考慮的動作數。在無限制的德撲中，通常允許玩家在 100 刀至 10000 刀之間進行任意價格投注。但是，在現實情況中投注 200 刀和 201 刀幾乎沒有區別。

為了降低形成策略的復雜性，Pluribus 在任何給定的決策點只考慮幾種不同的下注大小。它所考慮的確切投注數量在 1 到 14 之間變化，具體取決于具體情況。但是對手并不局限于那些少數選項。如果對手下注 150 美元而 Pluribus 只接受過 100 美元或 200 美元的投注訓練，會發生什么？一般來說，Pluribus 會依賴于搜索算法實時對這種“離樹”行為產生相應。

信息抽象對于所揭示信息（如玩家的牌和顯示的牌）類似的決策點進行合并。舉例來說 10-high str AI ght 和 9-high str AI ght 在牌型上差距明顯，但是策略層面卻是相似的。Pluribus 可以將這些牌型放在一起并對其進行相同的處理，從而減少了確定策略所需的不同情況的數量。信息抽象大大降低了游戲的復雜性，但它可能會消除一些對于超人表現來說非常重要的微妙差異。因此，在與人類的實際比賽中，Pluribus 僅使用信息抽象來推斷未來下注輪次的情況，而不是實際所在的下注輪次。

通過改進型蒙特卡洛CFR來進行自學習訓練

Pluribus 所使用的藍圖策略是 CFR（counterfactual regret minimization）中的一種。CFR 是一種迭自學習訓練算法， AI 從完全隨機開始，通過學習擊敗其早期版本逐漸改進。過去 6 年間幾乎所有德撲 AI 都采用了 CFR 變形中的一種。在本文中，作者采用一種蒙特卡洛 CFR（Monte Carlo CFR） 方法對博弈樹上的行動進行采樣而不是在每次迭代時遍歷博弈樹。

在每次算法迭代中，MCCFR 指定一名玩家為遍歷者（traverser），他的當前策略將在迭代時更新。迭代開始時，MCCFR 會根據所有玩家的當前策略模擬一手牌。一旦模擬結束，AI 就會審查遍歷者做出的每個決定，并考慮如果采用其他可行行動會更好還是更差。接下來，AI 會考慮在其他可行行動之后可能做出的每個假設決策，考慮其行動更好還是更差，以此往復。博弈樹如圖 2 所示。

在本文中，探索其他假設結果是可能的，因為 AI 知道每個玩家的迭代策略，因此可以模擬在選擇其他行動時會發生什么。這種反事實推理是將 CFR 與其他自學習訓練算法（Alphago、Dota2、星際爭霸 2 等使用的）區分開來的重要特點之一。

遍歷者選擇某種行為應獲得的和實際所得的差值被添加到此次行動的后悔值中（counterfactual regret），這代表了在之前迭代中遍歷者沒有選擇該行動的后悔值，迭代結束時，更新遍歷者的策略使得其以更高概率選擇具有更高后悔值的行動。盡管 CFR 方法沒法保證雙人零和博弈模型之外的策略達到納什均衡，但是他可以在所有有限博弈中保證后悔值在迭代次數上次線性增長。

由于反事實值和期望值的差值是被添加到后悔值中而不是取代后悔值，所以玩家第一次隨機行動（通常是一種差策略）仍會影響該后悔值。因此這種策略是一種面向未來而采取的策略。在一般的 CFR 方法中，第一次迭代的影響以 1/T 速率衰減，T 為迭代次數。為了快速削弱這種早期“壞”策略帶來的影響，Pluribus 在早期迭代中采取線性 CFR 方法（在后續迭代中作者不采用這種方法，因為乘法帶來的時間成本不值得這么做）。因此第一次迭代的影響將以如下速率衰減：

這使得策略得以在實戰中更快改進，同時仍然保持著優良性能。

Pluribus 的藍圖策略在一臺 64 核的服務器上計算了 8 天，沒有使用 GPU，并且要求的內存小于 512GB，這在云計算高度發達的今天，僅僅只需要花費 144 刀！

不完全信息博弈中的深度限制搜索

由于無限制德州撲克的規模和復雜性，整個游戲的藍圖策略必然是粗粒度的。Pluribus 僅僅在第一輪下注時根據藍圖策略進行游戲，其中決策點的數量足夠小，以至于藍圖策略可以承受不使用信息抽象并且在動作抽象中選擇更多動作。?在第一輪之后（即使在第一輪中，如果對手選擇的賭注大小與藍圖動作抽象中的大小完全不同），Pluribus 也會進行實時搜索，以確定更好，更細粒度的策略。對于在第一輪稍稍偏離博弈樹的對手投注，Pluribus 使用 pseudoharmonic mapping 將賭注映射到附近的 on tree 賭注上并繼續根據藍圖進行游戲，就好像對手真的使用了這樣的賭注大小。

在許多完全信息博弈中實時搜索對于實現超人類表現是非常重要和必要的。這種情況下國際 AI 通常會向前看一些移動，直到在算法前瞻的深度限制處到達葉節點。原則上，如果 AI 可以準確地計算每個葉節點的值（例如取勝，平局或失敗），則該算法將選擇最佳的下一步動作。但是這樣的搜索方法在不完全信息博弈中完全不適合。

例如，考慮一種順序形式的石頭剪刀布，如圖 3 所示，其中玩家 1 首先行動但不向玩家 2 顯示他的動作，然后玩家 2 動作。如果玩家 1 進行的搜索看起來只是前進一步，那么她的每一個動作都會導致一個零值的葉節點。畢竟，如果玩家 2 以選擇納什均衡策略（以 1/3 概率選擇任意一個動作），則選擇 Rock 的玩家 1 的值為零，選擇剪刀的值也是如此。因此，如果玩家 2 的戰略被固定為始終使用納什均衡，那么對于玩家 1 總是出石頭的確是一個最佳策略。然而，實際上，玩家 2 可以調整為總是出布。在這種情況下，總是出石頭的價值實際上是 -1。

這個例子證明在不完美信息子博弈中，葉子節點沒有固定值，相反，他們的值取決于探索者在子博弈中選擇的策略。原則上，這可以通過讓子博弈葉子節點的值作為搜索者在子博弈中的策略的函數來解決，但是這在大型游戲中是不切實際的。

Pluribus 使用一種新方法，其中搜索者明確地認為任何或所有玩家可以轉移到子博弈的葉節點之外的不同策略。作者假設當到達葉子節點時，每個玩家可以在 k 個不同的策略之間進行選擇以進行接下來的博弈。在本文中作者設定 k=4。第一種是預先計算的藍圖策略；第二種是一種改進的傾向于 folding 的藍圖策略；第三種是傾向于 calling 的藍圖策略；第四種是傾向于 raising 的藍圖策略。（以上 folding、calling、raising 均為牌桌策略，分別為棄牌、跟注和加注）

這種技術的引進將使得探索者找到更平衡的策略，因為選擇不平衡策略（例如總是出石頭）將被對手轉移到其他策略（例如總是出布）懲罰。

在不完全信息博弈中搜索的另一個主要挑戰是，玩家在特定情況下的最佳策略取決于從對手的角度看，玩家在每個情況下的策略是什么。為了應對這一挑戰，Pluribus 根據其策略跟蹤每副手牌可能達到當前狀況的概率。?無論 Pluribus 實際持有哪手牌，它都會先計算出每一手牌的動作方式，小心平衡所有牌局的策略，以保持不可預測性。一旦計算出所有人的平衡策略，Pluribus 就會為它實際持有的牌執行一個動作。?在 Pluribus 中使用的深度限制的不完全信息子博弈的結構如圖 4 所示。

Pluribus 使用兩種不同形式的 CFR 來計算子博弈中的策略，具體取決于子博弈的大小和游戲進行的位置。如果子博弈相對較大或者在游戲的早期，則使用和藍圖策略一樣的蒙特卡羅線性 CFR。否則，Pluribus 使用優化的基于矢量的線性 CFR 形式僅對機會事件（例如公共牌）進行采樣。

實際測試時，Pluribus 僅僅使用了兩臺 Intel Haswell E5-2695 v3 CPU，僅占用小于 128G 的內存。相比而言，AlphaGo 對陣李世石時使用了 1920 塊 CPU 和 280 塊 GPU。在對每一個子博弈進行搜索時，根據現場情況，Pluribus 僅需要 1-33 秒。在其與自己鏡像對抗的 6 人牌局中平均出牌時間為 20s，這遠比頂尖人類選手快了近乎 2 倍。

實驗

作者采用了兩種模式評估 Pluribus 對陣人類選手。1、5 個頂尖人類選手 +1 個 AI (5H1 AI )；2、1 個人類頂尖選手 +5 個 AI (1H5AI )。作者通過使用 AI 領域中的標準度量，mbb /game來衡量 AI 表現。該指標用來衡量每千手撲克平均贏得多少大盲注（Big Blind 大盲注 簡稱 BB 莊家左邊第 2 個位置，牌局開始前需固定下注的位置，一般下注額為當前牌桌底注）。此外，作者利用?AIVAT?技術（variance-reduction technique）來減少游戲中的運氣成分。

在 5H1AI 實驗中，人類玩家和 AI 之間展開為期 12 天的 10000 手撲克比賽，在應用了 AIVAT 之后，Pluribus 平均每手贏 48 個 mbb（48 mbb/game）。若以每注 100 美元計算，Pluribus 每手可贏 5 美元，這遠比人類玩家能達到的上限更高。在 1H5AI ?中，Pluribus 平均以 32mbb/game 的速率將人類擊敗。

總結

Pluribus 這次出彩的表現使得 AI 玩耍多人多方游戲不再是難以逾越的鴻溝。也說明面對更復雜的情況和場景，即使難以取得理論支撐，倘若合理建模、合理設計算法，則從實踐上先行突破也未必不可行。此外，人們潛意識中，訓練=資源=燒顯卡。此次 Pluribus 的成功無疑使得眾多“科研平民”看到了希望和曙光。最后，Pluribus 成功應用于德撲也增強了科研工作者將 AI 推廣于更復雜更廣泛領域的信心。

參考文獻

[1]?Bowling, Michael, et al. "Heads-up limit hold’em poker is solved." Science 347.6218 (2015): 145-149.

[2]?Brown, Noam, and Tuomas Sandholm. "Superhuman ?AI ?for heads-up?no-limit poker: Libratus beats top professionals." Science 359.6374(2018):418-424.

[3] Brown, Noam, and Tuomas Sandholm. "Superhuman ?AI ?for multiplayer poker." Science (2019): eaay2400.

[4] Zinkevich, Martin A., Michael Bowling, and Michael Wunder. "The lemonade stand game competition: solving unsolvable games." ACM SIGecom Exchanges 10.1 (2011): 35-38.

點擊以下標題查看更多往期內容：?

#投 稿 通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。

??來稿標準：

? 稿件確系個人原創作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發，請在投稿時提醒并附上所有已發布鏈接?

? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志

? 投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發送?

? 請留下即時聯系方式（微信或手機），以便我們在編輯發布時和作者溝通

?

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

▽ 點擊 |?閱讀原文?| 下載論文

總結

以上是生活随笔為你收集整理的Science论文解读：打牌一时爽，一直打牌一直爽的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。