一种大众麻将计算机博弈的胡牌方法研究

彭丽蓉，赵海璐，甘春晏，刘 洁，陈俊宇

(1.重庆理工大学 人工智能系统研究所，重庆 401135；2.重庆工业职业技术学院 人工智能与大数据学院，重庆 401120)

计算机博弈，也被称为机器博弈，一直是人工智能研究中的热门领域，其覆盖面非常广泛，最广为熟知的是在计算机博弈游戏中的应用，特别是棋牌类的游戏，许多研究者们致力于研发出能够像人类一样思考和决策的游戏智能体[1]。麻将是一种很受欢迎的多人游戏，老少皆宜，且种类与玩法十分丰富。在计算机博弈中，根据博弈中的信息是否能完全公开，分为完美信息博弈和非完美信息博弈2个类型，显然麻将属于非完美信息博弈类型。

顾名思义，在完美信息博弈中，对弈信息对对弈各方是完全公开的、透明的，智能体的构造或策略的设计大多可以基于树搜索和节点评估的方式，通过构建博弈树，设计不同的评估函数或方法来评估博弈树中每个节点，即可能的博弈局面，如围棋、西洋跳棋、五子棋等[2]，由此产生了系列经典的、高效的搜索算法，比如极大极小搜索算法[3]、alpha-beta剪枝算法[4]、UCT算法[5]等。

在非完美信息博弈中，不适合于照搬完美信息博弈方法来构造博弈智能体[6]。比如，非完美信息博弈游戏麻将博弈中，玩家除能知道已公开的出牌牌张和自己手上牌张外，其余牌张信息是不知道的，也就是不透明的，产生大量未知信息，而且，麻规则中还存在杠、碰、吃等着法，将打乱出牌顺序而产生随机性，从而增加决策困难。目前，麻将智能体的博弈策略设计方法主要采用如下2种方法：① 基于规则和经验[7-8]；② 采用深度强化学习算法[9-10]。方法①能够达到一定的牌力，但缺乏灵活性[11]，并且对设计者的麻将游戏实战能力提出要求，否则，将直接影响智能体的博弈水平。方法②能够构造出较高水平的麻将博弈智能体，如微软2019年设计的suphx，但是其模型构建难度大、训练成本高昂、普适性差，不利于推广。

综上，拟提出一种既具有一定灵活性、又具备一定普适性和低训练代价的胡牌距离概念，再基于最短胡牌距离数量值，融合牌局中的已知牌张信息和麻将博弈的先验知识，帮助博弈智能体快速胡牌，提升麻将智能体博弈水平。

1 麻将规则概述

麻将起源于中国，最初为上流阶层的游戏，在历史演变过程中逐渐流传于民间，其规则也因而演变成多种多样。本文以2020年中国计算机博弈锦标赛中大众麻将项目的规则为案例，说明麻将规则数量化的过程。

概况：麻将有筒、条、万3种花色，每种花色含数字1～9共9个牌张，每个牌张共4张，共108张牌。分列如图1所示的东、南、西、北4位玩家，玩家每次出牌动作的时间限制在3秒内。当有一个玩家成功胡牌，则该牌局就结束。

图1 麻将博弈示意图及牌型图例

报听：玩家手上的牌张还差一张牌，就可赢牌时的牌局状态。按照博弈规则要求，在报听后，玩家的博弈之鞥提就进入托管模式，即除胡牌行为外，不能再做任何其他动作，比如换牌、吃牌、碰牌和杠牌等。

出牌行为顺序：在打牌中，每方玩家起手牌规定是13张，但指定的“庄家”将打出第一手牌，就会手持14张，然后按顺时针方向依次出牌。除正常的出牌外，还有4种特殊的出牌行为，其优先级顺序为“胡牌>杠>碰>吃”：

1)吃牌：吃牌是指玩家拥有两张相邻或相隔一张的牌，当上家打出相邻或是中间的这张牌时，可以进行吃牌;

2)碰牌：碰牌是指有一对一样的牌，当其他任何一位玩家打出相同牌的时候，玩家可碰牌;

3)直杠：杠牌的一种，指玩家拥有刻子(3张一样的牌)，当其他任何玩家打出该刻子的第4张牌时，进行开杠即为直杠。

4)暗杠：杠牌的一种，当玩家手牌有4张一样牌张时，进行开杠即为暗杠，与直杠的区别的在于刻子的第4张牌由玩家自己从牌墙获得。

5)补杠：玩家碰牌后，再摸到第4张与已碰牌相同的牌，并杠牌，即为补杠。

6)听牌：玩家的手牌还差一张牌即可胡牌的状态，称为听牌状态。玩家可选择是否报听，报听后可以获得分数奖励，但是不可再换牌，即摸什么牌就打什么牌，但在不影响牌的情况下，有杠可以选择是否杠。

7)胡牌：玩家手上的14张牌能够组成特定组合条件的牌型时，即称为胡牌。此组合条件是不同地区、不同玩法的麻将，最大的不同所在。

为了胡牌，玩家需要不断地依据进张组合、拆分，再组合、再拆分，目标就是能最快地将手中14张牌组成特定牌型，这可以用式⑴量化表示，同时在满足式⑴或式⑵基础上，尽可能保证赢得表1所示的最大番值。

表1 牌种及番数

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

(1)

其中0≤a≤4。

b×DD

(2)

其中b=7。

在表1或式⑴或式⑵中，a、b均为整数；AAA表示同花色的任意相同3张牌，称为刻子，如图1中3张四筒；ABC表示同花色的连续顺序的3张牌，称之为顺子，如图1中3张一、二、三万；DD表示同花色的任意2张相同牌张，称之为对子，也称为将牌，如图1中2张四条。

从上可见，牌张分分合合的过程，其实就是一个牌局逼近胡牌状态的过程，与此同时，尽量追求最快时间和最大番值。进一步分析发现，通过计算，可以得到108张麻将牌中每一种胡牌类型的牌型数目，再将牌型数目值由大到小排列可得“基本胡>碰碰胡>清一色>七对”，简称为“x>y>z>q”，这说明表1中番值大小也是玩家胡牌获胜概率的大小写照，番值越大，获胜概率也越小，难度越大，反之亦然。

此外，笔者注意到不同地区的麻将博弈规则差异较大。比如，大众麻将规则与成都地区的“血战到底”麻将规则比较，至少存在2点巨大差异：一是胡牌花色种类不同，“血战麻将”任何胡牌类型，花色限制不超过2种，即必须打缺；而大众麻将从表可见，除表1中z类外，其他3种x、y、q胡牌类型，没有花色种类限制；二是游戏结束方式不同，大众麻将只要有某个玩家胡牌，就宣告游戏结束，而“血战麻将”即使某个玩家胡牌，也不意味着游戏结束，而是剩余玩家需要继续对弈，直到局面中仅有一名玩家没有胡牌或堂子中牌张清零，游戏才宣告结束，这也就是“血战到底”的含义。显然，“血战麻将”的博弈智能体构建难度更大，因为不断的胡牌玩家将会同时隐藏许多牌张信息，让后续玩家难以准确判断局面中剩余牌张，这将极大影响后续玩家的计算、判断和决策，增加博弈难度。

2 胡牌方法

2.1 胡牌距离概念

所谓的胡牌距离d，就是玩家当前手牌与胡牌状态度量值，即玩家当前手牌到最近胡牌类型所需牌张的数量，本质就是缺牌数量。如图2牌例中，尽管存在满足式⑴的3个顺子或刻子，还有2个对子，此时，玩家就面临拆4张“二条”为1个刻子，寻求1个条、筒花色的新对子，还是保留2张“二条”为将牌，再寻求3张条或筒花色的1个顺子或刻子，此时前1种情况距离胡牌还差2张牌、后1种情况距离胡牌还差3张牌，这样2种选择的胡牌距离d就分别是2和3。从胡牌距离大小来讲，选择d=2这条胡牌路线更好，这也是引入胡牌距离的本意，就是利用可量化的概念，告诉麻将博弈智能体胡牌路线的选择方向。当然，理论上讲，胡牌距离d是介于[0，12]区间的整数值，当d=0时，玩家起手就胡牌，这称为天牌，当d=13时，就是手上13张牌全是散乱，没有任何顺子、刻子、对子，理论上需要的胡牌14张牌，需要更换全部手上的13张牌，这称为烂牌。

图2 麻将游戏玩家手牌实例图

此外，麻将博弈常采用拆分方法、寻找其中隐藏的不同胡牌路线，而面对诸多胡牌路线，胡牌距离d就可以是其选择的依据。但是，d值的应用又不能太僵化，这是因为在逼近胡牌的过程中，玩家按照表1需要，不断对手上的牌进行顺、刻、对组合或拆分并同时考虑花色的搭配，这个过程中会产生一些新的牌张组合，如二连牌、搭子，如图3所示。这些新组合是逼近顺、刻、对的最佳牌档，以它们为基础可以建立满足式⑶的集合Q，称之为缺牌集：

图3 麻将博弈牌张组合图例

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

⑶

可以把二连牌、搭子等组合，理解为获得顺、刻、对组合的最佳中间牌张搭档。

2.2 手牌信息集

尽管胡牌距离d的大小可以是麻将博弈智能体的胡牌路线的选择依据，左右胡牌路线的方向选择，但是，博弈进程中，随着麻将游戏开始，东南西北4个玩家首先逐次摸牌获得起手13张牌，其中庄家多一张最先出牌张，为14张，然后是依照麻将规则摸牌、打牌，从而图1堂子中的牌张将会越来越多、玩家手上牌张通常至少有13张，除非有“杠”组合牌张存在或胡牌，牌张数会大于13。因此，玩家能看见的牌张信息就是堂子中的明牌、自己手上的牌和其他玩家各类吃牌、碰牌动作后的明牌，其余牌张信息是不清楚的，这些就是隐藏牌张。此时，如果单纯依据距离d大小，而不考虑隐藏牌张信息，就可能造成永远都不能胡牌，因为需要的胡牌张可能在其他玩家手中，而且是他们固定下来的组合，无论是有意还是无意，都不会打出来。比如，某玩家东仅仅只差将牌，手上有1张“二条”，此时d=1，但是在另外玩家西手中“二条”是1个刻子，此时玩家西不会将“二条”打出，而且还希望杠“二条”以加番，如果玩家东不能洞察而等“二条”，显然东家永远不能胡牌，此时最小的d值反而成为累赘。

除此之外，有时候不同的胡牌路线会拥有相同的胡牌距离。比如某玩家当前手牌为23345B(条)，所有可能的获胜牌型共有9种，玩家在逼近胡牌的过程中，对手牌不断进行拆分，根据不同的获胜牌型，玩家需要等待和需要丢弃的牌张是不同的，具体情况如图4、5所示。

图4 对3为将牌的获胜牌型

图4、5中带有下划线的数字表示玩家若想要以这种牌型获胜所需要的牌张，对应下方则为不需要的牌张。也就是说，玩家若想要以33234B的牌型获胜，就必须从当前的手牌中丢弃5B(条)，等待3B(条)；想要以33345B的牌型获胜，就必须丢弃2B(条)，等待3B。这样的情况总共有9种。同时，由式(3)可得，图中①②③④的获胜路线d=2，而其余5种获胜牌型d=1，显然①②③④的获胜路线并不是玩家的最佳选择。如果仅仅根据d的值来确定玩家的胡牌路线，那么玩家当前有5种胡牌路线可以选择，这5种胡牌路线所需的牌张信息，就构成了信息集I，其中需要的牌张组成缺牌集合Q，不需要的牌张组成弃牌集合D。I与Q、D的关系如式(4)所示。

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

(4)

若按照图4的拆牌方式，Q1={3B，6B}，对应D1={2B，5B}；若按照图5拆牌方式，Q2={2B，5B}，对应D2={3B}，就这样，不同拆牌方式得到的Q和D，共同构建了当前手牌的信息集I。

图5 其他牌作为将牌的获胜牌型

本质上，信息集I中存储的信息，就是玩家当前手牌下，所有可能执行的最优动作策略的合集。当然，依据胡牌距离d构建的信息集I，只是玩家在仅考虑自身手牌下的理想可执行动作，行牌过程中诸多的隐藏信息，必定会影响玩家最终动作决策。因此，胡牌距离d必须与手牌信息、缺牌信息进行融合决策，才能实现博弈智能体的胡牌目标。

2.3 行为决策

根据玩家在当前手牌下计算的胡牌距离以及构建的信息集I，本节的行为决策将介绍在获得手牌信息集的基础上，针对相同胡牌距离下玩家如何决定出牌动作及是否进行吃碰杠动作，提出一种融合场上信息，计算期望胜率的方法，指导玩家具体动作的决策。

在麻将游戏中，玩家所有可执行的动作包括：吃、碰、杠、出牌、摸牌。在计算机中，摸牌动作不需要AI玩家设计实现，直接由计算机程序控制发牌，AI玩家每次自动获得一张新牌，并按序排列。每当轮到玩家执行游戏动作时，首先结合当前场上信息，构建手牌信息集，然后根据手牌信息集，计算每个可能动作的期望胜率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)，可以计算出每个可能执行动作的期望胜率。

基于游戏规则可知，玩家的动作分为两类：出牌动作和其他动作，而其他动作是指吃、碰、杠。本质上，可以将玩家吃和碰的动作决策与玩家出牌动作的决策归为一类。吃、碰的动作与出牌动作有着共同点，其都需得到一张牌，再丢出一张牌，区别在于出牌动作是系统自动为AI玩家随机获得一张牌，然后AI玩家再丢弃一张牌，而吃、碰是“获得”其余玩家丢弃的一张牌，相当于摸进一张已知牌，然后再进行出牌动作，因此，可将吃、碰动作与出牌动作归为一类，看作统一决策情形进行处理[12]。

行为决策总体逻辑是：轮到玩家出牌时，系统已自动替玩家执行“摸牌”动作，因此程序输入牌的张数只可能是2、5、8、11、14张，然后进行出牌动作决策；当其他玩家动作时，AI玩家不断收集场上已知信息，并关注其他玩家丢弃的牌，判断是否进行吃、碰。AI玩家整体执行的逻辑流程如图6所示。

图6中，hand表示玩家当前手牌，state表示玩家当前状态，state=0，表示玩家当前状态是出牌状态，若不为零，则表示玩家为非出牌状态，即吃或碰的状态。hand′表示玩家处于非出牌状态下的手牌。T表示一张牌，初始值为空。d和I分别为根据玩家当前手牌计算的胡牌距离及构建的信息集，t表示最终计算得到的玩家可以丢弃的牌，Action表示玩家最终的动作。

图6 整体流程框图

当玩家为出牌状态，hand的值为玩家当前手牌，T的值为空，首先计算d，并构建I，然后计算每个可执行动作(即每张可以丢弃的牌)的期望胜率，最后选择出期望胜率最高的动作(即最终丢弃的牌t)，判断t的值是否与T的值相等，若不相等，则执行该动作。由于在出牌状态下，T的值始终为空，因此T和t永远都不会相等，Action=t，表示丢弃的牌为t。

当玩家为非出牌状态，即说明此时需要执行的动作是判断玩家是否进行吃或碰。程序中先假设已经进行吃或碰，将T的值赋为可吃或可碰的那张牌的值，并更新hand，处理逻辑与玩家处于出牌状态时一致，只是T的值不再为空。最后当T与t相等时，Action的值为pass，表示玩家不执行吃或碰的动作；T与t不等时，表示玩家执行吃或碰的动作，并丢弃t。

3 实验结果与分析

根据游戏规则，在有限的游戏局数中，游戏的获胜是由玩家最终累计获得的分数多少决定，而每局游戏，只要有一个玩家胡牌，则本局游戏结束，因此，采用维持最少缺牌数的胡牌方法，来实现快速胡牌，通过在胡牌次数上的优势，来获得最终的游戏胜利。为了验证本文方法的有效性，设计了与基于专家经验出牌程序MJ1和普通人类玩家MJ2的对照实验。使用平台为竞技世界(成都)网络技术有限公司研发的麻将博弈对战平台，该平台中有随机发牌的AI及判胡处理程序。实验程序只需按照接口文档，返回规定的数据，即可将多个不同类型的实验程序接入该平台，进行麻将对战。对手设置如表2所示。

表2 实验对手设置

基于胡牌距离设置的程序MJ-D，分别与上述对手进行1 000局的对弈，根据最终累计的胡牌总得分来判定胜负关系。实验设计一个MJ-D分别和3个MJ1、MJ2对局，这样可以保证3个对手的游戏水平是一致的，能尽可能避免位置不同带来的影响。表3和表4分别为和MJ1、MJ2的对局结果。

表3 对局结果

表4 对局结果

表1中MJ1基于专家经验设置而成，具备一定的对战能力，牌力在普通玩家之上，而表2中MJ2的牌力，更接近普通人类水平。根据表3和表4的对局结果可得，MJ-D在1 000局对弈中，虽然每局的平均得分并不是最高的，但是总的胡牌次数最多，最终的总得分也是最高的。由此，基于胡牌距离的胡牌方法舍弃高分牌型，以快速胡牌为目的，能够在胡牌次数的优势上赢得更多的分数，从而获取最终游戏胜利。

4 结论

提出了麻将博弈胡牌方法，基于胡牌距离构建手牌信息集，融合场上信息，通过维持最少缺牌数，计算相同胡牌距离局面下的期望获胜概率，更好地决定玩家动作，实现快速胡牌，从而在有限的游戏局数中，取得较多次数的游戏胜利。实验显示，基于胡牌距离的胡牌方法能够更为准确的决定玩家动作，虽然每局的平均得分不是最高的，但是在多局游戏中的获胜次数，明显高于基于经验的方法，最终的累积得分也是最高的。本文方法存在的不足是：① 在游戏中，需要收集场上所有已知牌的信息，并据此计算该局面期望胜率，而前期场上已知信息较少，胡牌距离较大时，信息集的构建会存在不可避免的偏差，导致游戏前期动作决策失误；② 舍弃了高分牌型，丧失了一部分获得高分的机会。后续将对游戏前期已知牌信息较少时，信息集的构建进行进一步研究，以减少前期错误动作对后续行为决策的影响，同时，加入高分牌型的处理决策。