二打一游戲拆牌算法研究

喬秀明,黃文杰,2,李淑琴,2

(1.北京信息科技大學 計算機學院， 北京 100101；2.感知與計算智能聯合實驗室， 北京 100101)

0 引言

機器博弈是人工智能研究的重要領域，是檢驗人工智能發展水平的一個重要平臺。根據博弈信息是否可以完全可知，可分為完全信息博弈和非完全信息博弈[1]，如代表完全信息博弈的圍棋、象棋等和代表非完全信息博弈的二打一、麻將等。在完全信息博弈中，谷歌的“Alphago Zero”[2]達到計算機博弈領域的新高度，為完全信息博弈游戲提供了通用解決方法，計算機棋手逐漸達到了職業玩家的水平，甚至超過人類玩家，這其中深度學習在游戲中起到了很大的作用。在非完全信息博弈中，玩家的操作范圍龐大，如有限注德州撲克，其所有信息集數量達到了(3.19×10)14，參與者要基于信息集進行決策[3]。對信息集中歷史狀態的數量關系和問題的規模及復雜度通常采用的簡化方法有：使用在完全信息博弈中[4]應用廣泛的蒙特卡羅樹搜索[5]和對博弈樹的抽象化[6]。博弈樹的抽象化本質是采用一種方法將復雜的博弈樹狀態節點合并，通常使用聚類或者分類方法。2017年，CMU設計的Lbratus[7]使用抽象方法以細化狀態空間和策略空間[8]，Andre按照勝率進行聚類，引入狀態空間算法和整數規劃對牌型進行抽象化[9]。

二打一(俗稱斗地主)[10]是一款集趣味性、廣泛性、專業性于一身的3人棋牌游戲，作為研究非完全信息博弈的典型問題，受到人工智能領域內專家越來越多的關注。目前文獻[11]在對二打一手牌水平評估的過程中直接以單張手牌為單位進行手牌水平分析，并以單張牌的編號所對應的角色進行分配，使用生成對抗網絡來達到控制手牌水平的目的。但是，其未考慮到牌與牌之間按照出牌規則的組合方式。文獻[12]使用二打一出牌機器人進行自博弈來對二打一手牌水平進行評估。雖然對二打一手牌進行研究的成果多種多樣，如文獻[13]基于權值對二打一手牌進行了拆分，但是模擬人類玩家拆牌的研究卻少有記錄。本文在對二打一手牌拆分研究的過程中受到自然語言處理領域序列標注任務的啟發，使用基于深度學習的BILSTM-CRF模型[14]作為建模方法嘗試對二打一初始手牌進行牌型標注訓練，在與傳統的最小組合拆分法進行比較后，獲得了初步的成效。

1 二打一手牌拆分模型

1.1 手牌拆分意義

手牌拆分指將當前手牌(初始手牌或對局中某個時刻的手牌)按照出牌規則拆分成合法牌型。拆牌效果的好壞影響這個打牌過程。對于人類玩家來說，每次進行二打一游戲對戰時，在確定好自己的初始手牌后，玩家都會對自己的初始手牌進行在心理層面的預拆分，即回答如何拆分出能夠壓制住對手的牌型、如何拆分出能夠在主動出牌時確立主動權的手牌、如何拆分才能把牌面較小的手牌打出去等系列問題，完成初步的拆牌規劃。對于新手而言，如果能夠利用拆牌模型，在每次出牌前進行手牌拆分，就可以有效地輔助自己的出牌決策，對于二打一計算機博弈智能體而言，也具有重要的借鑒意義。

此外，在機器學習或深度學習對手牌的研究過程中，僅僅以單張牌為單位，用數字化分析和建模整個手牌序列，實際上是難以體現規則中的牌型壓制關系的，所以，針對手牌水平評估的研究與手牌拆分存在密不可分關系的。

1.2 二打一手牌牌型

對于任意一條完整的二打一打牌數據，包括了勝者打出的手牌數據和敗者打出的手牌數據，其中勝者因優先將手牌打完而取得勝利，其中在打牌過程產生完整的手牌拆分時序序列信息，自然可以提取出來作為訓練之用。按照規則，二打一游戲的合法出牌牌型包含的常見牌型如下：

(a)火箭：由小王和大王兩張牌組成，可以壓制其他一切牌型。當且僅當大王和小王同時在一名玩家手中才能被打出。

(b)炸彈：由4張牌面大小一樣的牌組成，可以壓制除火箭和炸彈外的其他所有牌型，也可以壓制比自己牌面小的炸彈，比如“4444”可以壓制“3333”但是不能壓制“5555”。

(c)單張：由單張手牌組成的出法，如“3”，“4”，“5”等。

(d)單順：由連續的單張手牌組合成長度不少于5張的牌，如“34567”，“345678”，“45678”等。

(e)對牌：由2張牌面相同的牌組成的出法，如“33”，“44”，“55”等。

(f)雙順：由至少3組連續的對牌組成的出法，如“334455”，“33445566”，“445566”等。

(g)三張：由3張牌面相同的牌組成的出法，如“333”，“444”，“555”等。

(h)三順：由至少2組連續的3張組成的出法，如“333444”，“333444555”，“444555”等。

(i)三帶一：由3張牌型額外附帶單張牌，附帶的單張牌在壓制上不用比較大小，如“3337”，“4445”等。

(j)三帶一對：由3張牌型額外附帶對牌，附帶的對牌在壓制上不用比較大小，如“33377”，“44455”等。

(k)飛機帶翅膀：由三順牌型額外附帶單張牌或者對牌，附帶的對牌在壓制上不用比較大小，附帶的牌型要一致，如“33344467”，“333444555789”，“3334448899”等。

(h)四帶二：由炸彈牌型額外附帶2張單牌或者2個對牌，附帶的單牌或對牌在壓制上不用比較大小，附帶的牌型要一致，如“333345”，“44445588”等。

1.3 基于手牌牌型標注的拆分方法

手牌序列的拆分和NLP(自然語言處理)領域中的中文命名實體識別任務極為相似，都是通過對序列的標注來實現對序列的劃分。中文命名實體識別方法可以在每個字上進行標注，標注出句子中的名詞、動詞等，并按照標注的結果對句子進行劃分，用于后續的下游任務，如用B(Begain)、E(End)、V(Verb)將“我們愛祖國”這句話標注成“BEVBE”，并根據標注結果將這句話拆分成“我們”、“愛”、“祖國”3個實體。同理，可將組合成手牌序列的牌型看作要標注的實體，通過標注來進行拆分。

根據現有的數據資源，參考中文命名實體識別中的主流深度學習模型BILSTM-CRF，運用獨特的標簽信息提取思路，提出了基于BILSTM-CRF模型的手牌牌型標注的拆分方法。BILSTM-CRF模型是由雙向長短期記憶網絡(BILSTM)和條件隨機場(CRF)組成的復合深度學習網絡模型。其中雙向長短期記憶網絡可以提取到序列中前后之間的聯系，條件隨機場可以學習到序列中單位與單位之間狀態的前后聯系。BILSTM-CRF模型多用于序列標注任務，尤其在中文命名實體識別工作中應用廣泛。二打一初始手牌也是單一的序列，因而可以設計建模對整個序列進行牌型的類別標注，并將標注結果轉化為手牌牌型的拆分。為獲取人類玩家對手牌的拆分特征，需要通過監督學習的方式從人類玩家真實對戰的過程中提取到人類玩家的拆牌方式。

2 二打一拆牌模型設計與實現

2.1 手牌牌型標注

根據二打一計算機博弈規則和利用前述(a)～(h)，進一步實戰對局數據分成4類牌型，分類信息用標注序號0、1、2、3所示，如表1所示。

表1 牌型標注示例

在表1中，由于單順是由單張組合而成，單張和單順被劃分為第0類。拆牌過程中，在處理大量單張時，若存在至少5張連續的單牌，則可以組成單順。由于連對是由對牌組合而成，對牌和連對被劃分為第1類。拆牌過程中，在處理大量對牌時，若存在至少3組連續的對牌，則可以組成連對。由于三順是由3張組合而成，三張和三順被劃分為第2類。拆牌過程中，在處理大量三張時，若存在至少2組連續的三張，則可以組成三順。炸彈和火箭被劃分為第3類，因為炸彈和火箭均可以去壓制其他類型的牌型，屬于壓制性的牌型。在拆牌過程中，應考慮是否拆分出壓制性的牌型或者將壓制性牌型拆分成其他類型的牌型。三帶一、三帶二、飛機帶翅膀、四帶二不納入分類范疇，因其由3張、炸彈、單排和對牌組合而成，屬于二次組合后的復合牌型。

對一副手牌序列的每一張手牌，以表中的標注序號作為序列的標注表示，如手牌序列“34445556789TA22XD”可以由牌型{3，444555，6789T，A，22，XD}組成，該牌型集合中的牌型為{單牌(c)，三順(h)，單順(d)，單牌(c)，對牌(e)，炸彈(a)}。將牌型集合中的牌型依照表1進行標簽轉化，得到標注{0，222222，00000，0，11，33}，因此該手牌序列的標注信息為“02222220000001133”。

2.2 基于BILSTM-CRF的拆牌模型設計

基于BILSTM-CRF的拆牌模型網絡結構如圖1所示。首先將每一張牌進行向量賦值，并輸入到BI-LSTM網絡中，通過全連接層網絡輸出包含四種標注類型的分數。然后建立CRF狀態轉移矩陣，用CRF層去訓練牌與牌之間標注類型狀態轉移關系，最后將BI-LSTM網絡對標注的打分，和CRF層對標注的打分進行求和，并選取總得分最高的標注類型作為當前手牌的標注類型。

圖1 BILSTM-CRF模型網絡結構框圖

因手牌序列標注，需要考慮到每張手牌與其他手牌前后之間的關系，故選用BILSTM-CRF網絡，對手牌以單張手牌為單位進行向量讀取，BI-LSTM層的輸出連接到全連接輸出層，輸出維度為4，即對4種標注牌型的打分。全連接輸出層對每一張牌屬于4種牌型的分數進行輸出。每張牌的對應的分數h表示為式(1)，其中k代表手牌序列中第k個位置的手牌，k=1,2,3,…,L,其中L為序列長度。

ek∈{hk1,hk2,hk3,hk4}

(1)

對于長度序列為L的初始手牌序列，共產生N=L4種標注情況。每種標注情況在手牌序列中的總得分如式(2)所示，n=1,2,3…N,表示每種情況下的標注結果。

(2)

BI-LSTM層輸出的結果在歸一化后產生的預測結果并不能保證對于手牌的給出的標簽完全符合拆牌的規范，因而在模型中添加CRF層。在CRF層里，建立一個隨機初始化的狀態轉移矩陣，矩陣的規格為6*6。狀態轉移矩陣的橫縱坐標都表示為start狀態、4種牌型、end狀態。根據6種狀態和長度為L的手牌序列，建立長度為L+1的狀態轉移分數進行求和。狀態轉移序列求和表達式表示為式(3)。

Tn=mstart,1+m1,2+m2,3+…+mL-1,L+mL,end

(3)

CRF單個狀態轉移分數mij表示為式(4)。

(4)

CRF狀態轉移矩陣的含義是：對于橫軸第i個狀態和縱軸第j個狀態，從第i個狀態轉移到第j個狀態(在手牌序列中從前一張牌標注牌型結果的狀態，轉移到后一張牌標注牌型結果的狀態)的分數表示。CRF狀態轉移矩陣在隨機初始化后，其數值會隨著訓練的進行通過梯度下降更新。

網絡模型對N種標注情況下每種情況的得分表示為BI-LSTM層和CRF層在該種情況下對應的分數之和并取e的指數冪：

Pn=exp(En+Tn)

(5)

統計所有N種情況下Pn之和作為分母，將來自于訓練數據中真實存在的標注示例(即理想狀態下的標注結果)下計算得到的Pn作為分子Prealpath。損失函數取兩者的對數損失函數，如式(6)所示。

(6)

式(6)中，目標函數的更新趨勢是盡可能使分子所對應的目標分數增大，可以視為極小化對數損失函數。

3 實驗與分析

訓練環境的服務器配置為Windows 10操作系統；NVIDIA GeForce GTX 2070super顯卡，8GB顯存；pytorch版本1.4.0。數據為聯眾公司提供，共430萬條，其中有290萬局地主獲勝，140萬局農民獲勝。在訓練前，從地主數據集和農民數據集中共劃分出2 000條作為測試集數據使用。對于模型的準確率計算，以測試集上每張手牌的來自模型輸出的標注結果和來自原始數據的標注結果的符合比例作為檢驗模型訓練效果的標準。

3.1 二打一手牌拆分

用于訓練的每條數據的信息如表2所示。

表2 單條數據信息

表2展示了每條完整牌局所提供的有效信息，包括三方玩家的初始手牌、3張底牌以及從玩家0開始到玩家2結束的完整打牌過程。打牌過程是以先手玩家0作為地主，最后一名出牌玩家2是獲勝方(最先將所有手牌全部打出)。提取獲勝方玩家2在牌局中所打出過的完整手牌{3AAA，68TTTJJJ，KK，22，9}，將帶牌進行拆分{3，AAA，6，8，TTTJJJ，KK，22，9}。因此，根據表1的標注序號分類，將原手牌序列“3689TTTJJJKKAAA22”的拆分標注為“00002222221122211”

3.2 模型的訓練效果

經過多次調參訓練得到模型的最優結構，其超參數配置見表3。

表3 超參數配置

隨著訓練次數的增加，模型的準確率提升至89.16%，準確率隨訓練次數的變化如圖2所示，可以看出，隨著訓練次數的增加，模型在測試集上的準確率逐漸提升。

圖2 準確率隨訓練回合數的變化趨勢

3.3 效果分析

模型訓練完畢后，將需要進行拆分的手牌輸入模型，產生標注結果，按照拆分標注表的示例將手牌按照標注結果劃分成四類，每類結果進行牌型的合并，將連續至少5張的單牌組成單順，將連續至少3組的對牌組成雙順，將連續至少2組的三張組成三順。拆牌結果示例如表4所示。

表4中，當模型訓練完畢時，將示例手牌以從大到小的方式輸入到模型中，模型輸出每張手牌對應的手牌標注類型序號。如手牌“X2AAQQQJJTT988774”對應的拆分標注結果為“0,0,1,1,2,2,2,1,1,1,1,0,1,1,1,1,0”和手牌“2AKKKQQ9998888555”對應的拆分標注結果為“0,0,2,2,2,1,1,2,2,2,3,3,3,3,2,2,2”。將標注好的手牌按照標注的4種類型進行歸類。對于標注為0的類型的牌，判斷是否能湊成順子并合并；對于標注為1的類型的牌，先將單張手牌組成對牌，然后再判斷是否能湊成連對并合并；對于標注為2的類型的牌，先將單張手牌組成三張，然后再判別是否能湊成三順并合并；對于標注類型為4的牌，將火箭和炸彈直接進行拆分，得到單獨拆分出的火箭和炸彈的牌型。從表3中的結果來看，BI-LSTM+CRF模型在對二打一初始手牌標注上產生了良好的效果。

表4 拆牌結果示例

為了評估BILSTM-CRF模型對于在拆牌上的可靠性，實驗引入了基于文獻[15]的傳統手牌拆分方法的性能對比，該方法以最小拆分組合數為最終目標，其步驟為：

步驟1首先對牌型三張、炸彈、順子、連對和三順排列組合成不同優先級組合H1,H2,…,H40，其中，需要排除掉三張牌型優先級高于炸彈和三順的情況，共計40種組合。建立一個空的集合。

步驟2依次遍歷40種優先級組合，在每個優先級組合下，按照牌型的組合順序中優先級的高低依次選擇較高優先級的牌型對手牌進行拆分，從每一種優先級組合中產生若干組手牌拆分序列。

步驟3將第1組拆分序列插入集合中，并重復步驟2，依次循環直到遍歷完40種優先級組合。從第2組開始，每新產生一組拆分結果，變計算該拆分結果的拆分數目，若該拆分數目小于集合中的最小拆分數目，則將該拆分結果加入集合中，直至優先級組合遍歷完畢。

步驟4選取集合種拆分數目最小的拆分結果作為待拆分手牌的拆牌結果。

在430萬對戰數據的基礎上，使用基于梯度提升樹的XGBoost算法訓練出二打一的出牌AI。隨機生成1 000副初始手牌。對于每一副初始手牌，分別得到傳統最小組合拆分法的拆分結果h={h1,h2,…,hi}和BILSTM-CRF模型的標注拆分結果g={g1,g2,…,gj}，并通過AI進行對打，統計對局中AI在前5次主動出牌(根據是否進行跟牌的狀態分為主動出牌和被動出牌)下打出牌型(A1,A2,…,Aa,B1,B2,…,Bb,C1,C2,…,Cc)，其中ABC分別代表二打一對戰中3個角色打出的牌型。分別統計AI打出的牌型中存在于集合h和集合g的比例Ph和Pg，性能結果如表5所示。

表5 性能結果

傳統最小組合拆分法雖然能快速有效地產生手牌拆分結果，但是二打一的對局變化多端，拆分出的牌型并不能保證和對局中AI打出的牌型完全相符。而BILSTM-CRF模型的標注拆分法是基于人類玩家對局中的拆分結果進行拆分，該方法所產生的拆牌結果相比之下更能反映在實際玩家對戰中對手牌的拆分結果。

4 結論

基于聯眾提供的真人二打一游戲對戰數據構建了手牌拆分的真實數據集，數據規模達到了430萬條，為后續拆牌研究提供了數據基礎。提出基于BILSTM-CRF構建手牌序列標注模型，實驗證明了該模型在手牌拆分任務上的有效性，表明了通過對二打一手牌進行序列標注實現模擬人類手牌拆分的可行性，拓寬了BILSTM-CRF模型的應用領域。