“拱豬”游戲的深度蒙特卡洛博弈算法

吳立成,吳啟飛,鐘宏鳴,李霞麗

(中央民族大學 信息工程學院， 北京 100081)

0 引言

1997年，“深藍”[1]在國際象棋游戲上以 3.5∶2.5的比分擊敗了職業選手卡斯帕羅夫；2016年開始，Google旗下DeepMind公司研制的AlphaGo[2]與AlphaZero[3]在圍棋游戲上取得了非常優秀的成績。近年來，機器博弈在非完全信息領域逐漸成為熱門研究之一。2015年，CFR+算法的提出為解決有限注德州撲克[4-6]游戲中非完全信息博弈提供了新思路[7]，不足的是該算法只能解決小型的非完全信息博弈問題；2018年，由Brown等[8]提出的CFR算法變體可解決大型非完全信息博弈問題，并在大型撲克游戲中取得了強大的表現；2021年，張小川等[9]針對提高不同對手的評估效益的問題，提出了一種基于對手牌力的評估方法，實驗表明，其所構建的德州撲克智能體能夠打敗不同風格的對手，總體收益較靜態評估方法有所提高；2020年，由 Li等[10]開發的麻將人工智能模型Suphx在Tenhou平臺上超過了99.99%的玩家水平；2021年，Zha 等[11]開發的基于深度神經網絡的“斗地主”人工智能DouZero在Botzone的344個“斗地主”人工智能模型中取得了第一名的成績。除了傳統棋牌類游戲，人工智能在電子游戲上的發展也令人驚嘆，由DeepMind開發的AlphaStar[11]和OpenAI 開發的OpenAI Five[12]分別在星際爭霸和 Dota 2 中達到了專業玩家水平；2020年，Ye等[13]開發的“絕悟”人工智能模型擊敗了頂尖的王者榮耀職業玩家。

現有的“拱豬”人工智能模型較少，且主要采用監督學習方法，計算復雜且高度依賴人類知識。“拱豬”具有2個特點。第一：游戲具有極大的反轉性，參與游戲的玩家將在僅了解游戲部分信息的條件下進行競爭與合作，競爭和合作的選擇決定著最后的游戲結果；第二：游戲玩家與撲克牌可構成巨大的狀態空間，同時也擁有多達52種動作空間，這使得狀態空間的搜索與計算變得非常困難。以上2個特點決定了常見的深度學習方法在“拱豬”人工智能模型的構建上很難起到立竿見影的效果。

本文將在“斗地主”中已成功應用的深度蒙特卡洛算法[11]移用于“拱豬”游戲中，開發了不依賴人類知識、易于計算、訓練效率高的“拱豬”模型。該模型并不會搜索所有的狀態空間，而是在自對弈過程中進行逐步探索；基于并行處理的方式可生成更多的訓練數據。該模型具有3個優點，第一：它不依賴人類專家知識，可以自然地模擬人類行為并進行評估學習，且比傳統的深度學習需要更小的計算量；第二：依賴于現代計算機的強大計算能力，模型在訓練過程中可以輕易地覆蓋人類玩家不常見的狀態與動作并進行訓練與學習；第三：在大量的自對弈過程中，偶然錯誤的動作及其評估不會對模型的最終效果產生嚴重的影響。這3個優點使得該模型在訓練過程中能夠處理“拱豬”巨大且復雜的狀態空間，這對于“拱豬”人工智能模型的構建是至關重要的。

本文構建的模型在具有一個GPU的單臺服務器上訓練24 h后，表現出來的性能要優于基于卷積神經網絡的“拱豬”人工智能模型(以下簡稱卷積模型)。

1 “拱豬”游戲規則和數據格式

1.1 “拱豬”游戲規則

“拱豬”是一款風靡于全國及海外華人地區的傳統撲克牌游戲，規則簡單卻易懂難精，由一副去除大小王的52張撲克牌組成，參與游戲的玩家共4名，每位玩家隨機得到13張牌。在“拱豬”的游戲規則中，撲克牌被分為兩類：有分值的牌和無分值的牌，表1展示了“拱豬”中牌與分值的對應關系。

表1 “拱豬”中牌與分值的對應關系

除此之外，贏得梅花10的玩家手里的分牌分值將變為原本的2倍，若手里無其他分牌，則玩家獲得+50分。

“拱豬”分為亮牌階段和出牌階段。在亮牌階段，玩家可以將初始手牌中的黑桃Q、方塊J、梅花10以及紅桃A亮出，被亮出的牌分值將變為原來的2倍，若梅花10被亮出，則其翻倍效果由原來的2倍變為4倍。除了玩家手中僅有一張與首家出牌花色相同的牌之外，亮牌階段中被亮出的牌在該花色的第一輪不能打出。在出牌階段，在首輪出牌中，一般由擁有梅花2的玩家先出，首家出的牌被稱為“首引”，后續玩家出牌的花色必須與“首引”花色相同，若玩家手牌中沒有與“首引”花色相同的牌，則可以選擇一張其他花色的牌打出，稱為墊牌，墊牌在每一輪出牌中規定為最小，相同花色牌中，A最大，2最小。在一輪出牌結束后，出牌最大的玩家將贏得本輪出的所有牌，并作為下一輪首位出牌玩家。

在游戲結束后，若某位玩家贏得了所有紅桃花色的牌，該玩家將獲得+200分，如果在亮牌階段紅桃A被亮出，則獲得+400分；若某位玩家贏得了所有分牌與梅花10，那么該玩家將會獲得+800分。在“拱豬”中，最終得分最多的玩家為贏家。規則詳情請參見《中國華牌競賽規則(試行)》[14]。

1.2 數據格式設計

在“拱豬”人工智能模型構建中，亮牌階段使用1×4的one-hot矩陣對亮牌狀態與動作進行編碼；出牌階段使用1×52的one-hot矩陣對狀態和動作進行編碼。“拱豬”規定每位玩家每輪只能出一張牌，1×52的one-hot矩陣可以用不同位置的元素來表示對應牌的不同狀態，矩陣位置相對應的元素為1表示出此牌，為0則不出。可被亮的牌在矩陣中的位置對應關系如表2所示，出牌階段所有牌在矩陣中的位置對應關系如表3所示。

表2 可被亮的牌在1×4的one-hot矩陣中的位置

表3 不同牌在1×52的one-hot矩陣中的位置

除手牌外，1×52的one-hot矩陣還可以編碼任意玩家贏得的牌、已出的牌、亮牌等信息，這些信息被編碼后可以很容易地被神經網絡接收并處理，某位玩家的手牌信息編碼如圖1所示。1×52的one-hot矩陣僅僅只能表示位置信息，而某位玩家的出牌順序信息也至關重要，使用13×52的one-hot矩陣可編碼某位玩家每輪次的出牌信息。玩家歷史出牌的信息具有時序性，可以使用LSTM來處理此編碼后的信息。

圖1 1×52的one-hot矩陣對某副手牌進行編碼

2 深度蒙特卡洛算法

深度蒙特卡洛樹算法是在生成蒙特卡洛過程中使用深度神經網絡代替Q學習中的Q表來完成Q(s,a)的更新，該方法已經在“斗地主”中得到成功應用[11]。本文是將該算法移用于“拱豬”博弈研究中。

2.1 傳統型蒙特卡洛算法

傳統型蒙特卡洛算法屬于強化學習算法的一種。強化學習是指智能機器人如何在環境中采取不同的行動以最大程度地提高積累獎勵[15]，一個典型的強化學習框架由智能代理Agent、環境Environment、狀態State、動作Action、獎勵Reward以及行動策略π構成。“拱豬”游戲中，智能代理Agent在亮牌和出牌階段分別執行亮牌動作Action和出牌動作Action，當Agent執行某個亮牌或者出牌動作后，亮牌或出牌環境Environment會轉換到一個新的狀態State，即玩家亮牌情況或出牌局面發生變化，對于新的狀態，環境會給出獎勵信號(正獎勵或者負獎勵)。智能代理根據新的狀態和環境反饋的獎勵，按照一定的亮牌或出牌的行動策略π來執行新的動作。

狀態State與動作Action之間的關系由式(1)決定，其中，π為智能代理的策略。

π(State)=Action

(1)

2.2 改進型蒙特卡洛算法

傳統的蒙特卡洛算法和Q-learning算法是通過Q(s,a)去決定策略π，即智能代理根據Q(s,a)來選取獲得最大收益的動作。評估Q(s,a)的方法為求所有episode訪問(s,a)所得到的回報均值。Q值的更新函數如式(2)所示。其中R為回報函數，γ為折扣因子,ρ為學習率。

Q(s,a)←Q(s,a)+ρ(R+γmaxa′Q(s′,a′)-Q(s,a))

(2)

Q值的評估和更新過程可以很自然地與神經網絡結合，從而得到改進型的蒙特卡洛算法，即深度蒙特卡洛算法。具體來說，使用神經網絡和均方誤差來代替Q表完成Q(s,a)的更新。深度蒙特卡洛算法的偽代碼如下所示。

深度蒙特卡洛算法偽代碼：

輸入:狀態-動作對(s,a),學習率ρ,折扣因子γ

輸出：新狀態s

初始化：Q(s,a)

for iteration = 1,2,3,…… do (每個episode)

Initializes

for t = 1,2,3,…,Tdo (episode每個步驟)

Chooseafromsusing policy derived fromQ

Take actiona,observeR,s′

Q(st,at)←Q(st,at)+

(使用神經網絡和均方誤差相結合的方法)

s←s′

Untilsis terminal

end

end

第一個for循環中使用epsilon-greedy算法來對生成的episode進行選擇，可以最大程度地提高收益[16]，避免模型對預期收益較低的情況進行訓練。

第二個for循環中的平均回報可通過計算所有(s,a)折現的累計獎勵獲得，改進型蒙特卡洛算法使其能夠應用在神經網絡中。傳統的蒙特卡洛算法依賴Bootstrapping的Q學習過程繁瑣且訓練神經網絡需要的時間較長[17]，而基于改進型蒙特卡洛算法的Q學習對于一組(s,a)的平均回報能夠直接逼近目標Q(s,a)，這將大大縮短模型訓練的時間。

傳統的蒙特卡洛算法由于高方差的原因，處理非完備信息博弈時效率十分低下。深度蒙特卡洛算法已經在“斗地主”中得到了很好的驗證，其算法也同樣十分適合“拱豬”游戲。第一：“拱豬”同樣是一個回合性的任務游戲，它并不需要處理不完整的回合信息；第二：深度蒙特卡洛算法可以很容易地進行并行計算，每秒可生成更多的樣本數據，提高了訓練效率，同樣可以解決“拱豬”的高方差的問題。第三：“拱豬”智能代理是在沒有獎勵的情況下對游戲狀態和動作進行模擬，這種情況同樣會減慢Q學習的速度，讓模型變得不易收斂，而采用深度蒙特卡洛算法可以減少這種長時間無反饋帶來的影響[11]。因此，將深度蒙特卡洛算法應用到“拱豬”游戲中是具有可行性的。

3 神經網絡結構

“拱豬”有非時序性與時序性2種數據，對于非時序性數據，直接使用one-hot矩陣進行編碼并展平不同特征的矩陣進行連接。對于時序性數據，使用LSTM進行相應的處理，一個典型的例子是將某對手玩家的歷史出牌數據存儲至13× 52的矩陣中，如果玩家尚未出完13輪，則使用零矩陣來表示缺失的輪次。相比于其他傳統的神經網絡結構，LSTM可以更好地處理時序性數據[18]，該算法所需數據較少，能更好適應“拱豬”游戲中的時序性數據。圖2展示了“拱豬”人工智能模型內部的具體細節，基于蒙特卡洛的Q網絡由一個LSTM和6層隱藏維度為512的多層感知機組成。這個網絡將根據游戲狀態與動作來預測給定的Q(s,a)值。

圖2 “拱豬”Q網絡結構模型

“拱豬”是在游戲結束時才能準確計算每位玩家的分數，所以在整個游戲過程中，“拱豬”人工智能模型需要在沒有獎勵的情況下對游戲狀態和行動進行模擬，只有當游戲結束時，才能準確獲得這一局游戲的獎勵。這種情況會減慢Q學習的速度，讓模型變得不易收斂，而采用基于深度蒙特卡洛算法的神經網絡結構可以有效地解決長時間無反饋所帶來的影響。

4 模型訓練過程

4.1 模型特征選擇

在參與“拱豬”游戲時，玩家需要關注以下幾個方面的信息：自己的手牌、還未出現的牌、自己贏得的牌、其他人贏得的牌、被亮的牌、其余人打過的牌等，這些信息將可決定玩家在出牌時的選擇。表4為參與游戲的“拱豬”人工智能模型游戲代理所選用的特征參數。

4.2 并行訓練

在計算資源有限的情況下，采取并行訓練可以在單位時間內進行更多次的模型迭代與更新，很大程度上提高了模型的訓練效率。

表4 “拱豬”人工智能模型選用的參數特征

在構建“拱豬”人工智能模型時，將首輪第一個出牌的人工智能模型代理記為A，逆時針方向上的3位玩家分別記為B、C、D。

進程分為兩類：actor進程與Learner進程，actor進程產生訓練所需數據，Learner進程對網絡進行訓練與更新。“拱豬”的分布式并行訓練框架如圖3所示。

圖3 “拱豬”分布式并行訓練框架

本文深度神經網絡的訓練過程分為1個actor進程和1個Learner進程，其中actor為總進程，actor進程包含4個玩家的actor進程。Learner進程將為4個actor進程存儲4個Q網絡，這4個Q網絡被稱為各個位置的全局網絡，這4個全局Q網絡將會根據對應actor進程的均方誤差進行更新以接近目標值。同時，每個actor進程也存儲了4個Q網絡，這4個Q網絡被稱為各個位置的本地Q網絡。在整體訓練框架中，本地Q網絡將會在一定訓練時間后更新為全局Q網絡，Actor進程將從整體游戲環境中獲取計算所需的信息并以此更新不同條件下的Q(s,a)。Learner進程與Actor進程之間的通信通過緩沖區進行，每個緩沖區被區分為不同的數據區，不同數據區中存儲著游戲運行與模型訓練所需的關鍵數據。

4.3 模型訓練參數

“拱豬”人工智能模型訓練的過程采用分布式并行計算的方式進行，分布式并行計算框架的參數如表5所示。

表5 “拱豬”人工智能模型分布式并行計算參數設置

在單臺GPU的服務器上訓練24 h后，初步得到一個“拱豬”人工智能游戲代理。

“拱豬”人工智能模型訓練代碼及測試文件見https://github.com/Zhm0715/GZero。

5 實驗結果及分析

5.1 重要指標分析

在“拱豬”人工智能模型游戲代理的訓練過程中，actor進程為游戲中的每個位置(A、B、C、D)都訓練了一個自對弈的游戲代理。對于每一個episode，訓練環境將隨機生成一組手牌，4個游戲代理將在非完全信息的條件下進行自對弈。游戲結束后，該局游戲生成的訓練數據將被傳遞給Learner進程進行全局Q網絡的更新，并將這種更新同步至Actor進程的本地Q網絡。圖4展示了訓練過程中的Loss值與訓練數據量的關系。

由圖4可知，4個方位的游戲代理整體的Loss值隨著訓練數據量的增加而減少，這說明模型在經過訓練后逐步趨于局部或整體最優值。對于某方位的游戲代理，在訓練過程中會出現Loss值突增后再回落的現象，這主要是由于該模型訓練過程中采用了epsilon-greedy算法來避免4個方位的游戲代理同時陷入局部最優值導致訓練效果下降。

圖4 Loss值與訓練數據量的關系

除了Loss值，一局游戲最終的得分也至關重要。圖5展示了訓練過程中的episode返回的獎勵與訓練數據量的關系。為便于計算，此處獎勵值為原始分數值的1/100。

圖5 episode返回的獎勵與訓練數據量的關系

由圖5可知，A方位玩家的episode獎勵隨著訓練次數的增加而下降，而其他方位的玩家則表現出了episode獎勵不穩定的情況。在訓練初期，A方位的游戲代理表現得比其他方位的游戲代理更好；在訓練中后期，B、C、D方位的游戲代理表現得比A方位的游戲代理更好。

在訓練完成后，本模型與擬合了20 000條真實人類玩家對局數據的卷積模型游戲代理對弈了10 000局，該模型獲得了78.3%的勝率。表6為模型評估的關鍵參數。

表6 對弈結果關鍵參數

由表7可知，該模型返回的平均episode激勵為0.67，這表明了在10 000局對弈中，該模型游戲代理最終分數為正的局數為7 830局，平均每局獲得67分。除了North方位的游戲代理采用基于深度強化學習的“拱豬”人工智能模型外，West、South、East方位的游戲代理均采用卷積模型，這3個方位的游戲代理平均每局獲得的分數均為負數。由實驗結果可知，該模型在與卷積模型游戲代理進行對弈時能夠獲得巨大優勢。

5.2 算法成功分析

通過基于深度蒙特卡洛算法的模型與基于卷積模型之間的對弈，分析本文所提算法性能的優越性。卷積模型主要采用已有的少量且質量不高的真人玩家的對局數據，通過監督學習的方法，使智能代理能夠擬合人類玩家的游戲策略。這種算法高度依賴數據的質量和數量，無法很好地利用先前已學到的知識，更為重要的是，該算法也無法探索已有數據之外的知識，導致智能體的水平很難得到進一步地提升。由對弈結果數據分析可知，基于深度蒙特卡洛算法的智能代理在勝率上要遠高于基于卷積算法的智能代理，這是由以下深度蒙特卡洛算法的3個優點所決定的。

第一，它不需要高度依賴于訓練數據的數量和質量，可以自然地模擬人類的行為并進行評估學習，采用分布式并行計算的方式可以在每秒內產生多組訓練數據，大大地提高了訓練的效率，可有效解決高方差問題；第二，相較于卷積算法模型，深度蒙特卡洛算法模型可以很好地權衡利用和探索，在訓練過程中不僅可以利用先前已學到的知識，還可以輕易地探索到人類玩家不常見的狀態與動作并進行訓練與學習，可有效地提高智能代理的游戲水平；第三，在大量的自對弈過程中，偶然的錯誤動作及其評估不會決定著最終訓練的效果，可以減少低質量數據對實驗結果的影響。

5.3 示例分析

在指標參數之外，“拱豬”人工智能游戲代理在實戰中的表現也讓人欣喜。圖6展示了在某局游戲中“拱豬”人工智能游戲代理的對局情況。

圖6 某局中“拱豬”智能代理出牌動作

由圖6可知，在本局游戲的第2輪中，East方位的游戲代理首先出牌，因其手牌中含有黑桃Q和多張負分較大的紅桃牌張，且只有一張梅花花色的牌，故游戲代理選擇將惟一一張梅花花色的梅花6打出，在后續的游戲過程中，其他玩家出黑桃或者紅桃花色牌時，可以迅速將負分牌打出，避免獲得較多負分牌而輸掉游戲。

在本局游戲的第11輪中，North方位的玩家首先出打出方塊Q，隨后West方位的玩家打出一張黑桃，說明此時的West方位玩家手中已經沒有方塊花色牌張。結合游戲歷史出牌信息，從South方位玩家的視角來看，此時未被打出的方塊花色牌只有方塊J和方塊4，且North方位玩家先出方塊Q，其目的很可能是想得到方塊J從而獲得正分，所以可以推測出玩家North手中沒有方塊J的可能性較大，在這種情況下,East方位玩家手牌中有且僅有一張方塊花色的牌，即為方塊J，此時South方位玩家打出方塊A就有很大的幾率得到East方位玩家手牌中的方塊J，從而使自己獲得正分。

6 結論

將在“斗地主”游戲中表現優異的算法移用于“拱豬”博弈研究中，利用蒙特卡洛方法與深度神經網絡相結合的方式，構建了一個基于分布式并行計算的自對弈“拱豬”人工智能模型。該模型概念簡單，訓練高效。通過評估訓練的結果可知，該模型比采用深度神經網絡擬合人類玩家對局數據的人工智能游戲代理表現出更好的性能。

盡管該模型的人工智能游戲代理的表現讓我們欣喜，但仍有很多問題尚待解決。例如是否有其他網絡結構比現有的模型訓練效果更好？該模型能否根據游戲現有信息對其他玩家手牌進行預測？該模型是否能夠在其他類似問題上取得預期的效果？這些問題都將在后續研究中進行探索。