結(jié)合先驗(yàn)知識(shí)與蒙特卡羅模擬的麻將博弈研究

王亞杰，喬繼林，梁凱，謝延延

（1.沈陽(yáng)航空航天大學(xué) 工程訓(xùn)練中心, 遼寧 沈陽(yáng) 110136; 2.沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院, 遼寧 沈陽(yáng)110136）

計(jì)算機(jī)博弈是通過(guò)計(jì)算機(jī)給出著法，與人類選手或另一個(gè)計(jì)算機(jī)進(jìn)行的各種游戲?qū)模侨斯ぶ悄茴I(lǐng)域中最具挑戰(zhàn)性的研究方向之一，被稱為人工智能科學(xué)的“果蠅”[1-3]。

近些年來(lái)，DeepMind團(tuán)隊(duì)開(kāi)發(fā)的Alpha系列[4-7]使得人工智能在完備信息博弈中完全超越了人類。而以德州撲克為代表的Pluribus在無(wú)限制德州撲克的比賽中成功戰(zhàn)勝五名專家級(jí)人類玩家，標(biāo)志著人工智能在多人非完備信息博弈領(lǐng)域取得了重大突破[8-11]。

非完備信息博弈中隱藏信息對(duì)于博弈難度的影響較大，信息集數(shù)目和信息集平均大小與博弈復(fù)雜度成正比[12]。其中一對(duì)一德州撲克通過(guò)子博弈策略達(dá)到近似納什均衡求解[13]，而在多人撲克博弈中沒(méi)有合適的策略。麻將隱藏信息的數(shù)量遠(yuǎn)遠(yuǎn)超過(guò)德州撲克，所以麻將博弈研究比德州撲克更加復(fù)雜。

麻將除了豐富的隱藏信息，復(fù)雜的計(jì)分規(guī)則和出牌規(guī)則，還需要考慮多種決策類型。任意一位玩家的吃、碰、杠動(dòng)作都會(huì)改變后續(xù)玩家的摸牌順序，因此我們很難為麻將構(gòu)建一棵規(guī)則的博弈樹(shù)。一些在圍棋和德州撲克中表現(xiàn)很好的算法，如蒙特卡羅樹(shù)搜索、蒙特卡羅反事實(shí)遺憾最小化等都無(wú)法直接應(yīng)用于麻將博弈，導(dǎo)致麻將博弈中沒(méi)有經(jīng)典博弈算法可以對(duì)比，需要自行設(shè)計(jì)對(duì)比算法。

本文的研究以勝利局?jǐn)?shù)和點(diǎn)炮次數(shù)作為算法效果的評(píng)價(jià)指標(biāo)，不考慮復(fù)雜的計(jì)分規(guī)則。本文主要針對(duì)麻將博弈中的棄牌和聽(tīng)牌模塊進(jìn)行了設(shè)計(jì)，通過(guò)對(duì)比實(shí)驗(yàn)驗(yàn)證了所提出策略和算法的有效性。貢獻(xiàn)及創(chuàng)新點(diǎn)總結(jié)如下：

1) 設(shè)計(jì)了基礎(chǔ)版算法Fanfou_ba，以最快聽(tīng)牌、胡牌為目標(biāo)，應(yīng)用先驗(yàn)知識(shí)，針對(duì)棄牌模塊細(xì)粒度地設(shè)計(jì)了棄牌的優(yōu)先層級(jí)，并對(duì)吃牌模塊作了簡(jiǎn)單的限制處理。Fanfou_ba在第十四屆中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽麻將項(xiàng)目中獲得冠軍，取得了較好的效果。本文將Fanfou_ba作為基準(zhǔn)算法與提出的其它算法進(jìn)行對(duì)比。

2)在Fanfou_ba基礎(chǔ)上設(shè)計(jì)了優(yōu)化版算法Fanfou_op。首先，針對(duì)聽(tīng)牌模塊提出了“聽(tīng)牌有效數(shù)”的設(shè)計(jì)方法；其次，完成了吃牌模塊的優(yōu)先級(jí)設(shè)計(jì)；最后，實(shí)現(xiàn)了補(bǔ)杠、特殊牌型（如七對(duì)和碰碰胡和連牌牌型）的棄牌選擇處理。經(jīng)第一組12 000局對(duì)比實(shí)驗(yàn)，F(xiàn)anfou_op領(lǐng)先Fanfou_ba 1 171局，相比Fanfou_ba勝率提高了9.76%。

3)針對(duì)麻將多智能體博弈場(chǎng)景和麻將點(diǎn)炮讓己方收益最小化的問(wèn)題，不再局限于己方AI的設(shè)計(jì)，也為降低其他選手的胡牌概率采取措施，在Fanfou_op基礎(chǔ)上設(shè)計(jì)了提升版算法Fanfou_mc，應(yīng)用蒙特卡羅方法模擬聽(tīng)牌選手手牌。經(jīng)第二組和第三組共計(jì)32 000局對(duì)比實(shí)驗(yàn)，F(xiàn)anfou_mc在勝率分別提升0.2%和0.13%的基礎(chǔ)上，點(diǎn)炮率分別降低了0.4%和0.47%，驗(yàn)證了使用蒙特卡羅方法模擬聽(tīng)牌選手手牌對(duì)避免點(diǎn)炮的有效性。

1 相關(guān)工作

麻將的胡牌規(guī)則基本一致，但由于地區(qū)文化差異，玩法稍有不同。例如，具體番數(shù)計(jì)算、牌的種類和數(shù)目。本文研究的麻將沿用2020年“競(jìng)技世界杯”中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽暨第十四屆中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽麻將項(xiàng)目規(guī)則[14]，牌庫(kù)只有序數(shù)牌，不考慮其他牌型種類。圖1顯示了27種序數(shù)牌，每種序數(shù)牌有4張，共108張牌。

圖1 麻將序數(shù)牌Fig.1 Mahjong ordinal tile

目前關(guān)于麻將博弈的研究并不多，Cheng等[15]在2017年首次使用數(shù)學(xué)技術(shù)，通過(guò)基本組合理論研究麻將中一組特殊的牌型k-gate。例如：清一色的13張牌型T稱為nine-gate (九門(mén))，如圖2所示，可以向T中添加任意一張筒類牌實(shí)現(xiàn)胡牌。

圖2 nine-gate（九門(mén)）牌型TFig.2 nine-gate card type

來(lái)自悉尼科技大學(xué)和陜西師范大學(xué)的Li等[16]在2019年的論文中定義了“缺牌數(shù)”的概念，缺牌數(shù)代表當(dāng)前牌面的好壞，缺牌數(shù)為0時(shí)代表胡牌。同時(shí)提出最優(yōu)策略，在k次牌面變換（k≥ 1）的條件下增加胡牌的概率，確定當(dāng)前該打的牌。上述兩篇論文的研究都是基于起手牌為13張的麻將，并且只考慮了萬(wàn)條筒3種序數(shù)牌型。

關(guān)于麻將博弈算法的研究可以分為經(jīng)驗(yàn)知識(shí)和深度學(xué)習(xí)兩個(gè)視角。前者的研究主要集中在臺(tái)灣麻將，以先驗(yàn)知識(shí)設(shè)計(jì)為研究重點(diǎn)，并結(jié)合一些經(jīng)典算法[17-19]；而后者主要被應(yīng)用于日本麻將，通過(guò)大量的專家牌譜數(shù)據(jù)進(jìn)行神經(jīng)網(wǎng)絡(luò)訓(xùn)練，其中最顯著的成果是微軟亞洲研究院研發(fā)的AI Suphx[20-24]，內(nèi)陸麻將博弈的研究總體上還處于起步階段[25-27]。

2 基于知識(shí)和手牌模擬的麻將AI

本文麻將博弈主要內(nèi)容框架如圖3所示，設(shè)計(jì)了3種麻將AI算法：基礎(chǔ)版算法Fanfou_ba、優(yōu)化版算法Fanfou_op和提升版算法Fanfou_mc。其中，F(xiàn)anfou_ba考慮了棄牌模塊的優(yōu)先級(jí)設(shè)計(jì)和吃牌模塊的限制處理；Fanfou_op針對(duì)聽(tīng)牌和吃牌模塊提出了聽(tīng)牌有效數(shù)和吃牌模塊的優(yōu)先級(jí)；Fanfou_mc考慮到多智能體博弈場(chǎng)景和麻將點(diǎn)炮的特點(diǎn)，應(yīng)用蒙特卡羅方法對(duì)聽(tīng)牌對(duì)手手牌進(jìn)行了模擬。3種麻將AI算法的博弈水平呈現(xiàn)漸進(jìn)式提升，下面分別對(duì)3種算法進(jìn)行介紹。

圖3 主要內(nèi)容框架Fig.3 Main content framework

2.1 棄牌優(yōu)先級(jí)和吃牌限制

麻將中聽(tīng)牌是指缺少一張牌便能胡牌的狀態(tài)，如圖2的牌型，缺少任意一張筒字牌；胡牌是指形成特定的牌型(四個(gè)組合和一個(gè)對(duì)子，組合指順子或刻子)，分為自摸胡牌和點(diǎn)炮胡牌，自摸和炮胡的區(qū)別在于缺少的一張牌是由自己摸到還是對(duì)手打出。胡牌用式(1)表示：

式中：ABC代表順子；AAA代表刻子；AA代表對(duì)子；x(.)和y(.)代表對(duì)應(yīng)牌型的數(shù)目。本文研究的麻將起手牌是13張，此時(shí)x+y=4，而在起手牌16張的麻將博弈中，x+y=5。

Fanfou_ba要實(shí)現(xiàn)盡快聽(tīng)牌、胡牌的目標(biāo)，每次棄牌處理時(shí)都要打出當(dāng)前手牌中最不需要的牌，Li等[15]在論文中定義的缺牌數(shù)也說(shuō)明了棄牌模塊的重要性[16]。

Fanfou_ba針對(duì)棄牌模塊總體設(shè)計(jì)了4個(gè)優(yōu)先級(jí)，詳見(jiàn)表1。假設(shè)摸到1張牌后的手牌如圖4所示，分別對(duì)應(yīng)4種類型的單牌：兩邊都不搭的單牌有1條和7萬(wàn)(沒(méi)有2條、3條和5萬(wàn)、6萬(wàn)、8萬(wàn)、9萬(wàn))；只搭一邊的單牌有5條、7條和9條(沒(méi)有4條、6條和8條)；對(duì)子間隔搭的單牌有1萬(wàn)和4萬(wàn)(都沒(méi)有3萬(wàn))；對(duì)子旁邊搭的單牌有4萬(wàn)(沒(méi)有2萬(wàn)和5萬(wàn))。

表1 棄牌優(yōu)先層級(jí)Table 1 Priority level of discard

圖4 摸到1張牌后的手牌樣例（14張）Fig.4 Sample hand after drawing 1 card(14 tiles)

表1中具體牌型是通過(guò)大量測(cè)試總結(jié)出來(lái)的，層序代表了同等優(yōu)先級(jí)下單牌牌型棄牌的先后順序。因?yàn)?和9的序數(shù)牌可搭的牌有2種（分別是2、3和7、8對(duì)應(yīng)的序數(shù)牌），2和8的序數(shù)牌可搭的牌有 3種，3、4、5、6、7的序數(shù)牌可搭的牌有4種，所以順序分為：1和9對(duì)應(yīng)的序數(shù)牌（1 條/萬(wàn)/筒和 9 條/萬(wàn)/筒）；2 和 8 對(duì)應(yīng)的序數(shù)牌；3、4、5、6、7對(duì)應(yīng)的序數(shù)牌。數(shù)字下面的下劃線代表這張牌不是0張，可能多張或1張，數(shù)字下面雙劃線代表這張牌不是1張，可能多張或0張，數(shù)字下面虛線代表這張牌數(shù)量不為2，可能0、1、3、4張。算法1描述了基于棄牌優(yōu)先級(jí)的決策過(guò)程。

算法1基于棄牌優(yōu)先級(jí)的決策過(guò)程

輸入手牌，已經(jīng)打過(guò)的牌HISTORY；

輸出最佳棄牌選擇。

1) 手牌遍歷23種層級(jí)牌型，更新4個(gè)等級(jí)棄牌列表Di

2) FOR ALL EACHDii{1,2,3,4} DO

3) FORjIN len(Di) DO

4) IF HISTORY[Di[j]]>0:

5) RETURNDi[j]

6) END IF

7) END FOR

8) END FOR

表1中的數(shù)字代表序數(shù)牌中對(duì)應(yīng)的牌，0表示沒(méi)有對(duì)應(yīng)的序數(shù)牌，冒號(hào)后面的具體牌型代表?xiàng)壟茣r(shí)手牌需滿足的條件，若滿足條件則將對(duì)應(yīng)的牌加入當(dāng)前等級(jí)的棄牌列表。

因?yàn)楸荣愐?guī)則中規(guī)定吃牌獲得分?jǐn)?shù)低于碰牌和杠牌獲得的分?jǐn)?shù)，所以針對(duì)一些不合理的吃牌動(dòng)作策略進(jìn)行了優(yōu)化處理。例如：限制了拆除手牌中刻子(3張一樣的牌)或兩個(gè)對(duì)子進(jìn)行吃牌的動(dòng)作策略，因?yàn)檫@樣的吃牌處理可能會(huì)丟失碰牌或杠牌獲得更高分?jǐn)?shù)的機(jī)會(huì)。

2.2 聽(tīng)牌有效數(shù)和吃牌優(yōu)先級(jí)

麻將規(guī)則中明確規(guī)定，AI一旦聽(tīng)牌后不能再更改手牌，只能打出摸到的牌或者做杠牌和胡牌處理。本節(jié)針對(duì)Fanfou_ba在設(shè)計(jì)時(shí)沒(méi)有考慮到死聽(tīng)(聽(tīng)牌有效數(shù)為0)的問(wèn)題，提出了應(yīng)用聽(tīng)牌有效數(shù)的算法Fanfou_op。聽(tīng)牌有效數(shù)是聽(tīng)牌后所胡牌(胡張)的有效數(shù)量，也就是指牌庫(kù)(未知牌)中剩余胡張的個(gè)數(shù)，不包含手牌和已經(jīng)打出去的牌(已知牌)中的胡張，并將其應(yīng)用在棄牌處理之前的判聽(tīng)模塊。

首先，F(xiàn)anfou_op獲得一張牌后，輪流打出手牌中每一張牌，判斷手牌是否達(dá)到聽(tīng)牌狀態(tài)；其次，統(tǒng)計(jì)聽(tīng)牌有效數(shù)；再次，選擇棄牌后聽(tīng)牌有效數(shù)最大的手牌打出；最后，鑒于聽(tīng)牌有效數(shù)與胡牌概率成正比，因此Fanfou_op在聽(tīng)牌有效數(shù)小于2時(shí)選擇放棄聽(tīng)牌。假設(shè)聽(tīng)牌后能胡的牌有h種(0 ≤h≤9)，已經(jīng)打出去的牌中含有的胡張數(shù)有d張，手牌中含有的胡張數(shù)有m張，此時(shí)聽(tīng)牌有效數(shù)t_num的計(jì)算方法如公式(2)。

算法2描述了基于聽(tīng)牌有效數(shù)的決策過(guò)程。Fanfou_op在每一次棄牌前都會(huì)調(diào)用判聽(tīng)方法，在能夠聽(tīng)牌的條件下，計(jì)算所有胡牌張數(shù)h以及聽(tīng)牌有效數(shù)t_num，當(dāng)t_num ≥2時(shí)選擇對(duì)應(yīng)的手牌打出，然后聽(tīng)牌；否則放棄聽(tīng)牌，按照棄牌優(yōu)先級(jí)進(jìn)行棄牌處理。

算法2基于聽(tīng)牌有效數(shù)的決策過(guò)程

輸入手牌HAND；

輸出最佳棄牌選擇（聽(tīng)牌有效數(shù)最大的棄牌）。

1) FORiIN len(HAND) DO

2) TEMP_HAND = 復(fù)制(HAND)

3) TEMP_HAND.remove(HAND[i])

4)調(diào)用判聽(tīng)返回能否聽(tīng)牌和聽(tīng)牌結(jié)果得到CAN_TING和RESULT

5) IF CAN_TING THEN

6) 計(jì)算HAND[i]棄牌后的TING_NUM

7) END IF

8) END FOR

9) IF max(TING_LIST) > 1 THEN

10)返回 max(TING_LIST)對(duì)應(yīng)的手牌HAND[i]

11) END IF

假設(shè)摸到一張牌后的手牌如圖5所示，已打出去的胡張有x個(gè)。打出手牌中1萬(wàn)后，將有3萬(wàn)和6萬(wàn)兩種胡張，手牌中3萬(wàn)和6萬(wàn)各有1個(gè)，則此時(shí)的聽(tīng)牌有效數(shù)為 2 ×4?2?x；打出手牌中3萬(wàn)或6萬(wàn)后，將有1萬(wàn)一種胡張，手牌中1萬(wàn)有一個(gè)，則此時(shí)的聽(tīng)牌有效數(shù)為1 ×4?1?x；選擇打出牌后聽(tīng)牌有效數(shù)最大的手牌做棄牌處理。

圖5 摸到1張牌后的手牌樣例（5張）Fig.5 Sample hand after drawing 1 card(5 tiles)

Fanfou_ba針對(duì)吃牌模塊僅做了兩種特殊牌型的限制處理，并不足以應(yīng)對(duì)復(fù)雜的情況。例如：上家打出5萬(wàn)，F(xiàn)anfou_ba的手牌中有兩張3萬(wàn)、一張4萬(wàn)和一張6萬(wàn)，F(xiàn)anfou_ba會(huì)選擇3萬(wàn)和4萬(wàn)進(jìn)行吃牌，但理想的動(dòng)作策略應(yīng)該是保留3萬(wàn)的對(duì)子而選擇4萬(wàn)和6萬(wàn)進(jìn)行吃牌。

為解決上述問(wèn)題，F(xiàn)anfou_op提出了將吃牌處理模塊劃分為3個(gè)優(yōu)先級(jí)的方法，詳見(jiàn)表2。吃牌處理時(shí)，首先，考慮兩個(gè)單牌的牌型；其次，考慮一個(gè)對(duì)子和一張單牌的牌型；最后，考慮兩個(gè)對(duì)子的牌型，其中兩個(gè)對(duì)子吃牌的情況可以細(xì)分為3種特定條件。

表2 吃牌優(yōu)先級(jí)Table 2 Priority of chow

2.3 聽(tīng)牌對(duì)手的手牌模擬

麻將屬于多人非完備信息博弈，F(xiàn)anfou_ba和Fanfou_op均屬于單智能體的范疇，僅考慮己方AI的設(shè)計(jì)而沒(méi)有考慮到對(duì)手的手牌，忽略了多人博弈的特點(diǎn)，導(dǎo)致點(diǎn)炮概率較大，未能實(shí)現(xiàn)己方收益最大化。

文獻(xiàn)[16]通過(guò)使用蒙特卡羅方法模擬整個(gè)牌局來(lái)降低點(diǎn)炮概率：首先，隨機(jī)生成3個(gè)玩家的缺牌數(shù)；其次，檢查缺牌數(shù)是否合理；最后，模擬選手手牌。但是這樣模擬會(huì)產(chǎn)生兩個(gè)問(wèn)題：1)缺牌數(shù)的合理判斷需要結(jié)合人類經(jīng)驗(yàn)，具有較大的隨機(jī)性；2)最后隨機(jī)產(chǎn)生的手牌是經(jīng)由牌型的組合劃分（未知牌中順子、刻子、對(duì)子和單牌的組合）產(chǎn)生的，人工劃分的組合考慮不到所有的可能性。

針對(duì)上述問(wèn)題，提出了通過(guò)蒙特卡羅方法模擬聽(tīng)牌選手手牌的算法Fanfou_mc。AI進(jìn)行模擬需要滿足己方?jīng)]有聽(tīng)牌和對(duì)手有聽(tīng)牌兩個(gè)條件，后者避免了考慮結(jié)合經(jīng)驗(yàn)并且有較大隨機(jī)性的缺牌數(shù)問(wèn)題，只需要模擬出的手牌滿足聽(tīng)牌條件；前者保證了AI追求最快聽(tīng)牌胡牌的目標(biāo)不受影響。

通過(guò)模擬聽(tīng)牌選手手牌，計(jì)算棄牌列表中每張牌的點(diǎn)炮次數(shù)。若有3家對(duì)手聽(tīng)牌，則同時(shí)模擬3個(gè)玩家的手牌，選擇優(yōu)先級(jí)高的棄牌列表中點(diǎn)炮次數(shù)最少的牌打出，實(shí)現(xiàn)了通過(guò)模擬對(duì)手手牌降低點(diǎn)炮幾率的目標(biāo)。

Fanfou_mc包括兩個(gè)參數(shù)：模擬手牌的種類數(shù)目和模擬聽(tīng)牌玩家手牌的數(shù)目。其中，模擬手牌種類數(shù)目與模擬消耗時(shí)間成正比、與點(diǎn)炮概率成反比，考慮比賽有出牌時(shí)間的限制，經(jīng)反復(fù)實(shí)驗(yàn)后將模擬手牌種類數(shù)目設(shè)置為10，在盡可能降低點(diǎn)炮概率的同時(shí)出牌時(shí)間不超過(guò)比賽時(shí)間的限制，F(xiàn)anfou_mc的方案流程如圖6所示。

圖6 Fanfou_mc流程Fig.6 Flow of Fanfou_mc

模擬聽(tīng)牌玩家手牌的數(shù)目(sim_num)由聽(tīng)牌玩家的吃、碰、杠數(shù)目決定，設(shè)一聽(tīng)牌玩家吃牌、碰牌、杠牌數(shù)目分別為C、P、K，則模擬手牌數(shù)目計(jì)算方法如式(3)：

Fanfou_mc模擬完所有聽(tīng)牌選手手牌后，選擇棄牌列表中點(diǎn)炮次數(shù)為0的牌做棄牌處理時(shí)，點(diǎn)炮概率最小。若所有牌點(diǎn)炮次數(shù)都為0，則會(huì)按順序選擇棄牌列表中第一張點(diǎn)炮次數(shù)為0的牌打出；若棄牌列表中沒(méi)有點(diǎn)炮次數(shù)為0的牌，則會(huì)選擇點(diǎn)炮次數(shù)最少的牌打出。算法3描述了通過(guò)模擬聽(tīng)牌對(duì)手手牌降低點(diǎn)炮概率的決策過(guò)程。

算法3基于對(duì)手手牌模擬的棄牌決策過(guò)程

輸入手牌HAND，已經(jīng)打過(guò)的牌HISTORY；

輸出最佳棄牌選擇。

1) 剩余未知牌 CARD = 所有牌 ? HAND ?HISTORY

2) FOR ALL EACH OPPONENTi{上家，對(duì)家，下家} DO

3) IF OPPONENTi聽(tīng)牌THEN

4) 計(jì)算OPPONENTi的手牌數(shù)目sim_num

5) WHILE (TRUE) DO

6) SIM_LIST = CARD中隨機(jī)模擬sim_num個(gè)牌

7) IF SIM_LIST能夠聽(tīng)牌 THEN

8)j++ // 模擬的聽(tīng)牌手牌數(shù)目

9) END IF

10) IFj= = 10 THEN // 模擬10種聽(tīng)牌手牌

11) BREAK

12) END IF

13) END WHILE

14) END IF

15) END FOR

16) 將棄牌列表中每張牌依次加入到模擬聽(tīng)牌選手的手牌

17) 統(tǒng)計(jì)棄牌列表中每張牌的點(diǎn)炮次數(shù)

18) 生成棄牌列表對(duì)應(yīng)的點(diǎn)炮次數(shù)列表FIRE_LIST

19) IF min (FIRE_LIST) > 1 THEN

20) 選擇FIRE_LIST中第一個(gè)min (FIRE_LIST)打出

21) END IF

22) RETURN min (FIRE_LIST)對(duì)應(yīng)的牌

3 實(shí)驗(yàn)設(shè)計(jì)與分析

基于棄牌優(yōu)先級(jí)和吃牌限制設(shè)計(jì)的Fanfou_ba參加了2020“競(jìng)技世界杯”中國(guó)大學(xué)生計(jì)算機(jī)博弈大賽暨第十四屆中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽麻將項(xiàng)目比賽，經(jīng)過(guò)三輪初賽每輪50局，三輪決賽每輪100局比賽，獲得了冠軍，決賽最終成績(jī)?nèi)绫?所示，本文將此AI作為基準(zhǔn)程序。

表3 中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽首屆麻將項(xiàng)目決賽成績(jī)Table 3 Final result of the first Mahjong event of China Computer Game Championship

3.1 實(shí)驗(yàn)方案

實(shí)驗(yàn)環(huán)境是Pycharm2019，使用Python3.7實(shí)現(xiàn)本文方法，在一臺(tái)Inter (R) Core (TM) i5-4210U 1.7 GHz，內(nèi)存為4 GB，顯卡為NVIDIA GeForce 820M的Window 10操作系統(tǒng)上進(jìn)行實(shí)驗(yàn)。經(jīng)測(cè)試模擬10種聽(tīng)牌手牌的平均模擬次數(shù)為6 000次，平均消耗時(shí)間1.5 s，符合比賽出牌時(shí)間限制3 s的要求。

麻將屬于多智能體博弈項(xiàng)目，為能夠完整進(jìn)行實(shí)驗(yàn)并增加麻將博弈中的不確定性，引入了隨機(jī)出牌算法Robot，即棄牌處理時(shí)隨機(jī)打出手牌。由于麻將博弈中吃、碰、杠的動(dòng)作策略會(huì)打亂出牌順序和加快博弈進(jìn)程，所以Robot吃、碰、杠的動(dòng)作決策完全沿用Fanfou_op的設(shè)計(jì)，更加符合真實(shí)比賽和線下博弈的場(chǎng)景。本文實(shí)驗(yàn)的博弈平臺(tái)框架設(shè)計(jì)流程如圖7所示，具體設(shè)計(jì)可參考[14]中名為“完整實(shí)驗(yàn)2.1”的文件。

圖7 對(duì)比實(shí)驗(yàn)流程Fig.7 Flow of comparative experiment

本文以勝利場(chǎng)數(shù)和點(diǎn)炮次數(shù)作為評(píng)價(jià)指標(biāo)，進(jìn)行了3組對(duì)比實(shí)驗(yàn)。其中，第一組對(duì)比實(shí)驗(yàn)中Robot1、Robot2、Fanfou_ba和 Fanfou_op進(jìn)行比賽，驗(yàn)證Fanfou_op中的改進(jìn)策略的有效性；第2組對(duì)比實(shí)驗(yàn)中Robot1、Robot2、Fanfou_op和Fanfou_mc進(jìn)行比賽；第3組對(duì)比實(shí)驗(yàn)中Fanfou_op、Fanfou_op、Fanfou_mc和Fanfou_mc進(jìn)行比賽。后兩組實(shí)驗(yàn)是為了充分驗(yàn)證Fanfou_mc中通過(guò)蒙特卡羅方法模擬聽(tīng)牌對(duì)手手牌避免點(diǎn)炮的效果，第2組引入Robot是為增加比賽中的不確定性，對(duì)應(yīng)多智能體博弈中有牌力較弱選手參與的場(chǎng)景，第3組對(duì)應(yīng)多智能體都是牌力較強(qiáng)選手博弈的場(chǎng)景。

麻將規(guī)則表明，吃牌只能吃上家的牌，因此對(duì)比實(shí)驗(yàn)中需要考慮AI之間的順序。經(jīng)式(4)計(jì)算可知前兩組對(duì)比實(shí)驗(yàn)順序有12種，為確保實(shí)驗(yàn)的嚴(yán)謹(jǐn)性，每種排列方式要進(jìn)行一輪比賽，每輪比賽有1 000局非流局(一局比賽結(jié)束后有人胡牌)的測(cè)試結(jié)果；第三組對(duì)比實(shí)驗(yàn)順序有4種，安排4輪比賽，每輪比賽有5 000局非流局的測(cè)試結(jié)果。

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)數(shù)據(jù)中位置1、位置2、位置3、位置4分別代表麻將智能體的位置，局?jǐn)?shù)是指在該輪比賽中進(jìn)行的總場(chǎng)數(shù)(包括每輪比賽中產(chǎn)生的流局)，A、B、C、D、E分別代表 Fanfou_ba、Fanfou_op、Robot1、Robot2和Fanfou_mc五個(gè)智能體，炮數(shù)是指在該輪比賽中玩家的點(diǎn)炮總局?jǐn)?shù)。第1組對(duì)比實(shí)驗(yàn)結(jié)果數(shù)據(jù)見(jiàn)表4。

以表4中第一輪比賽數(shù)據(jù)為例，在第1輪比賽中一共進(jìn)行了1 008場(chǎng)比賽，其中Fanfou_ba獲勝472局，F(xiàn)anfou_op獲勝486局，Robot1和Robot2分別獲勝22局和20局。

表4 第1組Fanfou_ba、Fanfou_op和Robot對(duì)比實(shí)驗(yàn)結(jié)果Table 4 First set of Fanfou_ba, Fanfou_op and Robot comparative experiment results

在第1組對(duì)比實(shí)驗(yàn)中，F(xiàn)anfou_ba獲勝5 105局，勝率為42.54%，F(xiàn)anfou_op獲勝6 276局，勝率為52.3%；Fanfou_op相比Fanfou_ba勝率提升9.76%，驗(yàn)證了聽(tīng)牌有效數(shù)和吃牌優(yōu)先級(jí)策略的有效性，勝利場(chǎng)數(shù)比較如圖8所示。

圖8 第1組對(duì)比實(shí)驗(yàn)結(jié)果Fig.8 First set of comparative experiment results

第2組對(duì)比實(shí)驗(yàn)結(jié)果數(shù)據(jù)見(jiàn)表5，以表5中第一輪比賽數(shù)據(jù)為例，在第1輪比賽中一共進(jìn)行了1 010場(chǎng)比賽，一共點(diǎn)炮787局；其中Fanfou_mc獲勝480局，點(diǎn)炮128局，F(xiàn)anfou_op獲勝471局，點(diǎn)炮144局，Robot1獲勝24局，點(diǎn)炮284局，Robot2獲勝25局，點(diǎn)炮231局。

表5 第2組Fanfou_op、Fanfou_mc和Robot對(duì)比實(shí)驗(yàn)結(jié)果Table 5 Second set of Fanfou_op, Fanfou_mc and Robot comparative experiment results

在第2組對(duì)比實(shí)驗(yàn)中，F(xiàn)anfou_op獲勝5 698局，F(xiàn)anfou_mc獲勝6 276局，F(xiàn)anfou_mc的勝率相比Fanfou_op提升了0.2%；Fanfou_op點(diǎn)炮1 547局，F(xiàn)anfou_mc點(diǎn)炮1 509局，F(xiàn)anfou_mc的點(diǎn)炮率相比Fanfou_op降低了0.4%，勝利場(chǎng)數(shù)和點(diǎn)炮局?jǐn)?shù)比較如圖9所示。

圖9 第2組對(duì)比實(shí)驗(yàn)結(jié)果Fig.9 Second set of comparative experiment results

第3組對(duì)比實(shí)驗(yàn)結(jié)果數(shù)據(jù)見(jiàn)表6，經(jīng)計(jì)算可以得出，F(xiàn)anfou_mc的勝率相比Fanfou_op提升了0.13%，點(diǎn)炮率相比Fanfou_op降低了0.47%。后兩組對(duì)比實(shí)驗(yàn)驗(yàn)證了模擬聽(tīng)牌對(duì)手手牌避免點(diǎn)炮策略的有效性，勝利場(chǎng)數(shù)和點(diǎn)炮局?jǐn)?shù)比較如圖10所示。

圖10 第3組對(duì)比實(shí)驗(yàn)結(jié)果Fig.10 Third set of comparative experiment results

表6 第3組Fanfou_op和Fanfou_mc對(duì)比實(shí)驗(yàn)結(jié)果Table 6 Third set of Fanfou_op and Fanfou_mc comparative experiment results

實(shí)驗(yàn)數(shù)據(jù)表明，完善的知識(shí)體系使Fanfou_op能夠較快達(dá)到聽(tīng)牌狀態(tài)，對(duì)麻將AI的博弈水平有顯著的提升。由于Fanfou_mc中蒙特卡羅模擬策略無(wú)法在己方處于聽(tīng)牌狀態(tài)時(shí)使用，所以Fanfou_mc沒(méi)有明顯提高勝率。

4 結(jié)束語(yǔ)

本文以麻將為研究載體，提出了結(jié)合知識(shí)與蒙特卡羅模擬的博弈算法。首先，闡述了冠軍AI智能體Fanfou_ba棄牌優(yōu)先級(jí)和吃牌限制的設(shè)計(jì)思想；其次，以Fanfou_ba為基礎(chǔ)設(shè)計(jì)了Fanfou_op，提出了聽(tīng)牌有效數(shù)和吃牌優(yōu)先級(jí)的方法；再次，在Fanfou_op基礎(chǔ)上設(shè)計(jì)了Fanfou_mc，應(yīng)用蒙特卡羅方法模擬聽(tīng)牌對(duì)手手牌來(lái)降低點(diǎn)炮概率；最后，為完成實(shí)驗(yàn)引入了Robot1和Robot2，在個(gè)人平臺(tái)上進(jìn)行3組對(duì)比實(shí)驗(yàn)，前兩組各12輪每輪1 000局，第3組4輪每輪5 000局，共44 000局的比賽，實(shí)驗(yàn)的結(jié)果數(shù)據(jù)驗(yàn)證了本文所提算法的有效性，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析。

為了保證完全隨機(jī)性，在Fanfou_mc中使用的蒙特卡羅模擬方法，沒(méi)有考慮到其他玩家的歷史棄牌情況；未來(lái)可以在小批量樣本對(duì)手建模角度和深度學(xué)習(xí)兩個(gè)方面做進(jìn)一步的研究，前者是根據(jù)對(duì)手的棄牌歷史進(jìn)行建模，以預(yù)測(cè)對(duì)手需要的牌，后者則是建立己方的模型，兼顧勝率和點(diǎn)炮率。深度學(xué)習(xí)視角是將4個(gè)Robot自對(duì)弈的牌譜數(shù)據(jù)進(jìn)行訓(xùn)練，生成棄牌的模型，將該模型與Fanfou_ba、Fanfou_op和Fanfou_mc做對(duì)比實(shí)驗(yàn)，驗(yàn)證深度學(xué)習(xí)訓(xùn)練的棄牌模型的有效性。