结合先验知识与蒙特卡罗模拟的麻将博弈研究

王亚杰，乔继林，梁凯，谢延延

（1.沈阳航空航天大学 工程训练中心, 辽宁 沈阳 110136; 2.沈阳航空航天大学 计算机学院, 辽宁 沈阳110136）

计算机博弈是通过计算机给出着法，与人类选手或另一个计算机进行的各种游戏对弈，是人工智能领域中最具挑战性的研究方向之一，被称为人工智能科学的“果蝇”[1-3]。

近些年来，DeepMind团队开发的Alpha系列[4-7]使得人工智能在完备信息博弈中完全超越了人类。而以德州扑克为代表的Pluribus在无限制德州扑克的比赛中成功战胜五名专家级人类玩家，标志着人工智能在多人非完备信息博弈领域取得了重大突破[8-11]。

非完备信息博弈中隐藏信息对于博弈难度的影响较大，信息集数目和信息集平均大小与博弈复杂度成正比[12]。其中一对一德州扑克通过子博弈策略达到近似纳什均衡求解[13]，而在多人扑克博弈中没有合适的策略。麻将隐藏信息的数量远远超过德州扑克，所以麻将博弈研究比德州扑克更加复杂。

麻将除了丰富的隐藏信息，复杂的计分规则和出牌规则，还需要考虑多种决策类型。任意一位玩家的吃、碰、杠动作都会改变后续玩家的摸牌顺序，因此我们很难为麻将构建一棵规则的博弈树。一些在围棋和德州扑克中表现很好的算法，如蒙特卡罗树搜索、蒙特卡罗反事实遗憾最小化等都无法直接应用于麻将博弈，导致麻将博弈中没有经典博弈算法可以对比，需要自行设计对比算法。

本文的研究以胜利局数和点炮次数作为算法效果的评价指标，不考虑复杂的计分规则。本文主要针对麻将博弈中的弃牌和听牌模块进行了设计，通过对比实验验证了所提出策略和算法的有效性。贡献及创新点总结如下：

1) 设计了基础版算法Fanfou_ba，以最快听牌、胡牌为目标，应用先验知识，针对弃牌模块细粒度地设计了弃牌的优先层级，并对吃牌模块作了简单的限制处理。Fanfou_ba在第十四届中国计算机博弈锦标赛麻将项目中获得冠军，取得了较好的效果。本文将Fanfou_ba作为基准算法与提出的其它算法进行对比。

2)在Fanfou_ba基础上设计了优化版算法Fanfou_op。首先，针对听牌模块提出了“听牌有效数”的设计方法；其次，完成了吃牌模块的优先级设计；最后，实现了补杠、特殊牌型（如七对和碰碰胡和连牌牌型）的弃牌选择处理。经第一组12 000局对比实验，Fanfou_op领先Fanfou_ba 1 171局，相比Fanfou_ba胜率提高了9.76%。

3)针对麻将多智能体博弈场景和麻将点炮让己方收益最小化的问题，不再局限于己方AI的设计，也为降低其他选手的胡牌概率采取措施，在Fanfou_op基础上设计了提升版算法Fanfou_mc，应用蒙特卡罗方法模拟听牌选手手牌。经第二组和第三组共计32 000局对比实验，Fanfou_mc在胜率分别提升0.2%和0.13%的基础上，点炮率分别降低了0.4%和0.47%，验证了使用蒙特卡罗方法模拟听牌选手手牌对避免点炮的有效性。

1 相关工作

麻将的胡牌规则基本一致，但由于地区文化差异，玩法稍有不同。例如，具体番数计算、牌的种类和数目。本文研究的麻将沿用2020年“竞技世界杯”中国大学生计算机博弈大赛暨第十四届中国计算机博弈锦标赛麻将项目规则[14]，牌库只有序数牌，不考虑其他牌型种类。图1显示了27种序数牌，每种序数牌有4张，共108张牌。

图1 麻将序数牌Fig.1 Mahjong ordinal tile

目前关于麻将博弈的研究并不多，Cheng等[15]在2017年首次使用数学技术，通过基本组合理论研究麻将中一组特殊的牌型k-gate。例如：清一色的13张牌型T称为nine-gate (九门)，如图2所示，可以向T中添加任意一张筒类牌实现胡牌。

图2 nine-gate（九门）牌型TFig.2 nine-gate card type

来自悉尼科技大学和陕西师范大学的Li等[16]在2019年的论文中定义了“缺牌数”的概念，缺牌数代表当前牌面的好坏，缺牌数为0时代表胡牌。同时提出最优策略，在k次牌面变换（k≥ 1）的条件下增加胡牌的概率，确定当前该打的牌。上述两篇论文的研究都是基于起手牌为13张的麻将，并且只考虑了萬条筒3种序数牌型。

关于麻将博弈算法的研究可以分为经验知识和深度学习两个视角。前者的研究主要集中在台湾麻将，以先验知识设计为研究重点，并结合一些经典算法[17-19]；而后者主要被应用于日本麻将，通过大量的专家牌谱数据进行神经网络训练，其中最显著的成果是微软亚洲研究院研发的AI Suphx[20-24]，内陆麻将博弈的研究总体上还处于起步阶段[25-27]。

2 基于知识和手牌模拟的麻将AI

本文麻将博弈主要内容框架如图3所示，设计了3种麻将AI算法：基础版算法Fanfou_ba、优化版算法Fanfou_op和提升版算法Fanfou_mc。其中，Fanfou_ba考虑了弃牌模块的优先级设计和吃牌模块的限制处理；Fanfou_op针对听牌和吃牌模块提出了听牌有效数和吃牌模块的优先级；Fanfou_mc考虑到多智能体博弈场景和麻将点炮的特点，应用蒙特卡罗方法对听牌对手手牌进行了模拟。3种麻将AI算法的博弈水平呈现渐进式提升，下面分别对3种算法进行介绍。

图3 主要内容框架Fig.3 Main content framework

2.1 弃牌优先级和吃牌限制

麻将中听牌是指缺少一张牌便能胡牌的状态，如图2的牌型，缺少任意一张筒字牌；胡牌是指形成特定的牌型(四个组合和一个对子，组合指顺子或刻子)，分为自摸胡牌和点炮胡牌，自摸和炮胡的区别在于缺少的一张牌是由自己摸到还是对手打出。胡牌用式(1)表示：

式中：ABC代表顺子；AAA代表刻子；AA代表对子；x(.)和y(.)代表对应牌型的数目。本文研究的麻将起手牌是13张，此时x+y=4，而在起手牌16张的麻将博弈中，x+y=5。

Fanfou_ba要实现尽快听牌、胡牌的目标，每次弃牌处理时都要打出当前手牌中最不需要的牌，Li等[15]在论文中定义的缺牌数也说明了弃牌模块的重要性[16]。

Fanfou_ba针对弃牌模块总体设计了4个优先级，详见表1。假设摸到1张牌后的手牌如图4所示，分别对应4种类型的单牌：两边都不搭的单牌有1条和7萬(没有2条、3条和5萬、6萬、8萬、9萬)；只搭一边的单牌有5条、7条和9条(没有4条、6条和8条)；对子间隔搭的单牌有1萬和4萬(都没有3萬)；对子旁边搭的单牌有4萬(没有2萬和5萬)。

表1 弃牌优先层级Table 1 Priority level of discard

图4 摸到1张牌后的手牌样例（14张）Fig.4 Sample hand after drawing 1 card(14 tiles)

表1中具体牌型是通过大量测试总结出来的，层序代表了同等优先级下单牌牌型弃牌的先后顺序。因为1和9的序数牌可搭的牌有2种（分别是2、3和7、8对应的序数牌），2和8的序数牌可搭的牌有 3种，3、4、5、6、7的序数牌可搭的牌有4种，所以顺序分为：1和9对应的序数牌（1 条/萬/筒和 9 条/萬/筒）；2 和 8 对应的序数牌；3、4、5、6、7对应的序数牌。数字下面的下划线代表这张牌不是0张，可能多张或1张，数字下面双划线代表这张牌不是1张，可能多张或0张，数字下面虚线代表这张牌数量不为2，可能0、1、3、4张。算法1描述了基于弃牌优先级的决策过程。

算法1基于弃牌优先级的决策过程

输入手牌，已经打过的牌HISTORY；

输出最佳弃牌选择。

1) 手牌遍历23种层级牌型，更新4个等级弃牌列表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中的数字代表序数牌中对应的牌，0表示没有对应的序数牌，冒号后面的具体牌型代表弃牌时手牌需满足的条件，若满足条件则将对应的牌加入当前等级的弃牌列表。

因为比赛规则中规定吃牌获得分数低于碰牌和杠牌获得的分数，所以针对一些不合理的吃牌动作策略进行了优化处理。例如：限制了拆除手牌中刻子(3张一样的牌)或两个对子进行吃牌的动作策略，因为这样的吃牌处理可能会丢失碰牌或杠牌获得更高分数的机会。

2.2 听牌有效数和吃牌优先级

麻将规则中明确规定，AI一旦听牌后不能再更改手牌，只能打出摸到的牌或者做杠牌和胡牌处理。本节针对Fanfou_ba在设计时没有考虑到死听(听牌有效数为0)的问题，提出了应用听牌有效数的算法Fanfou_op。听牌有效数是听牌后所胡牌(胡张)的有效数量，也就是指牌库(未知牌)中剩余胡张的个数，不包含手牌和已经打出去的牌(已知牌)中的胡张，并将其应用在弃牌处理之前的判听模块。

首先，Fanfou_op获得一张牌后，轮流打出手牌中每一张牌，判断手牌是否达到听牌状态；其次，统计听牌有效数；再次，选择弃牌后听牌有效数最大的手牌打出；最后，鉴于听牌有效数与胡牌概率成正比，因此Fanfou_op在听牌有效数小于2时选择放弃听牌。假设听牌后能胡的牌有h种(0 ≤h≤9)，已经打出去的牌中含有的胡张数有d张，手牌中含有的胡张数有m张，此时听牌有效数t_num的计算方法如公式(2)。

算法2描述了基于听牌有效数的决策过程。Fanfou_op在每一次弃牌前都会调用判听方法，在能够听牌的条件下，计算所有胡牌张数h以及听牌有效数t_num，当t_num ≥2时选择对应的手牌打出，然后听牌；否则放弃听牌，按照弃牌优先级进行弃牌处理。

算法2基于听牌有效数的决策过程

输入手牌HAND；

输出最佳弃牌选择（听牌有效数最大的弃牌）。

1) FORiIN len(HAND) DO

2) TEMP_HAND = 复制(HAND)

3) TEMP_HAND.remove(HAND[i])

4)调用判听返回能否听牌和听牌结果得到CAN_TING和RESULT

5) IF CAN_TING THEN

6) 计算HAND[i]弃牌后的TING_NUM

7) END IF

8) END FOR

9) IF max(TING_LIST) > 1 THEN

10)返回 max(TING_LIST)对应的手牌HAND[i]

11) END IF

假设摸到一张牌后的手牌如图5所示，已打出去的胡张有x个。打出手牌中1萬后，将有3萬和6萬两种胡张，手牌中3萬和6萬各有1个，则此时的听牌有效数为 2 ×4−2−x；打出手牌中3萬或6萬后，将有1萬一种胡张，手牌中1萬有一个，则此时的听牌有效数为1 ×4−1−x；选择打出牌后听牌有效数最大的手牌做弃牌处理。

图5 摸到1张牌后的手牌样例（5张）Fig.5 Sample hand after drawing 1 card(5 tiles)

Fanfou_ba针对吃牌模块仅做了两种特殊牌型的限制处理，并不足以应对复杂的情况。例如：上家打出5萬，Fanfou_ba的手牌中有两张3萬、一张4萬和一张6萬，Fanfou_ba会选择3萬和4萬进行吃牌，但理想的动作策略应该是保留3萬的对子而选择4萬和6萬进行吃牌。

为解决上述问题，Fanfou_op提出了将吃牌处理模块划分为3个优先级的方法，详见表2。吃牌处理时，首先，考虑两个单牌的牌型；其次，考虑一个对子和一张单牌的牌型；最后，考虑两个对子的牌型，其中两个对子吃牌的情况可以细分为3种特定条件。

表2 吃牌优先级Table 2 Priority of chow

2.3 听牌对手的手牌模拟

麻将属于多人非完备信息博弈，Fanfou_ba和Fanfou_op均属于单智能体的范畴，仅考虑己方AI的设计而没有考虑到对手的手牌，忽略了多人博弈的特点，导致点炮概率较大，未能实现己方收益最大化。

文献[16]通过使用蒙特卡罗方法模拟整个牌局来降低点炮概率：首先，随机生成3个玩家的缺牌数；其次，检查缺牌数是否合理；最后，模拟选手手牌。但是这样模拟会产生两个问题：1)缺牌数的合理判断需要结合人类经验，具有较大的随机性；2)最后随机产生的手牌是经由牌型的组合划分（未知牌中顺子、刻子、对子和单牌的组合）产生的，人工划分的组合考虑不到所有的可能性。

针对上述问题，提出了通过蒙特卡罗方法模拟听牌选手手牌的算法Fanfou_mc。AI进行模拟需要满足己方没有听牌和对手有听牌两个条件，后者避免了考虑结合经验并且有较大随机性的缺牌数问题，只需要模拟出的手牌满足听牌条件；前者保证了AI追求最快听牌胡牌的目标不受影响。

通过模拟听牌选手手牌，计算弃牌列表中每张牌的点炮次数。若有3家对手听牌，则同时模拟3个玩家的手牌，选择优先级高的弃牌列表中点炮次数最少的牌打出，实现了通过模拟对手手牌降低点炮几率的目标。

Fanfou_mc包括两个参数：模拟手牌的种类数目和模拟听牌玩家手牌的数目。其中，模拟手牌种类数目与模拟消耗时间成正比、与点炮概率成反比，考虑比赛有出牌时间的限制，经反复实验后将模拟手牌种类数目设置为10，在尽可能降低点炮概率的同时出牌时间不超过比赛时间的限制，Fanfou_mc的方案流程如图6所示。

图6 Fanfou_mc流程Fig.6 Flow of Fanfou_mc

模拟听牌玩家手牌的数目(sim_num)由听牌玩家的吃、碰、杠数目决定，设一听牌玩家吃牌、碰牌、杠牌数目分别为C、P、K，则模拟手牌数目计算方法如式(3)：

Fanfou_mc模拟完所有听牌选手手牌后，选择弃牌列表中点炮次数为0的牌做弃牌处理时，点炮概率最小。若所有牌点炮次数都为0，则会按顺序选择弃牌列表中第一张点炮次数为0的牌打出；若弃牌列表中没有点炮次数为0的牌，则会选择点炮次数最少的牌打出。算法3描述了通过模拟听牌对手手牌降低点炮概率的决策过程。

算法3基于对手手牌模拟的弃牌决策过程

输入手牌HAND，已经打过的牌HISTORY；

输出最佳弃牌选择。

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

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

3) IF OPPONENTi听牌THEN

4) 计算OPPONENTi的手牌数目sim_num

5) WHILE (TRUE) DO

6) SIM_LIST = CARD中随机模拟sim_num个牌

7) IF SIM_LIST能够听牌 THEN

8)j++ // 模拟的听牌手牌数目

9) END IF

10) IFj= = 10 THEN // 模拟10种听牌手牌

11) BREAK

12) END IF

13) END WHILE

14) END IF

15) END FOR

16) 将弃牌列表中每张牌依次加入到模拟听牌选手的手牌

17) 统计弃牌列表中每张牌的点炮次数

18) 生成弃牌列表对应的点炮次数列表FIRE_LIST

19) IF min (FIRE_LIST) > 1 THEN

20) 选择FIRE_LIST中第一个min (FIRE_LIST)打出

21) END IF

22) RETURN min (FIRE_LIST)对应的牌

3 实验设计与分析

基于弃牌优先级和吃牌限制设计的Fanfou_ba参加了2020“竞技世界杯”中国大学生计算机博弈大赛暨第十四届中国计算机博弈锦标赛麻将项目比赛，经过三轮初赛每轮50局，三轮决赛每轮100局比赛，获得了冠军，决赛最终成绩如表3所示，本文将此AI作为基准程序。

表3 中国计算机博弈锦标赛首届麻将项目决赛成绩Table 3 Final result of the first Mahjong event of China Computer Game Championship

3.1 实验方案

实验环境是Pycharm2019，使用Python3.7实现本文方法，在一台Inter (R) Core (TM) i5-4210U 1.7 GHz，内存为4 GB，显卡为NVIDIA GeForce 820M的Window 10操作系统上进行实验。经测试模拟10种听牌手牌的平均模拟次数为6 000次，平均消耗时间1.5 s，符合比赛出牌时间限制3 s的要求。

麻将属于多智能体博弈项目，为能够完整进行实验并增加麻将博弈中的不确定性，引入了随机出牌算法Robot，即弃牌处理时随机打出手牌。由于麻将博弈中吃、碰、杠的动作策略会打乱出牌顺序和加快博弈进程，所以Robot吃、碰、杠的动作决策完全沿用Fanfou_op的设计，更加符合真实比赛和线下博弈的场景。本文实验的博弈平台框架设计流程如图7所示，具体设计可参考[14]中名为“完整实验2.1”的文件。

图7 对比实验流程Fig.7 Flow of comparative experiment

本文以胜利场数和点炮次数作为评价指标，进行了3组对比实验。其中，第一组对比实验中Robot1、Robot2、Fanfou_ba和 Fanfou_op进行比赛，验证Fanfou_op中的改进策略的有效性；第2组对比实验中Robot1、Robot2、Fanfou_op和Fanfou_mc进行比赛；第3组对比实验中Fanfou_op、Fanfou_op、Fanfou_mc和Fanfou_mc进行比赛。后两组实验是为了充分验证Fanfou_mc中通过蒙特卡罗方法模拟听牌对手手牌避免点炮的效果，第2组引入Robot是为增加比赛中的不确定性，对应多智能体博弈中有牌力较弱选手参与的场景，第3组对应多智能体都是牌力较强选手博弈的场景。

麻将规则表明，吃牌只能吃上家的牌，因此对比实验中需要考虑AI之间的顺序。经式(4)计算可知前两组对比实验顺序有12种，为确保实验的严谨性，每种排列方式要进行一轮比赛，每轮比赛有1 000局非流局(一局比赛结束后有人胡牌)的测试结果；第三组对比实验顺序有4种，安排4轮比赛，每轮比赛有5 000局非流局的测试结果。

3.2 实验结果与分析

实验数据中位置1、位置2、位置3、位置4分别代表麻将智能体的位置，局数是指在该轮比赛中进行的总场数(包括每轮比赛中产生的流局)，A、B、C、D、E分别代表 Fanfou_ba、Fanfou_op、Robot1、Robot2和Fanfou_mc五个智能体，炮数是指在该轮比赛中玩家的点炮总局数。第1组对比实验结果数据见表4。

以表4中第一轮比赛数据为例，在第1轮比赛中一共进行了1 008场比赛，其中Fanfou_ba获胜472局，Fanfou_op获胜486局，Robot1和Robot2分别获胜22局和20局。

表4 第1组Fanfou_ba、Fanfou_op和Robot对比实验结果Table 4 First set of Fanfou_ba, Fanfou_op and Robot comparative experiment results

在第1组对比实验中，Fanfou_ba获胜5 105局，胜率为42.54%，Fanfou_op获胜6 276局，胜率为52.3%；Fanfou_op相比Fanfou_ba胜率提升9.76%，验证了听牌有效数和吃牌优先级策略的有效性，胜利场数比较如图8所示。

图8 第1组对比实验结果Fig.8 First set of comparative experiment results

第2组对比实验结果数据见表5，以表5中第一轮比赛数据为例，在第1轮比赛中一共进行了1 010场比赛，一共点炮787局；其中Fanfou_mc获胜480局，点炮128局，Fanfou_op获胜471局，点炮144局，Robot1获胜24局，点炮284局，Robot2获胜25局，点炮231局。

表5 第2组Fanfou_op、Fanfou_mc和Robot对比实验结果Table 5 Second set of Fanfou_op, Fanfou_mc and Robot comparative experiment results

在第2组对比实验中，Fanfou_op获胜5 698局，Fanfou_mc获胜6 276局，Fanfou_mc的胜率相比Fanfou_op提升了0.2%；Fanfou_op点炮1 547局，Fanfou_mc点炮1 509局，Fanfou_mc的点炮率相比Fanfou_op降低了0.4%，胜利场数和点炮局数比较如图9所示。

图9 第2组对比实验结果Fig.9 Second set of comparative experiment results

第3组对比实验结果数据见表6，经计算可以得出，Fanfou_mc的胜率相比Fanfou_op提升了0.13%，点炮率相比Fanfou_op降低了0.47%。后两组对比实验验证了模拟听牌对手手牌避免点炮策略的有效性，胜利场数和点炮局数比较如图10所示。

图10 第3组对比实验结果Fig.10 Third set of comparative experiment results

表6 第3组Fanfou_op和Fanfou_mc对比实验结果Table 6 Third set of Fanfou_op and Fanfou_mc comparative experiment results

实验数据表明，完善的知识体系使Fanfou_op能够较快达到听牌状态，对麻将AI的博弈水平有显著的提升。由于Fanfou_mc中蒙特卡罗模拟策略无法在己方处于听牌状态时使用，所以Fanfou_mc没有明显提高胜率。

4 结束语

本文以麻将为研究载体，提出了结合知识与蒙特卡罗模拟的博弈算法。首先，阐述了冠军AI智能体Fanfou_ba弃牌优先级和吃牌限制的设计思想；其次，以Fanfou_ba为基础设计了Fanfou_op，提出了听牌有效数和吃牌优先级的方法；再次，在Fanfou_op基础上设计了Fanfou_mc，应用蒙特卡罗方法模拟听牌对手手牌来降低点炮概率；最后，为完成实验引入了Robot1和Robot2，在个人平台上进行3组对比实验，前两组各12轮每轮1 000局，第3组4轮每轮5 000局，共44 000局的比赛，实验的结果数据验证了本文所提算法的有效性，并对实验结果进行了分析。

为了保证完全随机性，在Fanfou_mc中使用的蒙特卡罗模拟方法，没有考虑到其他玩家的历史弃牌情况；未来可以在小批量样本对手建模角度和深度学习两个方面做进一步的研究，前者是根据对手的弃牌历史进行建模，以预测对手需要的牌，后者则是建立己方的模型，兼顾胜率和点炮率。深度学习视角是将4个Robot自对弈的牌谱数据进行训练，生成弃牌的模型，将该模型与Fanfou_ba、Fanfou_op和Fanfou_mc做对比实验，验证深度学习训练的弃牌模型的有效性。