彭麗蓉，趙海璐，甘春晏，劉 潔，陳俊宇

(1.重慶理工大學(xué) 人工智能系統(tǒng)研究所，重慶 401135；2.重慶工業(yè)職業(yè)技術(shù)學(xué)院 人工智能與大數(shù)據(jù)學(xué)院，重慶 401120)

計算機博弈，也被稱為機器博弈，一直是人工智能研究中的熱門領(lǐng)域，其覆蓋面非常廣泛，最廣為熟知的是在計算機博弈游戲中的應(yīng)用，特別是棋牌類的游戲，許多研究者們致力于研發(fā)出能夠像人類一樣思考和決策的游戲智能體[1]。麻將是一種很受歡迎的多人游戲，老少皆宜，且種類與玩法十分豐富。在計算機博弈中，根據(jù)博弈中的信息是否能完全公開，分為完美信息博弈和非完美信息博弈2個類型，顯然麻將屬于非完美信息博弈類型。

顧名思義，在完美信息博弈中，對弈信息對對弈各方是完全公開的、透明的，智能體的構(gòu)造或策略的設(shè)計大多可以基于樹搜索和節(jié)點評估的方式，通過構(gòu)建博弈樹，設(shè)計不同的評估函數(shù)或方法來評估博弈樹中每個節(jié)點，即可能的博弈局面，如圍棋、西洋跳棋、五子棋等[2]，由此產(chǎn)生了系列經(jīng)典的、高效的搜索算法，比如極大極小搜索算法[3]、alpha-beta剪枝算法[4]、UCT算法[5]等。

在非完美信息博弈中，不適合于照搬完美信息博弈方法來構(gòu)造博弈智能體[6]。比如，非完美信息博弈游戲麻將博弈中，玩家除能知道已公開的出牌牌張和自己手上牌張外，其余牌張信息是不知道的，也就是不透明的，產(chǎn)生大量未知信息，而且，麻規(guī)則中還存在杠、碰、吃等著法，將打亂出牌順序而產(chǎn)生隨機性，從而增加決策困難。目前，麻將智能體的博弈策略設(shè)計方法主要采用如下2種方法：① 基于規(guī)則和經(jīng)驗[7-8]；② 采用深度強化學(xué)習(xí)算法[9-10]。方法①能夠達到一定的牌力，但缺乏靈活性[11]，并且對設(shè)計者的麻將游戲?qū)崙?zhàn)能力提出要求，否則，將直接影響智能體的博弈水平。方法②能夠構(gòu)造出較高水平的麻將博弈智能體，如微軟2019年設(shè)計的suphx，但是其模型構(gòu)建難度大、訓(xùn)練成本高昂、普適性差，不利于推廣。

綜上，擬提出一種既具有一定靈活性、又具備一定普適性和低訓(xùn)練代價的胡牌距離概念，再基于最短胡牌距離數(shù)量值，融合牌局中的已知牌張信息和麻將博弈的先驗知識，幫助博弈智能體快速胡牌，提升麻將智能體博弈水平。

1 麻將規(guī)則概述

麻將起源于中國，最初為上流階層的游戲，在歷史演變過程中逐漸流傳于民間，其規(guī)則也因而演變成多種多樣。本文以2020年中國計算機博弈錦標賽中大眾麻將項目的規(guī)則為案例，說明麻將規(guī)則數(shù)量化的過程。

概況：麻將有筒、條、萬3種花色，每種花色含數(shù)字1～9共9個牌張，每個牌張共4張，共108張牌。分列如圖1所示的東、南、西、北4位玩家，玩家每次出牌動作的時間限制在3秒內(nèi)。當有一個玩家成功胡牌，則該牌局就結(jié)束。

圖1 麻將博弈示意圖及牌型圖例

報聽：玩家手上的牌張還差一張牌，就可贏牌時的牌局狀態(tài)。按照博弈規(guī)則要求，在報聽后，玩家的博弈之鞥提就進入托管模式，即除胡牌行為外，不能再做任何其他動作，比如換牌、吃牌、碰牌和杠牌等。

出牌行為順序：在打牌中，每方玩家起手牌規(guī)定是13張，但指定的“莊家”將打出第一手牌，就會手持14張，然后按順時針方向依次出牌。除正常的出牌外，還有4種特殊的出牌行為，其優(yōu)先級順序為“胡牌>杠>碰>吃”：

1)吃牌：吃牌是指玩家擁有兩張相鄰或相隔一張的牌，當上家打出相鄰或是中間的這張牌時，可以進行吃牌;

2)碰牌：碰牌是指有一對一樣的牌，當其他任何一位玩家打出相同牌的時候，玩家可碰牌;

3)直杠：杠牌的一種，指玩家擁有刻子(3張一樣的牌)，當其他任何玩家打出該刻子的第4張牌時，進行開杠即為直杠。

4)暗杠：杠牌的一種，當玩家手牌有4張一樣牌張時，進行開杠即為暗杠，與直杠的區(qū)別的在于刻子的第4張牌由玩家自己從牌墻獲得。

5)補杠：玩家碰牌后，再摸到第4張與已碰牌相同的牌，并杠牌，即為補杠。

6)聽牌：玩家的手牌還差一張牌即可胡牌的狀態(tài)，稱為聽牌狀態(tài)。玩家可選擇是否報聽，報聽后可以獲得分數(shù)獎勵，但是不可再換牌，即摸什么牌就打什么牌，但在不影響牌的情況下，有杠可以選擇是否杠。

7)胡牌：玩家手上的14張牌能夠組成特定組合條件的牌型時，即稱為胡牌。此組合條件是不同地區(qū)、不同玩法的麻將，最大的不同所在。

為了胡牌，玩家需要不斷地依據(jù)進張組合、拆分，再組合、再拆分，目標就是能最快地將手中14張牌組成特定牌型，這可以用式⑴量化表示，同時在滿足式⑴或式⑵基礎(chǔ)上，盡可能保證贏得表1所示的最大番值。

表1 牌種及番數(shù)

(4-a)×AAA+a×ABC+DD

(1)

其中0≤a≤4。

b×DD

(2)

其中b=7。

在表1或式⑴或式⑵中，a、b均為整數(shù)；AAA表示同花色的任意相同3張牌，稱為刻子，如圖1中3張四筒；ABC表示同花色的連續(xù)順序的3張牌，稱之為順子，如圖1中3張一、二、三萬；DD表示同花色的任意2張相同牌張，稱之為對子，也稱為將牌，如圖1中2張四條。

從上可見，牌張分分合合的過程，其實就是一個牌局逼近胡牌狀態(tài)的過程，與此同時，盡量追求最快時間和最大番值。進一步分析發(fā)現(xiàn)，通過計算，可以得到108張麻將牌中每一種胡牌類型的牌型數(shù)目，再將牌型數(shù)目值由大到小排列可得“基本胡>碰碰胡>清一色>七對”，簡稱為“x>y>z>q”，這說明表1中番值大小也是玩家胡牌獲勝概率的大小寫照，番值越大，獲勝概率也越小，難度越大，反之亦然。

此外，筆者注意到不同地區(qū)的麻將博弈規(guī)則差異較大。比如，大眾麻將規(guī)則與成都地區(qū)的“血戰(zhàn)到底”麻將規(guī)則比較，至少存在2點巨大差異：一是胡牌花色種類不同，“血戰(zhàn)麻將”任何胡牌類型，花色限制不超過2種，即必須打缺；而大眾麻將從表可見，除表1中z類外，其他3種x、y、q胡牌類型，沒有花色種類限制；二是游戲結(jié)束方式不同，大眾麻將只要有某個玩家胡牌，就宣告游戲結(jié)束，而“血戰(zhàn)麻將”即使某個玩家胡牌，也不意味著游戲結(jié)束，而是剩余玩家需要繼續(xù)對弈，直到局面中僅有一名玩家沒有胡牌或堂子中牌張清零，游戲才宣告結(jié)束，這也就是“血戰(zhàn)到底”的含義。顯然，“血戰(zhàn)麻將”的博弈智能體構(gòu)建難度更大，因為不斷的胡牌玩家將會同時隱藏許多牌張信息，讓后續(xù)玩家難以準確判斷局面中剩余牌張，這將極大影響后續(xù)玩家的計算、判斷和決策，增加博弈難度。

2 胡牌方法

2.1 胡牌距離概念

所謂的胡牌距離d，就是玩家當前手牌與胡牌狀態(tài)度量值，即玩家當前手牌到最近胡牌類型所需牌張的數(shù)量，本質(zhì)就是缺牌數(shù)量。如圖2牌例中，盡管存在滿足式⑴的3個順子或刻子，還有2個對子，此時，玩家就面臨拆4張“二條”為1個刻子，尋求1個條、筒花色的新對子，還是保留2張“二條”為將牌，再尋求3張條或筒花色的1個順子或刻子，此時前1種情況距離胡牌還差2張牌、后1種情況距離胡牌還差3張牌，這樣2種選擇的胡牌距離d就分別是2和3。從胡牌距離大小來講，選擇d=2這條胡牌路線更好，這也是引入胡牌距離的本意，就是利用可量化的概念，告訴麻將博弈智能體胡牌路線的選擇方向。當然，理論上講，胡牌距離d是介于[0，12]區(qū)間的整數(shù)值，當d=0時，玩家起手就胡牌，這稱為天牌，當d=13時，就是手上13張牌全是散亂，沒有任何順子、刻子、對子，理論上需要的胡牌14張牌，需要更換全部手上的13張牌，這稱為爛牌。

圖2 麻將游戲玩家手牌實例圖

此外，麻將博弈常采用拆分方法、尋找其中隱藏的不同胡牌路線，而面對諸多胡牌路線，胡牌距離d就可以是其選擇的依據(jù)。但是，d值的應(yīng)用又不能太僵化，這是因為在逼近胡牌的過程中，玩家按照表1需要，不斷對手上的牌進行順、刻、對組合或拆分并同時考慮花色的搭配，這個過程中會產(chǎn)生一些新的牌張組合，如二連牌、搭子，如圖3所示。這些新組合是逼近順、刻、對的最佳牌檔，以它們?yōu)榛A(chǔ)可以建立滿足式⑶的集合Q，稱之為缺牌集：

圖3 麻將博弈牌張組合圖例

d=min{|Qi| |i∈[1，n]}

⑶

可以把二連牌、搭子等組合，理解為獲得順、刻、對組合的最佳中間牌張搭檔。

2.2 手牌信息集

盡管胡牌距離d的大小可以是麻將博弈智能體的胡牌路線的選擇依據(jù)，左右胡牌路線的方向選擇，但是，博弈進程中，隨著麻將游戲開始，東南西北4個玩家首先逐次摸牌獲得起手13張牌，其中莊家多一張最先出牌張，為14張，然后是依照麻將規(guī)則摸牌、打牌，從而圖1堂子中的牌張將會越來越多、玩家手上牌張通常至少有13張，除非有“杠”組合牌張存在或胡牌，牌張數(shù)會大于13。因此，玩家能看見的牌張信息就是堂子中的明牌、自己手上的牌和其他玩家各類吃牌、碰牌動作后的明牌，其余牌張信息是不清楚的，這些就是隱藏牌張。此時，如果單純依據(jù)距離d大小，而不考慮隱藏牌張信息，就可能造成永遠都不能胡牌，因為需要的胡牌張可能在其他玩家手中，而且是他們固定下來的組合，無論是有意還是無意，都不會打出來。比如，某玩家東僅僅只差將牌，手上有1張“二條”，此時d=1，但是在另外玩家西手中“二條”是1個刻子，此時玩家西不會將“二條”打出，而且還希望杠“二條”以加番，如果玩家東不能洞察而等“二條”，顯然東家永遠不能胡牌，此時最小的d值反而成為累贅。

除此之外，有時候不同的胡牌路線會擁有相同的胡牌距離。比如某玩家當前手牌為23345B(條)，所有可能的獲勝牌型共有9種，玩家在逼近胡牌的過程中，對手牌不斷進行拆分，根據(jù)不同的獲勝牌型，玩家需要等待和需要丟棄的牌張是不同的，具體情況如圖4、5所示。

圖4 對3為將牌的獲勝牌型

圖4、5中帶有下劃線的數(shù)字表示玩家若想要以這種牌型獲勝所需要的牌張，對應(yīng)下方則為不需要的牌張。也就是說，玩家若想要以33234B的牌型獲勝，就必須從當前的手牌中丟棄5B(條)，等待3B(條)；想要以33345B的牌型獲勝，就必須丟棄2B(條)，等待3B。這樣的情況總共有9種。同時，由式(3)可得，圖中①②③④的獲勝路線d=2，而其余5種獲勝牌型d=1，顯然①②③④的獲勝路線并不是玩家的最佳選擇。如果僅僅根據(jù)d的值來確定玩家的胡牌路線，那么玩家當前有5種胡牌路線可以選擇，這5種胡牌路線所需的牌張信息，就構(gòu)成了信息集I，其中需要的牌張組成缺牌集合Q，不需要的牌張組成棄牌集合D。I與Q、D的關(guān)系如式(4)所示。

Ii={Qi:Di|i∈[1，n]}

(4)

若按照圖4的拆牌方式，Q1={3B，6B}，對應(yīng)D1={2B，5B}；若按照圖5拆牌方式，Q2={2B，5B}，對應(yīng)D2={3B}，就這樣，不同拆牌方式得到的Q和D，共同構(gòu)建了當前手牌的信息集I。

圖5 其他牌作為將牌的獲勝牌型

本質(zhì)上，信息集I中存儲的信息，就是玩家當前手牌下，所有可能執(zhí)行的最優(yōu)動作策略的合集。當然，依據(jù)胡牌距離d構(gòu)建的信息集I，只是玩家在僅考慮自身手牌下的理想可執(zhí)行動作，行牌過程中諸多的隱藏信息，必定會影響玩家最終動作決策。因此，胡牌距離d必須與手牌信息、缺牌信息進行融合決策，才能實現(xiàn)博弈智能體的胡牌目標。

2.3 行為決策

根據(jù)玩家在當前手牌下計算的胡牌距離以及構(gòu)建的信息集I，本節(jié)的行為決策將介紹在獲得手牌信息集的基礎(chǔ)上，針對相同胡牌距離下玩家如何決定出牌動作及是否進行吃碰杠動作，提出一種融合場上信息，計算期望勝率的方法，指導(dǎo)玩家具體動作的決策。

在麻將游戲中，玩家所有可執(zhí)行的動作包括：吃、碰、杠、出牌、摸牌。在計算機中，摸牌動作不需要AI玩家設(shè)計實現(xiàn)，直接由計算機程序控制發(fā)牌，AI玩家每次自動獲得一張新牌，并按序排列。每當輪到玩家執(zhí)行游戲動作時，首先結(jié)合當前場上信息，構(gòu)建手牌信息集，然后根據(jù)手牌信息集，計算每個可能動作的期望勝率Eaction。式(5)表示其計算公式。

Eaction=α*PDi+β*PQi

(5)

(6)

(7)

式(5)中的α、β分別表示Qi和Di的大小，式(6)中的PDi表示玩家丟棄棄牌集中元素的概率，式(7)中的PQi表示玩家得到缺牌集中元素的概率。在圖4中，Qi和Di的大小均為2，因此α=β=2，同理，在圖5中可得α=2,β=1。通過式(5)(6)(7)，可以計算出每個可能執(zhí)行動作的期望勝率。

基于游戲規(guī)則可知，玩家的動作分為兩類：出牌動作和其他動作，而其他動作是指吃、碰、杠。本質(zhì)上，可以將玩家吃和碰的動作決策與玩家出牌動作的決策歸為一類。吃、碰的動作與出牌動作有著共同點，其都需得到一張牌，再丟出一張牌，區(qū)別在于出牌動作是系統(tǒng)自動為AI玩家隨機獲得一張牌，然后AI玩家再丟棄一張牌，而吃、碰是“獲得”其余玩家丟棄的一張牌，相當于摸進一張已知牌，然后再進行出牌動作，因此，可將吃、碰動作與出牌動作歸為一類，看作統(tǒng)一決策情形進行處理[12]。

行為決策總體邏輯是：輪到玩家出牌時，系統(tǒng)已自動替玩家執(zhí)行“摸牌”動作，因此程序輸入牌的張數(shù)只可能是2、5、8、11、14張，然后進行出牌動作決策；當其他玩家動作時，AI玩家不斷收集場上已知信息，并關(guān)注其他玩家丟棄的牌，判斷是否進行吃、碰。AI玩家整體執(zhí)行的邏輯流程如圖6所示。

圖6中，hand表示玩家當前手牌，state表示玩家當前狀態(tài)，state=0，表示玩家當前狀態(tài)是出牌狀態(tài)，若不為零，則表示玩家為非出牌狀態(tài)，即吃或碰的狀態(tài)。hand′表示玩家處于非出牌狀態(tài)下的手牌。T表示一張牌，初始值為空。d和I分別為根據(jù)玩家當前手牌計算的胡牌距離及構(gòu)建的信息集，t表示最終計算得到的玩家可以丟棄的牌，Action表示玩家最終的動作。

圖6 整體流程框圖

當玩家為出牌狀態(tài)，hand的值為玩家當前手牌，T的值為空，首先計算d，并構(gòu)建I，然后計算每個可執(zhí)行動作(即每張可以丟棄的牌)的期望勝率，最后選擇出期望勝率最高的動作(即最終丟棄的牌t)，判斷t的值是否與T的值相等，若不相等，則執(zhí)行該動作。由于在出牌狀態(tài)下，T的值始終為空，因此T和t永遠都不會相等，Action=t，表示丟棄的牌為t。

當玩家為非出牌狀態(tài)，即說明此時需要執(zhí)行的動作是判斷玩家是否進行吃或碰。程序中先假設(shè)已經(jīng)進行吃或碰，將T的值賦為可吃或可碰的那張牌的值，并更新hand，處理邏輯與玩家處于出牌狀態(tài)時一致，只是T的值不再為空。最后當T與t相等時，Action的值為pass，表示玩家不執(zhí)行吃或碰的動作；T與t不等時，表示玩家執(zhí)行吃或碰的動作，并丟棄t。

3 實驗結(jié)果與分析

根據(jù)游戲規(guī)則，在有限的游戲局數(shù)中，游戲的獲勝是由玩家最終累計獲得的分數(shù)多少決定，而每局游戲，只要有一個玩家胡牌，則本局游戲結(jié)束，因此，采用維持最少缺牌數(shù)的胡牌方法，來實現(xiàn)快速胡牌，通過在胡牌次數(shù)上的優(yōu)勢，來獲得最終的游戲勝利。為了驗證本文方法的有效性，設(shè)計了與基于專家經(jīng)驗出牌程序MJ1和普通人類玩家MJ2的對照實驗。使用平臺為競技世界(成都)網(wǎng)絡(luò)技術(shù)有限公司研發(fā)的麻將博弈對戰(zhàn)平臺，該平臺中有隨機發(fā)牌的AI及判胡處理程序。實驗程序只需按照接口文檔，返回規(guī)定的數(shù)據(jù)，即可將多個不同類型的實驗程序接入該平臺，進行麻將對戰(zhàn)。對手設(shè)置如表2所示。

表2 實驗對手設(shè)置

基于胡牌距離設(shè)置的程序MJ-D，分別與上述對手進行1 000局的對弈，根據(jù)最終累計的胡牌總得分來判定勝負關(guān)系。實驗設(shè)計一個MJ-D分別和3個MJ1、MJ2對局，這樣可以保證3個對手的游戲水平是一致的，能盡可能避免位置不同帶來的影響。表3和表4分別為和MJ1、MJ2的對局結(jié)果。

表3 對局結(jié)果

表4 對局結(jié)果

表1中MJ1基于專家經(jīng)驗設(shè)置而成，具備一定的對戰(zhàn)能力，牌力在普通玩家之上，而表2中MJ2的牌力，更接近普通人類水平。根據(jù)表3和表4的對局結(jié)果可得，MJ-D在1 000局對弈中，雖然每局的平均得分并不是最高的，但是總的胡牌次數(shù)最多，最終的總得分也是最高的。由此，基于胡牌距離的胡牌方法舍棄高分牌型，以快速胡牌為目的，能夠在胡牌次數(shù)的優(yōu)勢上贏得更多的分數(shù)，從而獲取最終游戲勝利。

4 結(jié)論

提出了麻將博弈胡牌方法，基于胡牌距離構(gòu)建手牌信息集，融合場上信息，通過維持最少缺牌數(shù)，計算相同胡牌距離局面下的期望獲勝概率，更好地決定玩家動作，實現(xiàn)快速胡牌，從而在有限的游戲局數(shù)中，取得較多次數(shù)的游戲勝利。實驗顯示，基于胡牌距離的胡牌方法能夠更為準確的決定玩家動作，雖然每局的平均得分不是最高的，但是在多局游戲中的獲勝次數(shù)，明顯高于基于經(jīng)驗的方法，最終的累積得分也是最高的。本文方法存在的不足是：① 在游戲中，需要收集場上所有已知牌的信息，并據(jù)此計算該局面期望勝率，而前期場上已知信息較少，胡牌距離較大時，信息集的構(gòu)建會存在不可避免的偏差，導(dǎo)致游戲前期動作決策失誤；② 舍棄了高分牌型，喪失了一部分獲得高分的機會。后續(xù)將對游戲前期已知牌信息較少時，信息集的構(gòu)建進行進一步研究，以減少前期錯誤動作對后續(xù)行為決策的影響，同時，加入高分牌型的處理決策。