“冷撲大師”2.0就要來了？人類牌手們，準備好被碾壓了嗎？

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

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

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

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

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

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

論文地址：

https://arxiv.org/abs/1809.04040

摘要

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

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

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

論文內(nèi)容提要

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

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

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

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

實驗中使用的游戲——德州撲克和Goofspiel

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

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

實驗：CFR的幾種變體和CFR+基準

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

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

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

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

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

NH與RM都具備兩個很理想的特點：都沒有任何參數(shù)，并且會向后悔值為負的行為分配“零概率”（這意味著它可以很容易地用于CFR +上）。不過，NH操作在計算上比RM成本更高，因為它涉及取冪和線搜索。

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

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

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

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

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

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

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

結(jié)論

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