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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

圖2 nine-gate（九門）牌型TFig.2 nine-gate card type

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

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

2 基于知識和手牌模擬的麻將AI

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

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

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

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

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

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

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

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

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

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

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

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

輸出最佳棄牌選擇。

1) 手牌遍歷23種層級牌型，更新4個(gè)等級棄牌列表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ù)牌中對應(yīng)的牌，0表示沒有對應(yīng)的序數(shù)牌，冒號后面的具體牌型代表?xiàng)壟茣r(shí)手牌需滿足的條件，若滿足條件則將對應(yīng)的牌加入當(dāng)前等級的棄牌列表。

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

2.2 聽牌有效數(shù)和吃牌優(yōu)先級

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

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

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

算法2基于聽牌有效數(shù)的決策過程

輸入手牌HAND；

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

1) FORiIN len(HAND) DO

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

3) TEMP_HAND.remove(HAND[i])

4)調(diào)用判聽返回能否聽牌和聽牌結(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)對應(yīng)的手牌HAND[i]

11) END IF

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

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

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

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

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

2.3 聽牌對手的手牌模擬

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

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

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

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

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

圖6 Fanfou_mc流程Fig.6 Flow of Fanfou_mc

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

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

算法3基于對手手牌模擬的棄牌決策過程

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

輸出最佳棄牌選擇。

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

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

3) IF OPPONENTi聽牌THEN

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

5) WHILE (TRUE) DO

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

7) IF SIM_LIST能夠聽牌 THEN

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

9) END IF

10) IFj= = 10 THEN // 模擬10種聽牌手牌

11) BREAK

12) END IF

13) END WHILE

14) END IF

15) END FOR

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

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

18) 生成棄牌列表對應(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)對應(yīng)的牌

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

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

表3 中國計(jì)算機(jī)博弈錦標(biāo)賽首屆麻將項(xiàng)目決賽成績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)本文方法，在一臺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)測試模擬10種聽牌手牌的平均模擬次數(shù)為6 000次，平均消耗時(shí)間1.5 s，符合比賽出牌時(shí)間限制3 s的要求。

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

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

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

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

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

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

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

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

在第1組對比實(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)證了聽牌有效數(shù)和吃牌優(yōu)先級策略的有效性，勝利場數(shù)比較如圖8所示。

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

第2組對比實(shí)驗(yàn)結(jié)果數(shù)據(jù)見表5，以表5中第一輪比賽數(shù)據(jù)為例，在第1輪比賽中一共進(jìn)行了1 010場比賽，一共點(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對比實(shí)驗(yàn)結(jié)果Table 5 Second set of Fanfou_op, Fanfou_mc and Robot comparative experiment results

在第2組對比實(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%，勝利場數(shù)和點(diǎn)炮局?jǐn)?shù)比較如圖9所示。

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

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

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

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

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

4 結(jié)束語

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

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