原標(biāo)題：學(xué)界 | 一臺(tái)筆記本打敗超算：CMU冷撲大師團(tuán)隊(duì)提出全新德?lián)銩I Modicum

選自arXiv

參與：路、曉坤

CMU 冷撲大師團(tuán)隊(duì)在讀博士 Noam Brown、Tuomas Sandholm 教授和研究助理 Brandon Amos 近日提交了一個(gè)新研究：德州撲克人工智能 Modicum，它僅用一臺(tái)筆記本電腦的算力就打敗了業(yè)內(nèi)頂尖的 Baby Tartanian8(2016 計(jì)算機(jī)撲克冠軍)和 Slumbot(2018 年計(jì)算機(jī)撲克冠軍)。此前，冷撲大師的論文《Safe and Nested Subgame Solving for Imperfect-Information Games》是 NIPS 2017 的最佳論文。

1 引言

不完美信息博弈對(duì)智能體和隱藏信息之間的戰(zhàn)略互動(dòng)進(jìn)行建模。此類博弈的主要基準(zhǔn)是撲克，尤其是一對(duì)一無(wú)限注德州撲克(HUNL)，2017 年人工智能 Libratus 打敗德州撲克人類頂級(jí)玩家 [6]。帶來(lái)這一超人性能的關(guān)鍵突破在于嵌套求解(nested solving)，隨著在博弈樹(shù)的位置不斷下移，智能體實(shí)時(shí)重復(fù)計(jì)算更加精細(xì)調(diào)整的策略(只屬于完整博弈的一部分)。

但是，實(shí)時(shí)子博弈求解在前半場(chǎng)對(duì)于 Libratus 來(lái)說(shuō)成本太高，因?yàn)?Libratus 實(shí)時(shí)求解的這部分博弈樹(shù)(即子博弈)通常延伸到游戲結(jié)束。因此，前半場(chǎng) Libratus 預(yù)先計(jì)算出一個(gè)精密策略用作查找表。如果該策略成功，則它需要可用于計(jì)算的數(shù)百萬(wàn)核心時(shí)間和數(shù) TB 內(nèi)存。此外，在更深的序貫博弈中，該方法的計(jì)算開(kāi)銷更加昂貴，因?yàn)樾枰蠼飧L(zhǎng)的子博弈和更大型的預(yù)計(jì)算策略。一個(gè)更通用的方法是在博弈的早期階段就對(duì)深度有限(depth-limited)的子博弈進(jìn)行求解。

撲克 AI DeepStack 使用與嵌套求解類似的一項(xiàng)技術(shù)實(shí)現(xiàn)了這種操作 [26]。但是，盡管 DeepStack 戰(zhàn)勝了一組 HUNL 非頂尖人類專業(yè)選手，但它沒(méi)有打敗之前頂尖的 AI，盡管它使用超過(guò)一百萬(wàn)核心時(shí)間來(lái)訓(xùn)練智能體，這表明它使用的方法可能在撲克等領(lǐng)域不夠?qū)嶋H或有效。本論文在第 7 部分詳細(xì)討論了該問(wèn)題。本論文介紹了一種不同的深度有限求解方法，該方法戰(zhàn)勝了之前頂尖的 AI，且計(jì)算開(kāi)銷實(shí)現(xiàn)數(shù)量級(jí)的下降。

在完美信息博弈中，深度有限子博弈的葉節(jié)點(diǎn)處的值被替換為所有選手在均衡狀態(tài)時(shí)的狀態(tài)估計(jì)值 [34, 32]。例如，該方法在 backgammon [38]、國(guó)際象棋 [9] 和圍棋 [35, 36] 上達(dá)到了超越人類的水平。同樣的方法還廣泛應(yīng)用于單智能體設(shè)置中，如啟發(fā)式搜索 [29, 24, 30, 15]。的確，在單智能體和完美信息多智能體設(shè)置中，了解所有選手均衡狀態(tài)時(shí)的狀態(tài)值足以重建均衡。但是，該方法在不完美信息博弈中沒(méi)有效果。

2 深度有限求解在不完美信息博弈中遇到的挑戰(zhàn)

在不完美信息博弈中(也叫作部分可觀測(cè)游戲)，子博弈中的最優(yōu)策略無(wú)法通過(guò)了解所有選手均衡狀態(tài)時(shí)的狀態(tài)值(即博弈樹(shù)節(jié)點(diǎn))來(lái)確定。圖 1a 是一個(gè)簡(jiǎn)單圖示，展示了一種序貫博弈游戲「剪刀石頭布+」(Rock-Paper-Scissors+，RPS+)。RPS+ 和傳統(tǒng)的 RPS 相同，除了玩家出剪刀，贏者得 2 分而不是 1 分(輸者也輸 2 分)。圖 1a 以序貫博弈的形式展示 RPS+ 游戲，其中 P_1 首先動(dòng)作，但是沒(méi)有向 P_2 泄露動(dòng)作。該游戲中對(duì)于兩個(gè)玩家來(lái)說(shuō)，最優(yōu)策略(Minmax 策略，即雙人零和博弈中的納什均衡)就是每一方以 40% 的概率選擇石頭或布，20% 的概率選擇剪刀。在該均衡中，P_1 選擇石頭的期望值為 0，選擇剪刀或布的值也為 0。也就是說(shuō)，圖 1a 中所有的紅色狀態(tài)在該均衡中的值都為 0。現(xiàn)在，假設(shè) P_1 實(shí)施深度為 1 的深度有限搜索，深度極限處的均衡值被替代。該深度有限子博弈如圖 1b 所示。很明顯，在該子博弈中沒(méi)有足夠的信息達(dá)到 40% 石頭、40% 布、20% 剪刀的最優(yōu)策略。

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

在本文中，研究者引入了一種深度有限求解方法，確保玩家策略對(duì)于對(duì)手的變化具備魯棒性。研究者允許對(duì)手在深度有限(depth limit)處進(jìn)行最后一次動(dòng)作選擇(其中每個(gè)動(dòng)作對(duì)應(yīng)對(duì)手將在博弈余下部分執(zhí)行的策略)，而不是在深度極限處簡(jiǎn)單地替換單個(gè)狀態(tài)值。策略的選擇決定了狀態(tài)值。對(duì)手并沒(méi)有按特定于狀態(tài)的方式進(jìn)行選擇(即選擇最大狀態(tài)值)。相反，自然地，對(duì)手必須在所有狀態(tài)進(jìn)行相同的(對(duì)他而言)無(wú)法分辨的選擇。研究者證明了如果對(duì)手被給定了在深度有限處的足夠數(shù)量的策略，那么任何在深度有限處的子博弈求解都是完整博弈的納什均衡策略的一部分。他們還通過(guò)實(shí)驗(yàn)展示了，當(dāng)僅提供了少量的策略時(shí)(為提高計(jì)算速度)，該方法的性能達(dá)到極端的高度。

6 實(shí)驗(yàn)

研究者在一對(duì)一無(wú)限注德州撲克(HUNL)和一對(duì)一無(wú)限注 flop 撲克(NLFH)上構(gòu)建了實(shí)驗(yàn)。附錄 B 中有這些游戲的規(guī)則。HUNL 是不完美信息博弈 AI 的主要大規(guī)模基準(zhǔn)。NLFH 和 HUNL 相似，除了博弈會(huì)在第二個(gè)回合之后立刻結(jié)束，這使其規(guī)模足夠小，從而能精確地計(jì)算最佳反應(yīng)和納什均衡。性能根據(jù) mbb/g 測(cè)量，這是文獻(xiàn)中的標(biāo)準(zhǔn)勝率度量。mbb/g 即 milli-big blinds per game，代表玩家在每一手牌中平均能贏多少個(gè)大盲注(玩家在開(kāi)始時(shí)必須承諾的賭注)的千分之一。

圖 2：回應(yīng)對(duì)手的 off-tree 動(dòng)作的深度有限解決方案的利用度(exploitability)，作為狀態(tài)值數(shù)量的函數(shù)。研究者對(duì)比了動(dòng)作轉(zhuǎn)換和在動(dòng)作提取中包含 off-tree 動(dòng)作(在 CFR+的 1000 次迭代的達(dá)成利用度是下限值)的方法。

6.2 在一對(duì)一無(wú)限注德州撲克(HUNL)上對(duì)抗頂尖 AI 的實(shí)驗(yàn)

我們主要的實(shí)驗(yàn)使用了深度有限求解的方法，并僅使用普通筆記本電腦上的計(jì)算資源生成大師級(jí)的 HUNL 撲克 AI：Modicum。我們測(cè)試了 Modicum 與 Baby Tartanian8 [4] 和 Slumbot [18]，其中 Baby Tartanian8 是 2016 年度計(jì)算機(jī)撲克競(jìng)賽的獲勝者，Slumbot 是 2018 年度計(jì)算機(jī)撲克競(jìng)賽的獲勝者。Baby Tartanian8 和 Slumbot 都不使用實(shí)時(shí)計(jì)算，它們的策略都是在預(yù)計(jì)算的查找表中搜索得到的。Baby Tartanian8 使用了約為 250000 個(gè)核心計(jì)算小時(shí)和 2TB RAM 來(lái)計(jì)算策略。相反，Modicum 只使用 700 個(gè)核心計(jì)算小時(shí)和 16GB 的 RAM 計(jì)算策略，它在使用 4 核 CPU 的情況下還能以人類專家的速度實(shí)時(shí)進(jìn)行博弈(平均一手撲克需要 20 秒)。

7 對(duì)比先前研究工作

通過(guò)為狀態(tài)分配多個(gè)值，本論文介紹了一種克服這一挑戰(zhàn)的方法。一種不同的方法是將「狀態(tài)」的定義修改為所有博弈者對(duì)狀態(tài)的的信念概率分布(belief probability distribution)，我們稱之為聯(lián)合信念狀態(tài)，這種技術(shù)以前也用來(lái)開(kāi)發(fā)撲克 AI DeepStack [26]。實(shí)驗(yàn)表明，在我們測(cè)試的領(lǐng)域中，使用多值狀態(tài)(multi-valued states)能產(chǎn)生更好的性能。例如我們的方法在少于 1000 個(gè)核心計(jì)算小時(shí)的條件下能擊敗兩種以前頂級(jí)的德州撲克 AI。相比之下，雖然 DeepStack 擊敗了在 HUNL 中不是那么專業(yè)的人類專家，但它即使使用了 1000000 個(gè)核心計(jì)算小時(shí)，也不能擊敗以前頂尖的 AI。但是，這兩種方法都各自有優(yōu)缺點(diǎn)，我們需要根據(jù)領(lǐng)域正確地選擇，未來(lái)的研究也許會(huì)改進(jìn)它們的性能與優(yōu)勢(shì)。

論文：Depth-Limited Solving for Imperfect-Information Games

論文地址：https://arxiv.org/abs/1805.08195

在不完美信息博弈中，一個(gè)基本的挑戰(zhàn)即狀態(tài)沒(méi)有良好定義的值。因此在單智能體和完美信息博弈中常用的深度有限(depth-limited)搜索算法并不合適。本文介紹了一種在不完美信息博弈中進(jìn)行深度優(yōu)先求解的原則性方法，它允許對(duì)手在深度有限下為其余部分選擇多種策略。且每一種策略都會(huì)為葉節(jié)點(diǎn)生成一組不同值，這使得智能體針對(duì)對(duì)手可能采取的策略產(chǎn)生魯棒性。我們通過(guò)構(gòu)建大師級(jí)的一對(duì)一無(wú)限注德州撲克 AI 而證明這種方法的高效性，它僅使用一塊 4 核的 CPU 和 16GB 的內(nèi)存就能擊敗兩個(gè)以前頂級(jí)的智能體。以前，開(kāi)發(fā)這樣一個(gè)強(qiáng)大的智能體需要一臺(tái)超級(jí)計(jì)算機(jī)。

本文為機(jī)器之心編譯，轉(zhuǎn)載請(qǐng)聯(lián)系本公眾號(hào)獲得授權(quán)。返回搜狐，查看更多

責(zé)任編輯：

總結(jié)

以上是生活随笔為你收集整理的android德州扑克计算器,学界 | 一台笔记本打败超算：CMU冷扑大师团队提出全新德扑AI Modicum...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。