二打一游戏拆牌算法研究

乔秀明,黄文杰,2,李淑琴,2

(1.北京信息科技大学 计算机学院， 北京 100101；2.感知与计算智能联合实验室， 北京 100101)

0 引言

机器博弈是人工智能研究的重要领域，是检验人工智能发展水平的一个重要平台。根据博弈信息是否可以完全可知，可分为完全信息博弈和非完全信息博弈[1]，如代表完全信息博弈的围棋、象棋等和代表非完全信息博弈的二打一、麻将等。在完全信息博弈中，谷歌的“Alphago Zero”[2]达到计算机博弈领域的新高度，为完全信息博弈游戏提供了通用解决方法，计算机棋手逐渐达到了职业玩家的水平，甚至超过人类玩家，这其中深度学习在游戏中起到了很大的作用。在非完全信息博弈中，玩家的操作范围庞大，如有限注德州扑克，其所有信息集数量达到了(3.19×10)14，参与者要基于信息集进行决策[3]。对信息集中历史状态的数量关系和问题的规模及复杂度通常采用的简化方法有：使用在完全信息博弈中[4]应用广泛的蒙特卡罗树搜索[5]和对博弈树的抽象化[6]。博弈树的抽象化本质是采用一种方法将复杂的博弈树状态节点合并，通常使用聚类或者分类方法。2017年，CMU设计的Lbratus[7]使用抽象方法以细化状态空间和策略空间[8]，Andre按照胜率进行聚类，引入状态空间算法和整数规划对牌型进行抽象化[9]。

二打一(俗称斗地主)[10]是一款集趣味性、广泛性、专业性于一身的3人棋牌游戏，作为研究非完全信息博弈的典型问题，受到人工智能领域内专家越来越多的关注。目前文献[11]在对二打一手牌水平评估的过程中直接以单张手牌为单位进行手牌水平分析，并以单张牌的编号所对应的角色进行分配，使用生成对抗网络来达到控制手牌水平的目的。但是，其未考虑到牌与牌之间按照出牌规则的组合方式。文献[12]使用二打一出牌机器人进行自博弈来对二打一手牌水平进行评估。虽然对二打一手牌进行研究的成果多种多样，如文献[13]基于权值对二打一手牌进行了拆分，但是模拟人类玩家拆牌的研究却少有记录。本文在对二打一手牌拆分研究的过程中受到自然语言处理领域序列标注任务的启发，使用基于深度学习的BILSTM-CRF模型[14]作为建模方法尝试对二打一初始手牌进行牌型标注训练，在与传统的最小组合拆分法进行比较后，获得了初步的成效。

1 二打一手牌拆分模型

1.1 手牌拆分意义

手牌拆分指将当前手牌(初始手牌或对局中某个时刻的手牌)按照出牌规则拆分成合法牌型。拆牌效果的好坏影响这个打牌过程。对于人类玩家来说，每次进行二打一游戏对战时，在确定好自己的初始手牌后，玩家都会对自己的初始手牌进行在心理层面的预拆分，即回答如何拆分出能够压制住对手的牌型、如何拆分出能够在主动出牌时确立主动权的手牌、如何拆分才能把牌面较小的手牌打出去等系列问题，完成初步的拆牌规划。对于新手而言，如果能够利用拆牌模型，在每次出牌前进行手牌拆分，就可以有效地辅助自己的出牌决策，对于二打一计算机博弈智能体而言，也具有重要的借鉴意义。

此外，在机器学习或深度学习对手牌的研究过程中，仅仅以单张牌为单位，用数字化分析和建模整个手牌序列，实际上是难以体现规则中的牌型压制关系的，所以，针对手牌水平评估的研究与手牌拆分存在密不可分关系的。

1.2 二打一手牌牌型

对于任意一条完整的二打一打牌数据，包括了胜者打出的手牌数据和败者打出的手牌数据，其中胜者因优先将手牌打完而取得胜利，其中在打牌过程产生完整的手牌拆分时序序列信息，自然可以提取出来作为训练之用。按照规则，二打一游戏的合法出牌牌型包含的常见牌型如下：

(a)火箭：由小王和大王两张牌组成，可以压制其他一切牌型。当且仅当大王和小王同时在一名玩家手中才能被打出。

(b)炸弹：由4张牌面大小一样的牌组成，可以压制除火箭和炸弹外的其他所有牌型，也可以压制比自己牌面小的炸弹，比如“4444”可以压制“3333”但是不能压制“5555”。

(c)单张：由单张手牌组成的出法，如“3”，“4”，“5”等。

(d)单顺：由连续的单张手牌组合成长度不少于5张的牌，如“34567”，“345678”，“45678”等。

(e)对牌：由2张牌面相同的牌组成的出法，如“33”，“44”，“55”等。

(f)双顺：由至少3组连续的对牌组成的出法，如“334455”，“33445566”，“445566”等。

(g)三张：由3张牌面相同的牌组成的出法，如“333”，“444”，“555”等。

(h)三顺：由至少2组连续的3张组成的出法，如“333444”，“333444555”，“444555”等。

(i)三带一：由3张牌型额外附带单张牌，附带的单张牌在压制上不用比较大小，如“3337”，“4445”等。

(j)三带一对：由3张牌型额外附带对牌，附带的对牌在压制上不用比较大小，如“33377”，“44455”等。

(k)飞机带翅膀：由三顺牌型额外附带单张牌或者对牌，附带的对牌在压制上不用比较大小，附带的牌型要一致，如“33344467”，“333444555789”，“3334448899”等。

(h)四带二：由炸弹牌型额外附带2张单牌或者2个对牌，附带的单牌或对牌在压制上不用比较大小，附带的牌型要一致，如“333345”，“44445588”等。

1.3 基于手牌牌型标注的拆分方法

手牌序列的拆分和NLP(自然语言处理)领域中的中文命名实体识别任务极为相似，都是通过对序列的标注来实现对序列的划分。中文命名实体识别方法可以在每个字上进行标注，标注出句子中的名词、动词等，并按照标注的结果对句子进行划分，用于后续的下游任务，如用B(Begain)、E(End)、V(Verb)将“我们爱祖国”这句话标注成“BEVBE”，并根据标注结果将这句话拆分成“我们”、“爱”、“祖国”3个实体。同理，可将组合成手牌序列的牌型看作要标注的实体，通过标注来进行拆分。

根据现有的数据资源，参考中文命名实体识别中的主流深度学习模型BILSTM-CRF，运用独特的标签信息提取思路，提出了基于BILSTM-CRF模型的手牌牌型标注的拆分方法。BILSTM-CRF模型是由双向长短期记忆网络(BILSTM)和条件随机场(CRF)组成的复合深度学习网络模型。其中双向长短期记忆网络可以提取到序列中前后之间的联系，条件随机场可以学习到序列中单位与单位之间状态的前后联系。BILSTM-CRF模型多用于序列标注任务，尤其在中文命名实体识别工作中应用广泛。二打一初始手牌也是单一的序列，因而可以设计建模对整个序列进行牌型的类别标注，并将标注结果转化为手牌牌型的拆分。为获取人类玩家对手牌的拆分特征，需要通过监督学习的方式从人类玩家真实对战的过程中提取到人类玩家的拆牌方式。

2 二打一拆牌模型设计与实现

2.1 手牌牌型标注

根据二打一计算机博弈规则和利用前述(a)～(h)，进一步实战对局数据分成4类牌型，分类信息用标注序号0、1、2、3所示，如表1所示。

表1 牌型标注示例

在表1中，由于单顺是由单张组合而成，单张和单顺被划分为第0类。拆牌过程中，在处理大量单张时，若存在至少5张连续的单牌，则可以组成单顺。由于连对是由对牌组合而成，对牌和连对被划分为第1类。拆牌过程中，在处理大量对牌时，若存在至少3组连续的对牌，则可以组成连对。由于三顺是由3张组合而成，三张和三顺被划分为第2类。拆牌过程中，在处理大量三张时，若存在至少2组连续的三张，则可以组成三顺。炸弹和火箭被划分为第3类，因为炸弹和火箭均可以去压制其他类型的牌型，属于压制性的牌型。在拆牌过程中，应考虑是否拆分出压制性的牌型或者将压制性牌型拆分成其他类型的牌型。三带一、三带二、飞机带翅膀、四带二不纳入分类范畴，因其由3张、炸弹、单排和对牌组合而成，属于二次组合后的复合牌型。

对一副手牌序列的每一张手牌，以表中的标注序号作为序列的标注表示，如手牌序列“34445556789TA22XD”可以由牌型{3，444555，6789T，A，22，XD}组成，该牌型集合中的牌型为{单牌(c)，三顺(h)，单顺(d)，单牌(c)，对牌(e)，炸弹(a)}。将牌型集合中的牌型依照表1进行标签转化，得到标注{0，222222，00000，0，11，33}，因此该手牌序列的标注信息为“02222220000001133”。

2.2 基于BILSTM-CRF的拆牌模型设计

基于BILSTM-CRF的拆牌模型网络结构如图1所示。首先将每一张牌进行向量赋值，并输入到BI-LSTM网络中，通过全连接层网络输出包含四种标注类型的分数。然后建立CRF状态转移矩阵，用CRF层去训练牌与牌之间标注类型状态转移关系，最后将BI-LSTM网络对标注的打分，和CRF层对标注的打分进行求和，并选取总得分最高的标注类型作为当前手牌的标注类型。

图1 BILSTM-CRF模型网络结构框图

因手牌序列标注，需要考虑到每张手牌与其他手牌前后之间的关系，故选用BILSTM-CRF网络，对手牌以单张手牌为单位进行向量读取，BI-LSTM层的输出连接到全连接输出层，输出维度为4，即对4种标注牌型的打分。全连接输出层对每一张牌属于4种牌型的分数进行输出。每张牌的对应的分数h表示为式(1)，其中k代表手牌序列中第k个位置的手牌，k=1,2,3,…,L,其中L为序列长度。

ek∈{hk1,hk2,hk3,hk4}

(1)

对于长度序列为L的初始手牌序列，共产生N=L4种标注情况。每种标注情况在手牌序列中的总得分如式(2)所示，n=1,2,3…N,表示每种情况下的标注结果。

(2)

BI-LSTM层输出的结果在归一化后产生的预测结果并不能保证对于手牌的给出的标签完全符合拆牌的规范，因而在模型中添加CRF层。在CRF层里，建立一个随机初始化的状态转移矩阵，矩阵的规格为6*6。状态转移矩阵的横纵坐标都表示为start状态、4种牌型、end状态。根据6种状态和长度为L的手牌序列，建立长度为L+1的状态转移分数进行求和。状态转移序列求和表达式表示为式(3)。

Tn=mstart,1+m1,2+m2,3+…+mL-1,L+mL,end

(3)

CRF单个状态转移分数mij表示为式(4)。

(4)

CRF状态转移矩阵的含义是：对于横轴第i个状态和纵轴第j个状态，从第i个状态转移到第j个状态(在手牌序列中从前一张牌标注牌型结果的状态，转移到后一张牌标注牌型结果的状态)的分数表示。CRF状态转移矩阵在随机初始化后，其数值会随着训练的进行通过梯度下降更新。

网络模型对N种标注情况下每种情况的得分表示为BI-LSTM层和CRF层在该种情况下对应的分数之和并取e的指数幂：

Pn=exp(En+Tn)

(5)

统计所有N种情况下Pn之和作为分母，将来自于训练数据中真实存在的标注示例(即理想状态下的标注结果)下计算得到的Pn作为分子Prealpath。损失函数取两者的对数损失函数，如式(6)所示。

(6)

式(6)中，目标函数的更新趋势是尽可能使分子所对应的目标分数增大，可以视为极小化对数损失函数。

3 实验与分析

训练环境的服务器配置为Windows 10操作系统；NVIDIA GeForce GTX 2070super显卡，8GB显存；pytorch版本1.4.0。数据为联众公司提供，共430万条，其中有290万局地主获胜，140万局农民获胜。在训练前，从地主数据集和农民数据集中共划分出2 000条作为测试集数据使用。对于模型的准确率计算，以测试集上每张手牌的来自模型输出的标注结果和来自原始数据的标注结果的符合比例作为检验模型训练效果的标准。

3.1 二打一手牌拆分

用于训练的每条数据的信息如表2所示。

表2 单条数据信息

表2展示了每条完整牌局所提供的有效信息，包括三方玩家的初始手牌、3张底牌以及从玩家0开始到玩家2结束的完整打牌过程。打牌过程是以先手玩家0作为地主，最后一名出牌玩家2是获胜方(最先将所有手牌全部打出)。提取获胜方玩家2在牌局中所打出过的完整手牌{3AAA，68TTTJJJ，KK，22，9}，将带牌进行拆分{3，AAA，6，8，TTTJJJ，KK，22，9}。因此，根据表1的标注序号分类，将原手牌序列“3689TTTJJJKKAAA22”的拆分标注为“00002222221122211”

3.2 模型的训练效果

经过多次调参训练得到模型的最优结构，其超参数配置见表3。

表3 超参数配置

随着训练次数的增加，模型的准确率提升至89.16%，准确率随训练次数的变化如图2所示，可以看出，随着训练次数的增加，模型在测试集上的准确率逐渐提升。

图2 准确率随训练回合数的变化趋势

3.3 效果分析

模型训练完毕后，将需要进行拆分的手牌输入模型，产生标注结果，按照拆分标注表的示例将手牌按照标注结果划分成四类，每类结果进行牌型的合并，将连续至少5张的单牌组成单顺，将连续至少3组的对牌组成双顺，将连续至少2组的三张组成三顺。拆牌结果示例如表4所示。

表4中，当模型训练完毕时，将示例手牌以从大到小的方式输入到模型中，模型输出每张手牌对应的手牌标注类型序号。如手牌“X2AAQQQJJTT988774”对应的拆分标注结果为“0,0,1,1,2,2,2,1,1,1,1,0,1,1,1,1,0”和手牌“2AKKKQQ9998888555”对应的拆分标注结果为“0,0,2,2,2,1,1,2,2,2,3,3,3,3,2,2,2”。将标注好的手牌按照标注的4种类型进行归类。对于标注为0的类型的牌，判断是否能凑成顺子并合并；对于标注为1的类型的牌，先将单张手牌组成对牌，然后再判断是否能凑成连对并合并；对于标注为2的类型的牌，先将单张手牌组成三张，然后再判别是否能凑成三顺并合并；对于标注类型为4的牌，将火箭和炸弹直接进行拆分，得到单独拆分出的火箭和炸弹的牌型。从表3中的结果来看，BI-LSTM+CRF模型在对二打一初始手牌标注上产生了良好的效果。

表4 拆牌结果示例

为了评估BILSTM-CRF模型对于在拆牌上的可靠性，实验引入了基于文献[15]的传统手牌拆分方法的性能对比，该方法以最小拆分组合数为最终目标，其步骤为：

步骤1首先对牌型三张、炸弹、顺子、连对和三顺排列组合成不同优先级组合H1,H2,…,H40，其中，需要排除掉三张牌型优先级高于炸弹和三顺的情况，共计40种组合。建立一个空的集合。

步骤2依次遍历40种优先级组合，在每个优先级组合下，按照牌型的组合顺序中优先级的高低依次选择较高优先级的牌型对手牌进行拆分，从每一种优先级组合中产生若干组手牌拆分序列。

步骤3将第1组拆分序列插入集合中，并重复步骤2，依次循环直到遍历完40种优先级组合。从第2组开始，每新产生一组拆分结果，变计算该拆分结果的拆分数目，若该拆分数目小于集合中的最小拆分数目，则将该拆分结果加入集合中，直至优先级组合遍历完毕。

步骤4选取集合种拆分数目最小的拆分结果作为待拆分手牌的拆牌结果。

在430万对战数据的基础上，使用基于梯度提升树的XGBoost算法训练出二打一的出牌AI。随机生成1 000副初始手牌。对于每一副初始手牌，分别得到传统最小组合拆分法的拆分结果h={h1,h2,…,hi}和BILSTM-CRF模型的标注拆分结果g={g1,g2,…,gj}，并通过AI进行对打，统计对局中AI在前5次主动出牌(根据是否进行跟牌的状态分为主动出牌和被动出牌)下打出牌型(A1,A2,…,Aa,B1,B2,…,Bb,C1,C2,…,Cc)，其中ABC分别代表二打一对战中3个角色打出的牌型。分别统计AI打出的牌型中存在于集合h和集合g的比例Ph和Pg，性能结果如表5所示。

表5 性能结果

传统最小组合拆分法虽然能快速有效地产生手牌拆分结果，但是二打一的对局变化多端，拆分出的牌型并不能保证和对局中AI打出的牌型完全相符。而BILSTM-CRF模型的标注拆分法是基于人类玩家对局中的拆分结果进行拆分，该方法所产生的拆牌结果相比之下更能反映在实际玩家对战中对手牌的拆分结果。

4 结论

基于联众提供的真人二打一游戏对战数据构建了手牌拆分的真实数据集，数据规模达到了430万条，为后续拆牌研究提供了数据基础。提出基于BILSTM-CRF构建手牌序列标注模型，实验证明了该模型在手牌拆分任务上的有效性，表明了通过对二打一手牌进行序列标注实现模拟人类手牌拆分的可行性，拓宽了BILSTM-CRF模型的应用领域。