一台筆記本打敗超算：CMU冷撲大師團隊提出全新德撲AI Modicum

CMU 冷撲大師團隊在讀博士 Noam Brown、Tuomas Sandholm 教授和研究助理 Brandon Amos 近日提交了一個新研究：德州撲克人工智慧 Modicum，它僅用一台筆記本電腦的算力就打敗了業內頂尖的 Baby Tartanian8（2016 計算機撲克冠軍）和 Slumbot（2018 年計算機撲克冠軍）。此前，冷撲大師的論文《Safe and Nested Subgame Solving for Imperfect-Information Games》是 NIPS 2017 的最佳論文。1 引言不完美信息博弈對智能體和隱藏信息之間的戰略互動進行建模。此類博弈的主要基準是撲克，尤其是一對一無限注德州撲克（HUNL），2017 年人工智慧 Libratus 打敗德州撲克人類頂級玩家 [6]。帶來這一超人性能的關鍵突破在於嵌套求解（nested solving），隨著在博弈樹的位置不斷下移，智能體實時重複計算更加精細調整的策略（只屬於完整博弈的一部分）。

但是，實時子博弈求解在前半場對於 Libratus 來說成本太高，因為 Libratus 實時求解的這部分博弈樹（即子博弈）通常延伸到遊戲結束。因此，前半場 Libratus 預先計算出一個精密策略用作查找表。如果該策略成功，則它需要可用於計算的數百萬核心時間和數 TB 內存。此外，在更深的序貫博弈中，該方法的計算開銷更加昂貴，因為需要求解更長的子博弈和更大型的預計算策略。一個更通用的方法是在博弈的早期階段就對深度有限（depth-limited）的子博弈進行求解。

撲克 AI DeepStack 使用與嵌套求解類似的一項技術實現了這種操作 [26]。但是，儘管 DeepStack 戰勝了一組 HUNL 非頂尖人類專業選手，但它沒有打敗之前頂尖的 AI，儘管它使用超過一百萬核心時間來訓練智能體，這表明它使用的方法可能在撲克等領域不夠實際或有效。本論文在第 7 部分詳細討論了該問題。本論文介紹了一種不同的深度有限求解方法，該方法戰勝了之前頂尖的 AI，且計算開銷實現數量級的下降。

在完美信息博弈中，深度有限子博弈的葉節點處的值被替換為所有選手在均衡狀態時的狀態估計值 [34, 32]。例如，該方法在 backgammon [38]、國際象棋 [9] 和圍棋 [35, 36] 上達到了超越人類的水平。同樣的方法還廣泛應用於單智能體設置中，如啟發式搜索 [29, 24, 30, 15]。的確，在單智能體和完美信息多智能體設置中，了解所有選手均衡狀態時的狀態值足以重建均衡。但是，該方法在不完美信息博弈中沒有效果。

2 深度有限求解在不完美信息博弈中遇到的挑戰在不完美信息博弈中（也叫作部分可觀測遊戲），子博弈中的最優策略無法通過了解所有選手均衡狀態時的狀態值（即博弈樹節點）來確定。圖 1a 是一個簡單圖示，展示了一種序貫博弈遊戲「剪刀石頭布+」（Rock-Paper-Scissors+，RPS+）。RPS+ 和傳統的 RPS 相同，除了玩家出剪刀，贏者得 2 分而不是 1 分（輸者也輸 2 分）。圖 1a 以序貫博弈的形式展示 RPS+ 遊戲，其中 P_1 首先動作，但是沒有向 P_2 泄露動作。該遊戲中對於兩個玩家來說，最優策略（Minmax 策略，即雙人零和博弈中的納什均衡）就是每一方以 40% 的概率選擇石頭或布，20% 的概率選擇剪刀。在該均衡中，P_1 選擇石頭的期望值為 0，選擇剪刀或布的值也為 0。也就是說，圖 1a 中所有的紅色狀態在該均衡中的值都為 0。現在，假設 P_1 實施深度為 1 的深度有限搜索，深度極限處的均衡值被替代。該深度有限子博弈如圖 1b 所示。很明顯，在該子博弈中沒有足夠的信息達到 40% 石頭、40% 布、20% 剪刀的最優策略。

在 RPS+ 例子中，核心問題在於我們不正確地假設 P_2 將總是執行固定的策略。如果實際上 P_2 出石頭、布和剪刀的概率是<0.4,0.4,0.2>，那麼 P_1 將選擇任意的策略並且期望值為 0。然而，如果假設 P_2 總是執行固定的策略，P_1 可能無法找到對 P_2 變化具備魯棒性的策略。事實上，P_2 的最優策略依賴於 P_1 選擇石頭、布和剪刀的概率。一般而言，在不完美信息博弈中，玩家在某個決策點的最優策略依賴於玩家在狀態上的信度分布（belief distribution），以及其它智能體在該決策點上的策略。

在本文中，研究者引入了一種深度有限求解方法，確保玩家策略對於對手的變化具備魯棒性。研究者允許對手在深度有限（depth limit）處進行最後一次動作選擇（其中每個動作對應對手將在博弈餘下部分執行的策略），而不是在深度極限處簡單地替換單個狀態值。策略的選擇決定了狀態值。對手並沒有按特定於狀態的方式進行選擇（即選擇最大狀態值）。相反，自然地，對手必須在所有狀態進行相同的（對他而言）無法分辨的選擇。研究者證明了如果對手被給定了在深度有限處的足夠數量的策略，那麼任何在深度有限處的子博弈求解都是完整博弈的納什均衡策略的一部分。他們還通過實驗展示了，當僅提供了少量的策略時（為提高計算速度），該方法的性能達到極端的高度。

6 實驗研究者在一對一無限注德州撲克（HUNL）和一對一無限注 flop 撲克（NLFH）上構建了實驗。附錄 B 中有這些遊戲的規則。HUNL 是不完美信息博弈 AI 的主要大規模基準。NLFH 和 HUNL 相似，除了博弈會在第二個回合之後立刻結束，這使其規模足夠小，從而能精確地計算最佳反應和納什均衡。性能根據 mbb/g 測量，這是文獻中的標準勝率度量。mbb/g 即 milli-big blinds per game，代表玩家在每一手牌中平均能贏多少個大盲注（玩家在開始時必須承諾的賭注）的千分之一。

圖 2：回應對手的 off-tree 動作的深度有限解決方案的利用度（exploitability），作為狀態值數量的函數。研究者對比了動作轉換和在動作提取中包含 off-tree 動作（在 CFR+的 1000 次迭代的達成利用度是下限值）的方法。

6.2 在一對一無限注德州撲克（HUNL）上對抗頂尖 AI 的實驗我們主要的實驗使用了深度有限求解的方法，並僅使用普通筆記本電腦上的計算資源生成大師級的 HUNL 撲克 AI：Modicum。我們測試了 Modicum 與 Baby Tartanian8 [4] 和 Slumbot [18]，其中 Baby Tartanian8 是 2016 年度計算機撲克競賽的獲勝者，Slumbot 是 2018 年度計算機撲克競賽的獲勝者。Baby Tartanian8 和 Slumbot 都不使用實時計算，它們的策略都是在預計算的查找表中搜索得到的。Baby Tartanian8 使用了約為 250000 個核心計算小時和 2TB RAM 來計算策略。相反，Modicum 只使用 700 個核心計算小時和 16GB 的 RAM 計算策略，它在使用 4 核 CPU 的情況下還能以人類專家的速度實時進行博弈（平均一手撲克需要 20 秒）。

7 對比先前研究工作通過為狀態分配多個值，本論文介紹了一種克服這一挑戰的方法。一種不同的方法是將「狀態」的定義修改為所有博弈者對狀態的的信念概率分布（belief probability distribution），我們稱之為聯合信念狀態，這種技術以前也用來開發撲克 AI DeepStack [26]。實驗表明，在我們測試的領域中，使用多值狀態（multi-valued states）能產生更好的性能。例如我們的方法在少於 1000 個核心計算小時的條件下能擊敗兩種以前頂級的德州撲克 AI。相比之下，雖然 DeepStack 擊敗了在 HUNL 中不是那麼專業的人類專家，但它即使使用了 1000000 個核心計算小時，也不能擊敗以前頂尖的 AI。但是，這兩種方法都各自有優缺點，我們需要根據領域正確地選擇，未來的研究也許會改進它們的性能與優勢。

論文：Depth-Limited Solving for Imperfect-Information Games論文地址：https://arxiv.org/abs/1805.08195

在不完美信息博弈中，一個基本的挑戰即狀態沒有良好定義的值。因此在單智能體和完美信息博弈中常用的深度有限（depth-limited）搜索演算法並不合適。本文介紹了一種在不完美信息博弈中進行深度優先求解的原則性方法，它允許對手在深度有限下為其餘部分選擇多種策略。且每一種策略都會為葉節點生成一組不同值，這使得智能體針對對手可能採取的策略產生魯棒性。我們通過構建大師級的一對一無限注德州撲克 AI 而證明這種方法的高效性，它僅使用一塊 4 核的 CPU 和 16GB 的內存就能擊敗兩個以前頂級的智能體。以前，開發這樣一個強大的智能體以前需要一台超級計算機

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！