李淑琴,馮浩東

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

0 引言

自古以來，博弈就是一個經典的研究領域，人類生活中每時每刻都在做著平衡與決策。每天的衣食住行、升學就業(yè)時的選擇、購物消費時的優(yōu)惠折扣、國與國之間的經濟競爭和軍事競爭，等等，這些問題場景都可以抽象成博弈決策問題。根據不同的角度，可以把博弈分為不同類型。根據博弈參與者對整個博弈狀態(tài)的了解程度可以把博弈分為完全信息博弈和非完全信息博弈。在麻將游戲中，玩家只能看到自己的手牌信息和一些公共信息，而對手的手牌信息以及牌庫中的信息都是不可見的。因此，麻將是典型的非完全信息博弈。

在完全信息博弈領域，當前最出名的是谷歌公司DeepMind團隊開發(fā)的Alpha系列程序[1-4]，徹底擊敗了人類選手。與其不同，非完全信息博弈的解決面臨諸多難題。第一，狀態(tài)空間巨大。由于在非完全信息博弈中沒有辦法得知當前局面的全部信息，所以需要進行大量模擬來求解未知信息。非完全信息博弈的決策動作一般也不是固定的，例如德州撲克和斗地主中可以采取過牌操作，麻將中可以進行吃、碰、杠等操作，這都會使局面信息更加復雜。這些原因導致非完全信息博弈的狀態(tài)空間非常龐大。第二，信息缺失。不同于完全信息博弈，非完全信息博弈的參與者并不知道對手的私有狀態(tài)。這就意味著在完全信息博弈中的求解局部最優(yōu)解方法不適用于非完全信息博弈，且沒有辦法準確評估自己在整個博弈局勢中的優(yōu)劣。例如在象棋、五子棋等完全信息博弈中可以通過搜索和遍歷來得出最優(yōu)決策，但這在非完全信息博弈上是不可行的。

在非完全信息博弈中，德州撲克是最受歡迎的研究對象。參考文獻[5-7]使用反事實虛擬遺憾最小化算法在兩人有限注德州撲克上取得了近似納什均衡的效果。這是因為兩人有限注德州撲克的狀態(tài)空間小，因此反事實虛擬遺憾最小化算法是行之有效的。隨后，卡耐基梅隆大學的TSandholm團隊于2017—2018年提出了Libratus系列[8-9]程序，將改進的反事實虛擬遺憾最小化算法與安全子問題求解方法相結合解決了多人無限注德州撲克問題。Libratus沒有采用當時流行的深度學習方法和神經網絡模型，盡管取得了良好的效果，但是需要極大的計算資源。顯然，德州撲克的解決方法在麻將這種狀態(tài)空間爆炸的游戲中并不適用，因為其取得納什均衡的成本是極其高昂的。

在麻將領域，Cheng等[10]在2017年使用數學模型通過基本組合理論研究麻將游戲。王亞杰等[11]根據先驗知識和手牌信息給出麻將出牌決策，并使用蒙特卡洛模擬方法模擬對手手牌來防止點炮。雖然取得了不錯的效果，但其核心方法是大量的領域知識模型。對于棄牌信息的利用率不高，也沒有根據游戲狀態(tài)來動態(tài)調整先驗知識。針對非完全信息博弈和麻將游戲的特點，本文的工作目的就是充分利用麻將中的局面信息，尤其是棄牌信息，依此預測對手手牌和需求牌來縮減未知狀態(tài)空間，從而降低麻將游戲的難度。并使用動態(tài)游戲狀態(tài)劃分方法適時調整局面信息利用方法，提升其準確性。將本文方法應用于麻將程序后，大幅提高了麻將程序的勝率，并降低了點炮風險。

1 麻將的規(guī)則和術語

麻將作為一項智力競技運動，集益智性、趣味性、博弈性于一體。麻將自發(fā)明來一直深受社會各階層的喜愛。

1.1 麻將規(guī)則

本文的研究對象為大眾麻將，它是以國標麻將為基礎簡化而來。大眾麻將的特點為牌型組合多、番型多，幾乎涵蓋所有麻將番型，十分考驗麻將技巧與策略。牌庫中有萬、筒、條3種，點數分別為1～9，每個樣式的牌有4張，總共108張牌。莊家起手14張牌，其他3位起手13張牌。行牌過程，可吃、碰、杠和聽，并都可獲得直接收益。行牌過程的優(yōu)先級為：胡>杠>碰>吃。當有玩家成功胡牌或牌庫摸完后，牌局結束并給出總分。

1.2 麻將術語

本節(jié)對后文中將要提及的術語進行統一解釋。

順子：3張連續(xù)的牌稱為順子；

相關組：2張連續(xù)的牌或間隔為1的2張牌稱為相關組；

刻子：3張相同的牌稱為刻子；

對子：2張相同的牌稱為對子；

吃：當上一位玩家丟出一張牌，且可以與玩家手中的牌構成順子時，可以吃牌；

碰：當其他玩家丟出一張牌，且玩家手中有2張相同的牌時，可以碰牌；

杠：當其他玩家丟出一張牌，且玩家手中有3張相同的牌時，可以杠牌；

副露：玩家吃、碰、杠后，可以被所有玩家觀察到的牌型稱為副露；

莊家：第一個打牌的玩家被稱為莊家；

聽牌：當玩家只剩一張牌就可以達到獲勝狀態(tài)時，可以宣布聽牌；

向聽數：向聽數指玩家的手牌還差多少張牌可以聽牌。

胡：當玩家組成獲勝牌型，即4個順子或刻子、一個對子時稱為胡；

點炮：當玩家丟出的牌使對手達到胡牌狀態(tài)時，稱為點炮。

2 局面信息利用方法

在麻將中，因為玩家的棄牌與手牌具有一定的聯系，玩家的信息會隨著游戲進程的發(fā)展而不斷暴露。在麻將中轉換局面信息不僅可以幫助麻將程序做出更合理的出牌決策，也可以降低點炮風險，進而提高自己的收益。本文首先根據大眾麻將領域知識提出棄牌信息利用方法和對手牌型概率計算方法，然后進行蒙特卡洛模擬得到對手的手牌分布，實現對麻將局面信息的最大化利用。

2.1 棄牌信息利用方法

本小節(jié)將把對手玩家的棄牌信息轉換為可利用信息，并推算對手玩家持有某張牌的概率。在大眾麻將中，同一花色的連續(xù)牌是具有強關聯性的。針對大眾麻將的規(guī)則特點，本文將在游戲的前后期采取2種不同的棄牌信息利用方法。

按照當前局面的情形，根據式(1)計算每一張牌的剩余牌數。

Ni=4-NOi-NMi

(1)

式中：Ni表示牌i的剩余張數；NOi表示對手棄牌中牌i的張數；NMi表示我方手牌及我方棄牌中牌i的張數。

大眾麻將游戲前期，各個玩家都追求快速達到聽牌狀態(tài)，一般不會將關聯牌拆分打出，所以前期的方法將圍繞這一理念展開。與之對應，本文提出相依牌的概念。例如，若玩家丟棄某一花色的5點數牌時，其手牌中應該不會還有5，且在棄牌前應該沒有「4、5」、「5、6」、「3、5」、「5、7」等組合牌。因此，若某一玩家棄牌中有5，應降低該玩家持有該花色牌中3、4、5、6、7的概率。其中，持有5的概率最小，其次是4和6、3和7。類似的，以此為依據可以得出相依牌表，如表1所示。表中相依牌與棄牌的相依程度依次降低，隨著博弈的進行，相依程度還會進一步降低。此外，相依程度還與玩家的聽牌時機高度相關，需要動態(tài)調整。

表1 相依牌表

根據棄牌的數量和相依程度，可以得到某一張牌對所預測牌的影響度。計算方式如式(2)所示,式中Ai, j指牌i對牌j的影響度，Ni指棄牌中牌i的張數，Ri, j指牌i與牌j的相依程度。

Ai, j=Ni×Ri, j

(2)

根據某一玩家的棄牌信息可以給出該玩家擁有某一張牌i的可能性PRi，計算方法如式(3)所示。當牌的點數不同時，其對應的相依牌數目也不同，因此式(3)按牌的點數將牌分為了5類。

(3)

游戲進入中后期時，玩家的手牌已基本成型，玩家丟出的牌多數都是與手牌無關的。當玩家棄牌時，理論上也不需要跟這張棄牌相關的牌。與之對應，提出非需求牌的概念。例如，由于1可以跟2、3組成順子，當玩家打出1時，可能是該玩家手中并沒有「2、3」這個組合，或是手牌中已有「1、2、3」的順子，或是已經跟相鄰的4組合成「2、3、4」的組合，而不論是上述哪一個狀況，都可以推論該玩家對4的需求會降低。類似的，以此為依據可以得出非需求牌表，如表2所示。

表2 非需求牌表

非需求牌主要在防守階段使用，通過其他玩家的棄牌信息來推算其不需要的牌，并且在游戲終盤時根據非需求牌調整手牌的權重分，使其他玩家不需要的牌更容易被打出去，挑選棄牌時的依據會從進牌收益最高的牌，變成兼具進牌收益與防守收益的牌，以此降低自己的點炮概率。

2.2 對手牌型概率計算方法

在2.1小節(jié)中，已經得到了玩家手牌中持有某張牌的概率計算方法。以此為依據，下面對玩家手中持有刻子、順子、對子和相關組的概率進行計算。玩家手牌中擁有刻子牌型的概率計算方法如公式(4)所示。當牌A的數量小于3時，此時不可能存在由牌A組成的刻子；當牌A的數量大于等于3時，將根據牌A的數量和該玩家擁有該牌的可能性綜合計算擁有牌A刻子的概率。玩家手牌中擁有順子牌型的概率計算方法如式(5)所示。計算該玩家手牌中擁有順子中每張牌的可能性，選最小值作為擁有該順子的概率。與刻子和順子不同，本文在對子和相關組牌型的概率值計算上還考慮了棄牌中其需求牌的非需求牌數量，若其需求牌的非需求牌數量很多，說明對手玩家手中有此牌型的概率極低，如式(6)—(8)所示。

(4)

PABC=min(PRA,PRB,PRC)

(5)

(6)

PAB=min(PRA,PRB)-(NN(A-1)+NN(B+1))/2

(7)

PAC=min(PRA,PRC)-NN(A+1)

(8)

式中：PAB指連續(xù)相關組的概率計算方式；PAC指間隔相關組的概率計算方式；NNi指的是牌i的非需求牌數。

至此，手牌中各種牌型的概率計算方法已經成型，但對手玩家手中各種牌型的數目仍然無法確定。接下來需要模擬對手玩家的向聽數來確定玩家手牌分布。向聽數將根據由大量真實對局數據得出的每輪向聽數分布和玩家副露數計算得出，為

WN=1+GWN-F

(9)

式中：GWN指根據真實對局統計的向聽數概率分布隨機選擇得到的向聽數；F指玩家副露數。

2.3 對手手牌模擬方法

通過蒙特卡洛模擬方法來模擬對手手牌，不僅可以降低給對手打出需求牌的概率，還可以輔助判斷我方的需求牌數量，使我方牌型更加合理，增加獲勝概率。蒙特卡洛模擬是一種統計學方法，用來模擬大量數據。其核心思想就是通過模擬出來的大量樣本集或者隨機過程去近似想要研究的實際問題對象。對于那些由于計算過于復雜而難以得到解析解或者根本沒有解析解的問題，蒙特卡洛模擬是一種有效的求出數值解的方法。

在麻將游戲初期，暴露的信息過少，若在初期進行蒙特卡洛模擬，只會增加模型復雜度而不會產生收益，因此蒙特卡洛模擬將在游戲中后期進行。下面給出基于局面信息和蒙特卡洛的對手手牌模擬算法流程，將整個模擬過程迭代X次至結果收斂便可以得出對手手牌，還可以根據對手手牌模擬剩余牌庫分布。這樣，麻將游戲中的信息不透明度會進一步降低，便于麻將程序對博弈局勢做出更準確的判斷。對手手牌模擬流程如算法1所示。

算法1對手手牌模擬方法

輸入：我方手牌H，對手棄牌Di，對手副露Fi，輪數Round

輸出：對手玩家的手牌分布DHi

01：根據式(1)計算每一張牌的剩余牌數Ni

02： while(X-->0) do

03：根據式(9)計算出Round輪的向聽數WN

04：根據向聽數WN，隨機選擇刻子數NAAA、順子數NABC、對子數NAA、相關組數NAB

05：隨機生成刻子、順子、對子和相關組，根據公式(4)—(8)計算其持有概率，若概率極低則重新生成

06：根據隨機結果更新DHi

07：end while

08：returnDHi

3 動態(tài)游戲狀態(tài)劃分方法

在麻將游戲中，玩家的出牌與出牌時的游戲狀態(tài)是有密切聯系的，合理的前后期游戲狀態(tài)劃分方法可以提高局面信息利用的準確率。在以往類似的研究中[12-13]，常常以對大量數據樣本統計后的向聽數為1時的最大輪數分布為游戲前后期界線。該方法雖然可以代表多數情況，但其對于部分牌局情況的適應性較差，會降低局面信息轉換的準確性。所以本文提出了一種動態(tài)劃分游戲前后期界線的方法，可以根據當前局面信息對游戲前后期做出更為合理的分界，這會進一步提升局面信息的利用效率，從而提高麻將程序的出牌水平。

和以往的方式不同，本文以動作數為標準劃分游戲前后期，而不是游戲輪數。此處的動作包括摸牌、吃牌和碰牌。本文統計了3 000局真實對局中4位玩家每次動作后的向聽數分布，統計結果如圖1所示，頻次指在對應動作數下的指定向聽數出現次數。從圖中可以看出，部分牌局在執(zhí)行一次動作后，就有玩家達到了1向聽狀態(tài)。顯然，如果只依據向聽數為1的最大輪數分布進行前后期劃分，將使麻將程序進入歧途。而且在執(zhí)行動作3、4、5、6次后，都有很大概率達到1向聽狀態(tài)，顯然不能僅僅以1向聽的最大分布動作數4為前后期分界。

圖1 大眾麻將中向聽數隨動作數變化的分布圖

根據大眾麻將的游戲規(guī)則，吃、碰動作對向聽數的影響遠大于摸牌操作。因此本文還對吃、碰動作進行了額外的分析，統計了3 000局真實對局中4位玩家每次吃、碰動作后的向聽數分布。因為在執(zhí)行一次吃、碰動作后4向聽的頻次極低，因此在統計時將其忽略，最終的統計結果如圖2所示。從圖中可以看出，當玩家執(zhí)行2次吃、碰動作后，向聽數基本在2及2以下。

因此，本文將以向聽數為1時的最大分布動作數4為前后期分界基準，以每輪游戲中玩家的吃、碰動作次數為輔，對每輪游戲中各個玩家的前后期界線進行動態(tài)劃分，如式(10)所示。式中Di指針對i玩家的游戲前后期分界動作數，CPi指玩家i的吃碰次數。

Di=4-(CPi-1)

(10)

圖2 大眾麻將中向聽數隨吃、碰動作數變化的分布圖

4 實驗結果與分析

本文結合局面信息利用方法和動態(tài)游戲狀態(tài)劃分方法構造了一個麻將AI程序，為了證明其可靠性，在本節(jié)進行了大量實驗。在每輪對局中，采用2+2的對戰(zhàn)策略，即2位使用A方法的麻將程序和2位使用B方法的麻將程序進行對戰(zhàn)。為了消除麻將游戲中靠運氣取得勝利的因素，本文設定了1 000局對局為標準來驗證各個方法的有效性。根據麻將規(guī)則，玩家只能吃上家的牌。因此需要考慮不同程序之間的座位順序，在實驗時通過調換每輪游戲中麻將程序的座位順序加以解決。為了便于對比，將2個使用相同程序的對局結果累加，將點炮率、獲勝率和得分作為比較標準，給出實驗結果。

4.1 對比實驗

4.1.1局面信息利用方法的影響

正如前文所說，局面信息利用方法的目的是通過轉換局面信息降低麻將游戲局面的不透明度，從而提高麻將程序的出牌水平，并降低麻將程序的點炮率。為了證明其有效性，本文將其與傳統的使用追求快速聽牌方法的麻將程序[14-15]進行對比，將2個使用本文方法的麻將程序和2個使用傳統方法的麻將程序進行了對戰(zhàn)，結果如表3所示。容易看出，使用局面信息利用方法的麻將程序得分大幅領先于使用追求快速聽牌方法的麻將程序，在點炮率和獲勝率上都優(yōu)于追求快速聽牌方法的麻將程序。

表3 局面信息利用方法的影響

4.1.2動態(tài)游戲狀態(tài)劃分方法的影響

為了證明動態(tài)游戲狀態(tài)劃分方法是必要的，本節(jié)將動態(tài)游戲狀態(tài)劃分模塊替換為傳統的靜態(tài)麻將對局前后期劃分方法進行對比試驗。使用統計數據中向聽數為1時的最大動作數分布，即玩家采取第4個動作時為前后期分界，在這里將之稱為靜態(tài)游戲狀態(tài)劃分方法。每場比賽包括2個使用動態(tài)游戲狀態(tài)劃分方法的麻將程序和2個使用靜態(tài)游戲狀態(tài)劃分方法的麻將程序，結果如表4所示。使用動態(tài)游戲狀態(tài)劃分方法后，點炮率大幅下降，其獲勝率和得分也隨之提高。此外，使用靜態(tài)游戲狀態(tài)劃分方法的麻將程序在游戲后期常常會做出不符合游戲規(guī)則的決策，這與其對游戲局面信息的錯誤利用有關，而動態(tài)游戲狀態(tài)劃分方法避免了這一問題。

表4 游戲狀態(tài)劃分方法的影響

4.2 與高水平麻將AI之間的比賽

本節(jié)使用本文方法構建的麻將程序與在2020年中國計算機博弈錦標賽麻將項目中取得冠軍成績的程序[11]進行了比賽，每場比賽包括2個使用本文方法的麻將程序和2個冠軍程序，統計了不同程序的點炮率、獲勝率和最終得分。該冠軍程序針對麻將游戲規(guī)則設計了一種基于棄牌優(yōu)先級表的麻將決策方法，為不同牌型設定了不同的棄牌先后順序。實驗結果如表5所示，得益于本文的局面信息利用方法，使用本文方法的麻將程序點炮率相比冠軍程序降低了11.9%，獲勝率提升了7.6%。這表明使用本文方法構建的麻將AI達到了較高水平。

表5 與高水平麻將AI比賽

5 結論

本文提出了多種方式來充分利用麻將游戲對局信息，并使用動態(tài)游戲狀態(tài)劃分方法劃分游戲前后期，以保證棄牌信息利用方法、對手牌型概率計算方法和對手手牌模擬方法的準確性。實驗結果顯示，本文的方法最大程度利用了麻將游戲中的局面信息。但是這些方法都是根據大眾麻將的游戲規(guī)則而設定的數學模型。為了擺脫人類知識的局限性，今后將嘗試結合深度學習方法，將數學模型與神經網絡模型相結合，使麻將程序的出牌決策更加合理。