陈子鹏，李淑琴，郑蓝舟，孟 坤，丁 濛

（1.北京信息科技大学，北京 100010；2.感知与计算智能联合实验室，北京 100010；3.微智娱（北京）科技有限公司，北京 100010）

二打一是一种玩法简单、娱乐性强的三人扑克牌游戏［1］。一局牌需3个玩家，一个玩家称为地主，地主下家（逆时针第1个农民）称为农民1，地主上家（逆时针第2个农民）称为农民2。在每一局游戏中，地主独立存在，而其他2名玩家以农民的身份组成一队与地主对抗。地主、农民1、农民2依次出牌，3个人都进行了1次出牌定义为1个回合。地主的目标是以多种出牌组合方式首先打完自己的手牌；农民队伍只要有1人比地主先出完手牌便可获得游戏胜利，并计算本局小分。

2016年9月3 日，中国国家体育总局举办了首届全国竞技二打一扑克锦标赛（China competitive poker championship，CCPC）［2］，目前已举办了2届。赛事沿用大师分系统［3-5］和复式赛制［1］，采取瑞士移位竞赛办法［3-5］和去纸牌化的桌面裁判员管理办法，力求比赛公正与公平。首届全国竞技二打一扑克锦标赛历经近1年时间，先进行全国大师分排行榜排名赛，再由全国大师分排行榜前2016名进行全国公开赛，最后选出108名选手进行全国锦标赛，这些选手经过为期2天紧张刺激的18轮比拼，最终决出本届赛事的冠、亚、季军。竞技二打一比赛存在赛制冗长的问题，如果比赛所发初始手牌对选手的区分能力较强，则能够以更少的轮数确保选手获取唯一称号。因此，对能够区分二打一游戏竞技者能力初始手牌的选取进行研究。

1 系统设计思想

一般将竞技选拔试题对被试者情况分辨能力的大小称为区分度［6］，主要用于评价以选拔为目的的选题。目前用于区分度分析的方法主要有经典测量理论［7-10］（classical test theory，CTT）和项目反映理论［11-13］（item response theory，IRT）。CTT以区分度选择合格题目的过程需要经过统计考生得分、建立模型计算区分度、根据区分度选取合格的题目，通常的关注点是所有考生。然而竞技二打一锦标赛以选拔高水平竞技者为目的，需要确保排名靠前的竞技者能够获得唯一的称号和奖励，因此CTT中常用的区分度评估模型不适用于解决竞技二打一锦标赛的相关问题。本文中借鉴CTT框架提出选取合格的题目的步骤，其中创造性地提出了初始手牌的区分度（distinction of initial hand，DIH）的概念和算法，对区分二打一游戏竞技者能力的测试用例进行研究。

定义1初始手牌

在出牌阶段之前，3家（地主、农民1、农民2）分别持有的每1张扑克单牌的组合为初始手牌。

定义2测试用例

将经过区分度筛选的多个初始手牌称为区分二打一游戏竞技者能力的测试用例。

对于区分二打一游戏竞技者能力的测试用例的研究主要分两大方面，即根据二打一真实用户打牌的行为数据，如何进行测试用例的选取，然后测试用例的可信度。

1.1 测试用例选取方法的研究

测试用例的选取思想：首先对大量真实用户打牌行为数据进行分析及处理，计算每个初始手牌对应的得分概率分布；针对每副初始手牌，在比赛每轮使用与该初始手牌有着相同得分概率分布的初始手牌的条件下，计算此比赛最终的得分概率分布。基于此概率分布、比赛参赛人数、预先确定的比赛轮数、比赛需要确保选手获取唯一奖励的人数计算区分度，并进行非降序排序；选取区分度高对应的初始手牌作为测试用例。

1.1.1 初始手牌对应得分概率分布的计算

真实二打一用户打牌行为数据有地主、农民1、农民2所持所有单牌组成的初始手牌信息，以及地主的得分。这些数据杂乱、无规律，本文中通过分析，计算初始手牌得分概率分布来得到初始手牌与得分之间关系。

使用的竞技二打一的计分规则是胜负系数×加倍系数。当进攻方胜利，胜负系数为1，失败，胜负系数为-1。加倍系数为n，n值为本副牌中打出的火箭数+炸弹数。火箭是双王（大王和小王），炸弹是4张点数相同的牌。因此，得分分数所构成的集合为｛-n，…，-2，-1，0，1，2，…，n｝。

初始手牌的表示分为3个部分，每个部分放在一组中括号内，第1个中括号内为地主手牌，第2个和第3个中括号内为2个农民的手牌。例如“［TTKA379Q2D69K5Q94J6］［3JX8Q885TTK3265AK］［29Q435J426787JA7A］”，每个字符代表1张单牌，其中T代表单牌“10”，X代表单牌“小王”，D代表单牌“大王”。

对于牌库（C1，C2，…，Cb），b为牌库的初始手牌的数量，针对每副初始手牌Ci，其潜在的所有得分即潜在得分的分布Si＝（Si1，Si2，…，Sih），h为所有潜在得分分数的数量。进行y轮对局，每轮的对局得分Sij对应的出现次数cij加1，每个潜在得分出现的次数被记录（ci1，ci2，…，cih），计算在不同分数上的得分概率Di＝（Pi1，Pi2，…，Pih），Di即初始手牌Ci的得分概率分布，其中

1.1.2 初始手牌区分度的计算

计算区分度的目的是选取初始手牌组成测试用例，以降低排名靠前的若干名选手分数重复的概率，针对竞技二打一竞赛的问题，对区分度有如下定义。

定义3初始手牌的区分度（distinction of initial hand，DIH）n人参赛，经过m轮比赛，保证前r名选手的得分不重复的概率。即希望前r名选手在锦标赛中获取不同的分数。

对于牌库（C1，C2，…，Cb），b为牌库的初始手牌的数量，针对每副初始手牌Ci，假设其每轮比赛的得分概率分布都为Di＝（Pi1，Pi2，…，Pih），计算m轮比赛结束后的潜在得分的分布对应的不同分数上的得分概率，k为m轮比赛后所有潜在得分分数的数量。

下面通过1个例子进行详细说明。例如，比赛共有玩家9人，即n＝9。比赛轮数2轮，即m＝2。比赛需要确保获取唯一奖励的数量r为2。若此比赛所分发牌的初始手牌得分概率分布如表1所示，即潜在得分的分布S＝（-2，-1，1，2），计算其对应的得分概率分布P＝（0，0.6，0.4，0），对于此次比赛该初始手牌的区分度计算步骤如下。

表1 某初始手牌的得分概率分布

假设2轮比赛完全独立，则比赛结束后的潜在得分的分布为S（2）＝（-4，-3，-2，-1，0，1，2，3，4），统计比赛结束后的得分概率分布P（2），如表2所示，P（2）＝（0，0，0.16，0，0.48，0，0.36，0，0）。依次计算第1名获得-2，-1，0，1，2，3，4分的情况，即公式中共需要累加项数k＝7。当第1名获得4分时，第2名得分的取值情况是-4＜M2＜4，M2共有7种取值，即集合M共有7个元素，因此区分度的第1层累加和的第1项如式（3）所示。按上述步骤在计算剩余的6项，区分度结果为0.358。表明初始手牌的区分度比较低，不能用来比赛。

表2 2轮比赛结束后此初始手牌的得分概率分布

1.1.3 测试用例的选取

选取测试用例的目的是应用于实际比赛中，以降低赛程所耗费的时间。选取测试用例的方法是根据拟定的比赛轮数、参赛人数和唯一奖励的个数，计算各初始手牌的区分度，并进行非降序排序；选取区分度高对应的初始手牌作为测试用例，初始手牌的数量与比赛轮数相同。测试用例的选取算法的伪代码如下：

其中，append（）函数是在列表的最后添加新的元素，sorted（）函数为列表进行排序，len（）获取列表的长度。

1.2 测试用例的验证

检验测试用例的设计思想：指定若干名比赛状态稳定，并有区分度的选手，进行玩家固定成为某一角色的方式的比赛。固定比赛轮数，即比赛共有m轮，先给选手按随机分发初始手牌进行比赛。每轮比赛统计选手得分，第d轮比赛的选手得分记为（Sd，1，Sd，2，…，Sd，n），n是选手的人数，根据（Sd，1，Sd，2，…，Sd，n）为选手进行排名，每人的名次记为（Od，1，Od，2，…，Od，n），Od，i∈（1，2，…，n）。同时，若从第y名开始在有k个人得分相同，此k个人的排名都记为y+1，且第y+k名选手的名次记为y+k即 （Od，y-1，Od，y，Od，y+1，…，Od，y+k-1，Od，y+k）＝（y，y+1，y+1，…，y+1，y+k）。根据排名为每位选手对第d轮比赛进行积分，即选手的排名分（Rd，1，Rd，2，…，Rd，n），Rd，i＝2×（n-Od，i+1），并统计每个选手的m轮比赛结束的总排名分只要不同选手的总排名分不相等，选手就是可区分的。上述的比赛共举办w场，计算排名前r个选手可区分的概率，记为P1。再按用测试用例分发初始手牌进行比赛，比赛共举办w场，同样计算排名前r个选手可区分的概率，记为P2。比较P1与P2值的大小，如果P2比P1值大，就说明测试用例是可信、实用的。

如何选取“比赛状态稳定且据有区分度的选手”是难点。因为真人选手比赛时间一长就不能保证其比赛状态的稳定性。另外，选手的区分度需要通过上百甚至千场的线上对局才能评估，因此，找真人做实验不太现实。为此，本文中提出通过具有区分度的多个“斗地主AI程序”来代替真人选手进行实验的方案。

笔者所在研究团队曾针对地主、农民1、农民2分别开发了多款斗地主AI程序。他们没有考虑叫分功能，通过人类打牌日志基于CNN模型训练出牌策略，能够达到著名竞技二打一牌手的水平，相关的具体信息参见文献［14-16］。

算法1获取具有区分度的“AI打牌组合选手”

输入：a个地主的“斗地主AI程序”，（l1，l2，…，la）；

b个农民1的“斗地主AI程序”，（f11，f12，…，f1b）；

d个农民2的“斗地主AI程序”，（f21，f22，…，f2d）；

比赛拟定的参赛人数，u。

输出：具有区分度的多个“AI打牌组合选手”。

步骤1通过地主、农民1、农民2的交叉组合，获得若干由1个地主、1个农民1和1个农民2组成的“AI打牌组合选手”，（G1，G2，…，Ga×b×d），Gi＝（li，f1i，f2i），共计a×b×d组。

步骤2随机生成m副初始手牌（H1，H2，…，Hm），随机初始手牌的生成见算法3。

步骤3i＝1，即选取第1副初始手牌H1

步骤4每个“AI打牌组合选手”打完这副牌Hi；统计当前轮比赛“AI打牌组合选手”的地主的得分，并计算当前“AI打牌组合选手”的地主的总得分。

步骤5i＝i+1；

步骤6if i＞m then跳转至步骤4，否则跳转至步骤7。

步骤7统计打完m副初始手牌的每个“AI打牌组合选手”的地主的总得分（T1，T2，…，Ta×b×d）进行排序，记录其最大值Tmax和最小值Tmin。计算每个组（G1，G2，…，Ga×b×d）的得分率（P1，P2，…，Pa×b×d），即

步骤8以（P1，P2，…，Pn）的最大值1和最小值0划分区间，将［0，1］的区间均分为w个（I1，I2，…，Iw），Ii＝（（i-1）×（1／w），i×（1／w））。w为将指定的测试AI的数量。

步骤9得分率落在同一个区间“打牌组合选手”被分到同一个集合中（C1，C2，…，Cw）。

步骤10随机从每个集合中挑选1个“AI打牌组合选手”，组成1组具有区分度的测试者。

初始手牌的生成算法如下所示：

算法2随机生成初始手牌。

输入：54张扑克单牌。

输出：3家（地主、农民1、农民2）的初始手牌。

步骤1对54张扑克单牌进行洗牌，获得被打乱顺序的54张扑克单牌的列表（c1，c2，…，c54）。

步骤2i＝1，即取单牌c1。

步骤3当i mod 3＝1即i除以3所得余数是1时，分发给地主，当i mod 3＝2时，分发给农民1，当i mod 3＝0时，分发给农民2。

步骤4i＝i+1

步骤5if i＜52 then转至步骤3，否则跳转至步骤6。

步骤6剩余的3张扑克单牌（c52，c53，c54）归地主所有。

2 系统实现

使用Intel Xeon E5-2640 CPU，NVIDIA 1080Ti GPU和Ubuntu 16.04服务器系统的服务器。

2.1 生成初始手牌库及生成测试用例

首先建立初始手牌库，并从初始手牌库中选取初始手牌组成测试用例。竞技二打一游戏平台提供了500万条游戏日志，统计每副初始手牌所出现的次数，为了使初始手牌得分数据更加真实，所以本文中只考虑打牌次数大于50次的初始手牌，共有1 925副。1 925副初始手牌在单次对局中打出的火箭数+炸弹数的上限为6，因此，初始手牌的得分分布将被表示为（-6，-5，-4，-3，-2，-1，1，2，3，4，5，6）。

先根据式（1）计算1 925副每个初始手牌的得分分布。再根据算法1，通过初始手牌区分度的式（2）计算每副初始手牌的DIH，对初始手牌按DIH进行非递减排序，依据比赛轮数选取靠前的若干副初始手牌即测试用例。

例如，对于比赛人数为8，比赛轮数为4，唯一奖励数为2的比赛，选取出的测试用例如表3所示。

表3 比赛人数为8，比赛轮数为4，唯一奖励数为2的比赛的测试用例

2.2 验证测试用例的可信性

利用已有的斗地主3个角色的出牌模型，分别训练了9个地主、7个农民1和7个农民2 AI玩家。使用算法3随机生成了4 000副初始手牌。通过9个地主、7个农民1和7个农民2的交叉组合，共拥有9×7×7＝441个“AI打牌组合选手”。

由于竞技二打一的冠军称号最为重要且唯一，固定唯一奖励的个数为1，替换参赛人数n和比赛的轮数m，对给选手按随机分发初始手牌进行的比赛和按用测试用例分发初始手牌进行的比赛分别模拟了多场，在参数不同的比赛中，选取测试用例所用的DIH相应的参数也随之改变，从而对测试用例进行验证，同时分析DIH的参数间的关系。对于同一种比赛，共模拟1 000次，每次模拟依据拟比赛人数n通过算法2选取具有区分度的“打牌组合选手”。多种比赛的不重复概率见表4，表序中r是唯一奖励个数；n为参赛人数；m为比赛人数；P1是给选手按随机分发初始手牌进行比赛，在m轮比赛结束后，前r名参赛选手比分不重复的概率；P2是按用测试用例分发初始手牌进行比赛，在m轮比赛结束后，前r名参赛选手比分不重复的概率；（P2-P1）／P1是P2相对于P1的提升比率。

表4 测试用例的可信度的验证

通过实验结果发现：

1）当m相对于n很小时，如m＝2，r＝1，n＝30时，选牌的随机性很大，同时选取的测试用例稳定，结果的提升率为346.75%，因此，表明了测试用例选取方法的有效性。

2）接下来通过结果对参数之间的关系进行分析，以n＝30，r＝1为例对按用测试用例分发初始手牌进行比赛不重复的概率，提升比率与m的关系进行分析。当m增加时，不重复的概率增加，但是P2相对于P1的提升率在降低即使用测试用例的有效性降低，因此选择一个适中的m是最佳的选择。

3）固定r＝1和m＝5，分析n和实验结果的关系。当n＝10时，P1相对于P2的提升率为25.24%，当n＝20时，P1相对于P2的提升率为49%，当n＝30时，P1相对于P2的提升率为76.79%，P1相对于P2的提升率随着n的增加而增加。即当参赛人数增加时，测试用例的有效性增加。

综上，不论比赛的相关参数，按用测试用例分发初始手牌进行比赛的不重复概率都高于给选手按随机分发初始手牌进行比赛的不重复的概率，因此选取测试用例的方法是有效的，可以用来解决比赛赛程过长的问题。

3 结论

提出通过给出具有较高区分度的初始手牌用于比赛发牌阶段，以减少比赛轮次的解决方案，并提出初始手牌区分度的算法。为验证测试选取用例的有效性，提出采用多个具有不同区分度的“AI打牌组合选手”进行模拟比赛。实验结果表明测试用例的选取方法是有效的。但是初始手牌区分度的算法的时间复杂度和比赛唯一奖励的个数呈指数级增长，因此不适用于大型比赛计算，算法需要进一步优化。另外，区分度的参赛人数与比赛轮数、获奖人数等存在一定关系，在接下来的工作中还需要对三者具体关系进行研究。