二打一游戏残局模式下的对弈策略研究

郭荣城，李淑琴，龚元函，黄韶华，衡 鑫

（北京信息科技大学 计算机学院，北京 100101）

0 引 言

计算机博弈作为人工智能的重要发展方向之一，被称为是人工智能学科的“果蝇”。二打一智力游戏（也称“斗地主”）是一种玩法简单、娱乐性强的扑克游戏。经典的玩法是扑克牌一共54张，斗地主智力游戏需由3个玩家进行，每人首先有17张手牌，底牌有3张。其中一名玩家根据手牌选择要底牌，该玩家成为地主，其余2名玩家则为农民。以某一玩家率先出尽手中牌来结束牌局判定胜负。

随着斗地主智力游戏作为应用软件在各类电子平台的日渐普及，游戏运营平台逐渐对游戏玩法进行拓展，除经典玩法外又陆续推出了多样化的各种玩法，如残局玩法、癞子玩法、换三张挑战赛等，这些玩法基于斗地主智力游戏的基础规则衍生出其他新的规则或针对传统牌局的局部进行独立，其中“残局玩法”（如图1）便是其中的一个代表。

图1 一残局模式开局Fig.1 One endgame start

“残局玩法”的规则为：牌局中有2个角色：一位地主和一位农民，双方分别有部分手牌（张数不固定），玩家将固定当地主首先出牌，农民方为运营平台的智能AI，双方均为明牌，整个牌局至少存在一种地主胜利的解法，玩家需要尝试赢下牌局，出牌规则与经典玩法一致。

二打一智力游戏作为一种经典的博弈类游戏，受到机器博弈领域的广泛研究与关注，由于这是一种非完全信息类游戏，每个玩家看到的信息是不对称的，就使得玩家只能靠“猜”来做决策，增加了很多变数，并且二打一智力游戏中合作与竞争并存的设定，空间动作的巨大使得自身与其他机器博弈类游戏有很大差距，研究可知针对围棋的著名AI算法AlphaZero中的算法MCTS就无法直接应用在二打一中。所以二打一的AI算法很多都采用了蒙特卡洛、深度学习、神经网络等，例如2021年快手推出的DouZero作为一匹黑马击败344个AI登顶二打一AI排行榜便是应用了蒙特卡洛、深度神经网络、动作编码等技术。

而二打一残局模式相较于经典二打一模式，针对于少量手牌将局面做了很大程度简化，由三人非完全信息博弈转变为双人完全信息博弈，残局模式旨在锻炼玩家对拆牌压牌的理解，以达到在普通玩法中合理运用己方手牌达到“以弱胜强”的效果。本文拟采用基于Alpha-Beta剪枝的方法，对二打一残局模式进行研究。

1 二打一游戏残局对弈策略设计与实现

本文二打一游戏残局对弈整体策略由手牌拆分、招法过滤和招法应对三个主要部分组成。

1.1 手牌拆分的设计与实现

本文首先将二打一中手牌定义为火箭、炸弹、单牌、对子、三张、三带一、三带二、单顺、连对、飞机、三带一飞机、三带二飞机、四带二和四带两对，总共14种牌型。由二打一游戏对弈规则，火箭最大，可以打任意其他的牌。炸弹比火箭小，比其他牌大，都是炸弹时按牌的分值比大小。除火箭和炸弹外，其他牌必须要牌型相同且总张数相同才能比大小。对牌、三张牌都按分值比大小。单顺牌按最大的一张牌的分值来比大小。单牌按分值比大小，依次是：大王＞小王＞2＞A＞K＞Q＞J＞10＞9＞8＞7＞6＞5＞4＞3，不分花色。为此，本文根据对弈规则为每种牌型赋予了牌型内分值和牌型价。其中，牌型内分值指各牌型中的招法之间存在分值大小关系。牌型价值是指除炸弹与火箭外所有牌型价值为0，炸弹价值为1，火箭价值为2。具体见表1。

表1 牌型定义及分值表Tab.1 Card type definition and score table

手牌拆分就是当轮到己方出牌时将手牌进行循环遍历，将手牌依据表1中的牌型组合出所有对应的招法，招法指根据14种牌型组出的具体手牌组合。然后将招法分别存入到对应的牌型中，并根据牌型类型与点数大小赋予对应的分值。程序针对图1返回的己方所有可行招法的实际演示见图2，共有11种组合招法。

图2 针对图1的己方所有招法Fig.2 All the moves against Fig.1 in self side

1.2 招法过滤设计与实现

拆分好手牌后进行招法过滤，招法过滤分2种情况：

（1）当牌局开始或对方Pass轮到己方出牌时，遍历存储己方招法的，按表1中牌型顺序返回当前手牌可组成的所有招法。

（2）当对方出牌后，将对方的招法与14种牌型做对比，判断对手招法是14种牌型类型的哪一种，依据前文中提到的招法价值大小关系将对方招法与己方所有招法进行牌型内分值与牌型价值比较，返回所有牌型内分值或牌型价值大于对方招法的己方招法。

1.3 招法应对设计与实现

招法应对对应招法过滤也分2种情况：

（1）当牌局开始或对方Pass轮到己方出牌时，招法选择分值为100的招式作为出牌策略。

（2）当对方出牌后、己方跟牌时，从招法过滤获取到己方所有可组成的招法中，通过Alpha-Beta剪枝算法，选择出一种必胜的出牌策略。Alpha-Beta剪枝搜索大体可以分为3个步骤：局面标定、传递倒推、剪枝。3个步骤依次进行，最终获取到一条最优路径，即选出最佳出牌策略。

1.3.1 深度搜索局面标定

Alpha-Beta剪枝搜索经常用于计算机零和博弈游戏中。在建立博弈树的过程中，地主状态层，农民状态层交替建立，两者博弈树关系如图3所示。图3中，方形代表地主，圆形代表农民。由于斗地主残局模式属于双人完备信息游戏，所以获得胜利的决策近乎唯一。在这种情况下进行Alpha-Beta剪枝搜索，可以找出最佳出牌路径，通过搜索到底得到精确的输赢反馈值，从而对局面进行标定。

图3 完全搜索倒推的预计结果Fig.3 Expected results of full search backwards

深度搜索局面标定法步骤如下：

（1）将双方剩余手牌作为当前局面。

（2）对当前局面执行Alpha-Beta深度搜索，每执行一步为一节点。

（3）每走一步便进行手牌拆分，并将新拆分出的招法作为下一步的分支。

（4）将一条分支延伸到一方手牌出尽，若地主胜利则将当前局面值标定为100，若农民胜利则将当前局面值标定为0。

1.3.2 向上传递

（1）在偶数层节点的招法、即轮到农民出牌的节点时，农民应考虑最好的情况，选择其全部子节点中评估值最大的一个，即：

其中，（·）为节点估值，，，…，v为节点的子节点。

（2）在奇数层节点的招法、即轮到地主出牌的节点时，地主应考虑最坏的情況，选择其全部子节点中评估值最小的一个，即：

其中，（·）为节点估值，，，…，v为节点的子节点。

（3）评价往回倒推时，相当于2个局中人的对抗策略，交替使用（1）、（2）两种方法传递倒推值。具体实例参见图3。

1.3.3 Alpha-Beta剪枝

本程序中Alpha-Beta剪枝与普通的Alpha-Beta剪枝算法稍有不同，由于局面标定中只会出现0和100两个值，分别代表农民胜利和地主胜利，所以当min层中出现0，便意味着此条分支的父节点所选择的招法已无法获得地主胜利的情况，所以当前父节点还未搜索的分支已无搜索的必要，即减去后续未搜索的分支。max层中出现100时与之同理。

剪枝实例如图4所示。图4中，①处分支为min层，由于遍历搜索已经搜索到了值为100的分支，所以①分支便停止搜索即被剪枝，②处同理，③、④分支处于max层，由于已搜索到了值为0的分支，所以③、④分支被剪枝，但由于已搜索到一条分值为100的树，程序已经停止搜索，故实际上③、④所处子树并未被搜索。

图4 剪枝实例Fig.4 Pruning example

上述算法的实现流程如图5所示。图5中，为min层值，为max层值。

图5 算法流程图Fig.5 Algorithm flowchart

2 实验结果与分析

本文通过微信平台小程序“欢乐斗地主”中的残局闯关模式对算法程序进行测试，以下为其中一残局的完整对弈局，并将己方出牌执行情况附在图的右侧。

己方出牌为［‘4’］时的牌局如图6所示，将残局双方手牌导入进程序，第一步为己方出牌，根据双方手牌运行Alpha-Beta剪枝程序，通过多线程搜索分别基于不同出牌方式构建多个博弈树，由图6可见，当前手牌程序返回了11种出牌方式，即基于这11种出牌方式构建11棵博弈树，由图6可见程序依次返回基于出牌方式［‘k’，’k’，’k’］、［‘8’］、［‘6’］、［‘7’］、［‘K’］所构建的博弈树的返回值为0，即这些出牌方式己方无法胜利，继续返回基于出牌方式［‘4’］所构建的博弈树，返回值为100，即此种出牌方式己方必胜，搜索到必胜的出牌方法后停止对其余出牌方式的博弈树的构建，但考虑到搜索为多线程进行，在发出停止命令之前其他线程又返回了基于出牌方式［‘Q’］、［‘6’，’6’］、［‘7’，’7’］、［‘8’，’8’］、［‘2’］所构建的博弈树，由于已经搜索到必胜的出牌方式［‘4’］，所以下一步的手牌出法为［‘4’］。

对方出Q，如图7所示。

当前本文程序返回了3种出牌方式，即基于这3种出牌方式构建3棵博弈树，由图6、图7可见程序首先返回基于出牌方式［‘K’］所构建的博弈树，返回值为100，即此种出牌方式己方必胜，搜索到必胜的出牌方法后停止对其余出牌方式的博弈树的构建，但也考虑到搜索为多线程进行，在发出停止命令之前其他线程又返回了基于出牌方式［‘2’］所构建的博弈树，由于已经搜索到必胜的出牌方式［‘K’］，所以下一步的手牌出法为［‘K’］。己方出牌为［‘K’］时的牌局如图8所示。

图6 己方出牌为［‘4’］Fig.6 The card of the self side is［‘4’］

图7 对方出牌为［‘Q’］Fig.7 The card of the opponent side is［‘Q’］

图8 己方出牌为［‘K’］Fig.8 The card of the self side is［‘K’］

对方出［‘2’］，如图9所示。

图9 对方出牌为［‘2’］Fig.9 The card of the opponent side is［‘2’］

对方出牌为［‘2’］，己方无可出牌型，即只有一种手牌出法：“pass”。如图10所示。

图10 己方passFig.10 The self is pass

对方出“334455”，如图11所示。

己方当前手牌程序返回了2种出牌方式，即基于这2种出牌方式构建2棵博弈树，由图11可见程序首先返回基于出牌方式［‘6’‘6’‘7’‘7’‘8’‘8’］所构建的博弈树，返回值为100，即此种出牌方式己方必胜，搜索到必胜的出牌方法后停止对其余出牌方式的博弈树的构建，但由于搜索为多线程进行看，在发出停止命令之前其他线程又返回了基于出牌方式pass所构建的博弈树，由于已经搜索到必胜的出牌方式［‘6’‘6’‘7’‘7’‘8’‘8’］，所以下一步的手牌出法为［‘6’‘6’‘7’‘7’‘8’‘8’］。如图12所示。

图11 对方出牌为［‘3’‘3’‘4’‘4’‘5’‘5’］Fig.11 The opponent′s card is［‘3’‘3’‘4’‘4’‘5’‘5’］

图12 己方出牌为［‘6’‘6’‘7’‘7’‘8’‘8’］Fig.12 The card of the self side is［‘6’‘6’‘7’‘7’‘8’‘8’］

对方出“pass”，如图13所示。

图13 对方passFig.13 The opponent is pass

己方当前手牌程序返回了2种出牌方式，即基于这2种出牌方式构建2棵博弈树，由图可见程序首先返回基于出牌方式［‘2’］所构建的博弈树，返回值为100，即此种出牌方式己方必胜，搜索到必胜的出牌方法后停止对其余出牌方式的博弈树的构建，下一步的手牌出法为［‘2’］。如图14所示。

图14 己方出牌为［‘2’］Fig.14 The card of the self side is［‘2’］

对方继续“pass”，如图15所示。

图15 对方passFig.15 The opponent is pass

己方只剩一张牌［‘Q’］，下一步的手牌出法为［‘Q’］，手牌出完，游戏胜利。如图16和图17所示。

图16 己方出牌为［‘Q’］Fig.16 The card of the self side is［‘Q’］

图17 游戏胜利Fig.17 Game victory

本文通过微信端欢乐斗地主小程序中的餐具闯关模式对程序进行实际测试，共进行了140关残局闯关测试，均成功取得胜利，实验结果如图18所示。

图18 残局闯关通过关数截图Fig.18 Screenshot of the number of passes through the endgame

3 结束语

在斗地主游戏中，残局策略非常关键，对博弈胜负有着至关重要的作用。本文基于Alpha-Beta剪枝算法对斗地主残局模式出牌策略展开了研究分析，提出了一种新的残局策略，并加以实现，在与双人明牌斗地主残局中有着较好的表现。在接下来的工作中还需进一步提炼判定手牌优劣的因子加入完善算法，有利于后续研究的深入开展。