還記得去年戰(zhàn)勝4位專業(yè)牌手的德州撲克AI“冷撲大師”嗎？最近，它的締造者、“德州撲克AI之父”Noam Brown和Tuomas Sandholm再發(fā)新論文，通過德州撲克基準(zhǔn)平臺(tái)來探討不完全信息條件下的博弈策略問題，也許“冷撲大師2.0”真的要來了。

最近，Arxiv上的一篇題為《Solving Imperfect-Information Games via Discounted Regret Minimization》引發(fā)關(guān)注，原因主要在于本文的兩位作者的鼎鼎大名，CMU計(jì)算機(jī)系博士生Noam Brown，以及該校計(jì)算機(jī)系教授Tuomas Sandholm。這兩位就是去年的著名的德州撲克AI程序“冷撲大師”（Libratus）的締造者，堪稱德州撲克AI之父。

“冷撲大師”在去年曾與4位人類專業(yè)德州撲克牌手大戰(zhàn)20天，最后全面獲勝。兩位作者還去Reddit論壇的機(jī)器學(xué)習(xí)板塊上搞了一次“Ask meanything”的網(wǎng)友問答互動(dòng)，一時(shí)名聲大噪。闡述“冷撲大師”背景技術(shù)的論文也被評為NIPS 2017最佳論文。

“冷撲大師”在2017年的人機(jī)德州撲克大賽面對4位專業(yè)人類牌手，全部獲勝

時(shí)隔一年多，二位大師再次發(fā)布關(guān)于不完全信息博弈策略的論文，仍主要以德州撲克為測試基準(zhǔn)平臺(tái)，難道“冷撲大師”2.0就要來了？人類牌手們，準(zhǔn)備好（再次）被碾壓了嗎？

一起看看這篇文章都講了些什么。

論文地址：

https://arxiv.org/abs/1809.04040

摘要

Counterfactual regret minimization（CFR）是目前很流行的一系列迭代算法，實(shí)際上也是近似解決大型不完美信息游戲的最快的AI算法。本算法系列中提出了一個(gè)“后悔值” （regrets）的概念，即在當(dāng)前狀態(tài)下，選擇行為A，而不是行為B，后悔的值是多少。

在本文中，我們介紹了一些CFR算法的一些新變化，其中包括1）采用多種方法從早期迭代中減低“后悔值”（regret）（在某些情況下對正面和負(fù)面后悔值使用不同策略）。（2）以各種方式對迭代進(jìn)行重新加權(quán)，以獲得更佳的輸出策略。（3）使用非標(biāo)準(zhǔn)化的后悔值最小化策略。（4）利用optimistic regret matching。這些方法可以在諸多環(huán)境中顯著提高性能。

首先，我們在每個(gè)測試的游戲中引入一個(gè)優(yōu)化的CFR +的變體算法，這是之前最先進(jìn)的算法。CFR+是一個(gè)強(qiáng)大的基準(zhǔn)，沒有其他算法能夠超越它。我們表明，與CFR +不同，許多基于CFR的重要的新算法與現(xiàn)代不完全信息游戲修剪技術(shù)兼容，而且與游戲樹中的樣本兼容。

論文內(nèi)容提要

不完全信息博弈模擬互相擁有隱藏信息的玩家之間的戰(zhàn)略互搏，比如談判、網(wǎng)絡(luò)安全和拍賣都是屬于此類。撲克游戲是這類博弈的常用測試基準(zhǔn)。

這種測試的一般目標(biāo)是找到一種（近似的）均衡，在這種均衡狀態(tài)下，沒有玩家可以通過偏離該均衡狀態(tài)來提高自己的收益。對于線性程序無法應(yīng)對的的極大規(guī)模的不完全信息博弈，通常使用迭代算法來近似均衡。

CFR方法的主要思想是把游戲中所有狀態(tài)都考慮到，生成一顆完整的狀態(tài)樹。對樹的每一個(gè)節(jié)點(diǎn)都初始化一個(gè)策略，然后根據(jù)這個(gè)策略來玩游戲。每次都走狀態(tài)樹的一條邊，然后根據(jù)游戲的結(jié)果來更新相關(guān)節(jié)點(diǎn)的策略。

當(dāng)CFR進(jìn)行了許多次迭代之后，這個(gè)狀態(tài)樹的每條路徑都被遍歷了很多次，每個(gè)節(jié)點(diǎn)的策略都被更新趨于均衡了，從而得到一個(gè)可以玩游戲的AI。

實(shí)驗(yàn)中使用的游戲——德州撲克和Goofspiel

德州撲克是測試不完全信息博弈算法表現(xiàn)的典型游戲。在本文中使用無限制Heads-up德州撲克規(guī)則。兩位玩家（P1和P2）起手籌碼各為20000美元，大/小盲注為50/100美元。每輪加注不得少于100美元。讓對方籌碼降至0者獲勝。

除了德州撲克外，本文采用了另一種紙牌游戲Goofspiel，兩位玩家各擁有5張手牌(A、2、3、4、5)，牌桌中間有5張牌的獎(jiǎng)勵(lì)牌堆，牌堆中的牌也是A\2\3\4\5。每輪從牌堆中先翻開最上面的牌作為獎(jiǎng)勵(lì)牌，然后兩名牌手同時(shí)出一張手牌比大小，勝者贏得獎(jiǎng)勵(lì)牌，用過的手牌被棄掉。最后以獎(jiǎng)勵(lì)牌總分?jǐn)?shù)（A為1分、2為2分，以此類推）多者獲勝。

實(shí)驗(yàn)：CFR的幾種變體和CFR+基準(zhǔn)

我們的實(shí)驗(yàn)針對德州撲克進(jìn)行了32768次迭代，對Goofspiel進(jìn)行了8192次迭代。由于是近似均衡，而不是精確均衡，所以何時(shí)終止迭代計(jì)算很大程度上取決于實(shí)驗(yàn)者，一般取100-1000次迭代的結(jié)果就是有意義的。

所有實(shí)驗(yàn)都使用CFR的交替更新形式。我們衡量兩個(gè)玩家的平均可利用性。我們的實(shí)驗(yàn)表明，在某些游戲中，線性CFR（LCFR）可以在合理的時(shí)間范圍內(nèi)顯著提高CFR +的性能。

然而，LCFR在實(shí)際實(shí)驗(yàn)中的表現(xiàn)似乎比CFR+差。線性CFR在Subgame1和3中的表現(xiàn)特別好，與Subgame2和4相比，相對于每個(gè)玩家可以下注的最高金額，底池中籌碼價(jià)值很小，這時(shí)更容易出現(xiàn)嚴(yán)重的錯(cuò)誤行為。在Goofspiel中，線性CFR同樣表現(xiàn)不佳，這表明線性CFR特別適合可能出現(xiàn)嚴(yán)重錯(cuò)誤的游戲。

NormalHedge CFR（NH）是一個(gè)在游戲中每個(gè)信息集中獨(dú)立應(yīng)用regret最小化的框架。通常，我們使用Regret Matching（RM）作為實(shí)現(xiàn)后悔最小化的工具，主要是由于無參數(shù)的特點(diǎn)和簡單的實(shí)現(xiàn)形式。但是，我們也可以應(yīng)用任何其他實(shí)現(xiàn)regret最小化的工具。

我們使用Normal Hedge（NH）作為CFR中的regret最小化工具進(jìn)行研究。

NH與RM都具備兩個(gè)很理想的特點(diǎn)：都沒有任何參數(shù)，并且會(huì)向后悔值為負(fù)的行為分配“零概率”（這意味著它可以很容易地用于CFR +上）。不過，NH操作在計(jì)算上比RM成本更高，因?yàn)樗婕叭绾途€搜索。

我們發(fā)現(xiàn)，NH在具有大錯(cuò)誤動(dòng)作的游戲中可能做得更好。在這些實(shí)驗(yàn)中，NH的性能是根據(jù)可利用性作為迭代次數(shù)的函數(shù)來測量的。但是，在我們的實(shí)現(xiàn)中，由于NH中涉及取冪和行搜索操作，每次迭代所需的時(shí)間要比RM方法長五倍。

因此，使用NH實(shí)際上減慢了實(shí)踐中的收斂。然而，在指數(shù)和線搜索操作的成本無關(guān)緊要的某些情況下，比如算法的瓶頸主要在于內(nèi)存不足，而不是計(jì)算速度時(shí)，NH方法可能是更好的選擇。

蒙特卡洛CFR（MCCFR）是CFR算法的另一變體，該算法對玩家的某些行為或機(jī)會(huì)結(jié)果進(jìn)行采樣。).

MCCFR與抽象方法相結(jié)合，可以產(chǎn)生最先進(jìn)的面向德州撲克游戲的AI算法。該模型在沒有特殊結(jié)構(gòu)的博弈中特別有用，可以利用該算法來達(dá)成CFR的快速矢量實(shí)現(xiàn)。

MCCFR的種類不少，具有不同的采樣方案。最流行的是外部采樣MCCFR，其中根據(jù)其概率對對手和機(jī)會(huì)動(dòng)作進(jìn)行采樣，但是遍歷了更新regret值的玩家的所有行動(dòng)。目前也存在其他性能優(yōu)異的MCCFR變體，但外部采樣式MCCFR簡單且廣泛使用，可用作我們實(shí)驗(yàn)的基準(zhǔn)。

盡管CFR+在非抽樣的情況下體現(xiàn)出比CFR更大的性能改進(jìn)，但CFR+中的變化，在應(yīng)用于MCCFR時(shí)并不會(huì)帶來更優(yōu)秀的性能。

上圖表明，與vanilla MCCFR相比，模型在德州撲克上具有更優(yōu)越的表現(xiàn)。在子游戲3（圖中上半部分）中，這種性能提升尤為明顯。

結(jié)論

我們在本文中介紹了CFR算法的變體，可以對先前的迭代進(jìn)行discount，并表現(xiàn)出比之前最先進(jìn)的CFR +類算法更強(qiáng)大的性能，在涉及重大錯(cuò)誤的環(huán)境中表現(xiàn)的更加明顯。