非完美信息博弈廣泛存在于日常生活的方方面面，如智慧交通、網(wǎng)絡(luò)安全、金融分析等。騰訊AI Lab以麻將AI為切入點(diǎn)研究非完美信息博弈，其目標(biāo)不僅限于打造世界級(jí)的國粹麻將AI，更多的在于探索非完美信息博弈在游戲領(lǐng)域，以及其他廣闊的社會(huì)生活領(lǐng)域的實(shí)際應(yīng)用價(jià)值。

研究背景

棋牌游戲一直以來都是AI技術(shù)的優(yōu)質(zhì)試驗(yàn)場，例如，在圍棋上就誕生了AlphaGo、絕藝等標(biāo)桿性的AI。相比于圍棋這類“完美信息”游戲，德州撲克，橋牌，麻將這類“非完美信息”游戲存在著大量的隱藏信息，例如，玩家無法直接知道對(duì)手的手牌，這給游戲帶來了更高的不確定性，對(duì)AI的博弈能力提出更高要求。

具體而言，在完美信息游戲中，始終存在確定性的最優(yōu)解，即任何狀態(tài)下都存在一個(gè)固定的最優(yōu)動(dòng)作。然而在非完美信息游戲中，最優(yōu)策略往往是隨機(jī)化的。例如，在二人石頭-剪刀-布游戲中，最優(yōu)策略（納什均衡策略）不在是某一個(gè)固定的動(dòng)作，而是關(guān)于每個(gè)動(dòng)作的一個(gè)概率分布：等概率出石頭，剪刀，和布。

二人石頭-剪刀-布

近年來，反事實(shí)遺憾值最小化算法（CFR）在德州撲克游戲AI上取得了一些列突破性進(jìn)展，例如DeepStack（2017 Science雜志），Libratus（冷撲大師，2017 Science雜志），和Pluribus（2019 Science雜志）。CFR具有收斂到納什均衡解的理論保證。然而，由于CFR是一種基于表格的算法，并且需要對(duì)游戲樹做全遍歷，CFR在德州撲克游戲上的應(yīng)用需要大量的領(lǐng)域知識(shí)來對(duì)游戲樹做剪枝。雖然后續(xù)有一些工作嘗試將深度學(xué)習(xí)和CFR做結(jié)合，但目前還沒有看到CFR在其他大規(guī)模非完美信息游戲上的成功應(yīng)用。

另一方面，由于深度強(qiáng)化學(xué)習(xí)高效的可擴(kuò)展性，深度強(qiáng)化學(xué)習(xí)結(jié)合自博弈廣泛用于大規(guī)模非完美信息游戲中求解高強(qiáng)度AI，例如星際2，Dota2，和王者榮耀。

然而，基于深度強(qiáng)化學(xué)習(xí)的大部分AI的魯棒性有待提高，集中表現(xiàn)為AI容易被針對(duì)，最壞情況下的性能沒有保證。這些問題的根本原因在于深度強(qiáng)化學(xué)習(xí)結(jié)合自博弈缺乏收斂到納什均衡解的理論保證。例如下圖所示，在一個(gè)簡單的二人石頭-剪刀-布游戲中，自博弈Proximal Policy Optimization無法收斂到（紅線為收斂過程）納什均衡解（藍(lán)點(diǎn)）。

方法簡介

騰訊AI Lab的研究結(jié)合經(jīng)典反事實(shí)遺憾值最小化算法CFR的思想，在大規(guī)模強(qiáng)化學(xué)習(xí)算法框架下提出了一個(gè)新的策略優(yōu)化算法Actor-Critic Hedge (ACH)。該算法一方面具備深度強(qiáng)化學(xué)習(xí)方法的可擴(kuò)展性，一方面在某些條件下具備收斂到納什均衡解的理論保證。

具體來說，我們修改傳統(tǒng)深度強(qiáng)化學(xué)習(xí)策略網(wǎng)絡(luò)的損失函數(shù)：從最大化累計(jì)獎(jiǎng)勵(lì)到擬合累計(jì)采樣advantage：

累計(jì)采樣advantage與CFR中的累計(jì)遺憾值存在一定的等價(jià)關(guān)系。另外，可以證明，相比過去基于采樣regret的方法，采樣advantage有更小的variance：

更小的variance在基于神經(jīng)網(wǎng)絡(luò)的方法中意味著更穩(wěn)定的效果。

ACH具體算法流程如下：

在該工作中，我們引入了一類新的CFR算法：Weighted CFR。Weighted CFR有如下定義：

算法ACH可以看作是一類基于神經(jīng)網(wǎng)絡(luò)的Weighted CFR算法的一個(gè)高效實(shí)現(xiàn)。我們證明了Weighted CFR的算法收斂性，進(jìn)而近似證明了ACH的算法收斂性：

另外，針對(duì)1v1麻將的具體神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)如下：

實(shí)驗(yàn)結(jié)果

在對(duì)比主流方法的基礎(chǔ)上，該算法的優(yōu)越性在1v1麻將（戰(zhàn)勝職業(yè)冠軍）和1v1德州撲克上均得到了驗(yàn)證。

二人麻將：“二人雀神”

1v1麻將（二人雀神）測試中，「絕藝」與世界冠軍職業(yè)選手對(duì)戰(zhàn)1000回合，平均贏番0.82

（標(biāo)準(zhǔn)差0.96，單邊 t 檢驗(yàn)的 p value 為0.19）

1v1麻將環(huán)境，主流算法性能對(duì)比

1v1簡單德?lián)洵h(huán)境，各種經(jīng)典反事實(shí)遺憾值最小化算法擴(kuò)展的對(duì)比

songjy