基于BDI推理模型的麻将游戏机器人设计

徐玉朋+朱明富

摘 要：在分析麻将游戏基本规则的基础上，引入BDI推理模型，构建了一种麻将游戏机器人结构，介绍了对机器人信念、愿望、目标等元素的实现，并提出一种游戏中机器人的使用策略，为不同规则的麻将游戏机器人开发提供参考。

关键词：BDI推理模型；麻将；游戏机器人

DOIDOI：10.11907/rjdk.171235

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2017）007-0090-03

0 引言

麻将游戏深受人们喜爱，网络载体的麻将游戏有着广泛的群众基础，设计能够与玩家互动的麻将游戏机器人具有广阔的应用前景。作为真实玩家的对手，机器人的表现直接影响着游戏的趣味性，由于机器人是计算机操控的角色，开发人员可以为机器人赋予真人玩家没有的能力，例如获取别的玩家手中牌的信息。受商业元素影响，为了缩短产品开发周期，这种作弊手段在现有网络麻将游戏开发中常常用到。该开发方法有一定优势，但与真实世界的脱离会降低玩家对游戏的认同感，进而影响市场占有率，故不可取。BDI模型已经被证实符合正常人的推理思维，因此，设计基于BDI推理模型的麻将游戏机器人是很好的选择。

1 BDI推理模型

20世纪80年代，M E Bratman[1]在斯坦福大学的理性Agent项目研究中提出了信念—愿望—意图（Belief-Desire-Intention，BDI）模型。在Bratman工作的基础上，Cohen和Levesque[2]构建了基于正规模态逻辑的BDI模型，而Rao和Georgeff[3]则采用计算树逻辑对BDI模型的组成与推理作了更详细的刻画。BDI模型结构是慎思型Agent的主要结构，信念、愿望、意图是Agent的3种心智状态。信念是Agent对世界的认知，代表着对获得信息的一种评价；愿望是Agent希望达到的一种事件状态，是Agent的一些可选目标集合，并且这些目标可以是相互冲突的；意图是Agent当前想要达到的工作状态，可以是愿望中的一个。BDI推理过程如图1 所示。

目前，关于BDI推理模型的研究方法主要有两种，一是基于逻辑系统对BDI推理模型的研究和扩展[4]，二是从应用角度利用BDI推理模型进行仿真研究[5]和实用系统开发[6]。仿真研究多借助于现有成熟的仿真平台，如Netlog、Jade、Jack等，实用系统的开发多基于现有的开发平台，如Microsoft Agent。

BDI模型符合正常人的思维过程，但BDI模型只提供一个抽象的模式化结构，在具体应用中如何将BDI推理模型中抽象的组成实例化是开发工作人员面临的问题，麻将游戏机器人的设计也不例外。

2 麻将游戏机器人建模

2.1 麻将游戏基本规则

各地的麻将游戏融合了当地人的智慧，规则略显不同，但具有通用的麻将游戏基本规则。麻将按花色分为条万筒3种序数牌、东西南北4种风字牌，以及中发白3种箭牌。每种序数牌由1到9组成，共27种，每种牌有4张，整副牌共（3*9+4+3）*4=136张。玩家共有4人，开局后每个玩家分发13张牌。从庄家开始，获得牌权的玩家做动作，获得牌权的方式有顺序获取、碰、吃、杠4种。获得牌权的玩家如果手中牌的数目除以3余1，则先从牌堆中取出一张，然后出牌，直至赢牌或者牌堆剩余数目低于约定数目（一般为1）。

赢牌牌型必须符合m*AAA+n*ABC+DD的形式，其中m、n可以为0 。玩家游戏的过程可以描述为通过不断替换手中的牌，直至达到赢牌状态。

麻将游戏是棋牌类游戏的代表，棋牌游戏具有离散事件、动态系统的特点，其状态变化均发生在离散的时间点[7]。麻将游戏的参与者都要遵守游戏规则，机器人也不例外，故机器人的行为是受限的，其做出的每一个行为都要包含于有限的可选动作集中。

2.2 机器人结构建模

图2为根据BDI推理模型构建的机器人结构，感知器捕获触发此机器人的消息，并更新记忆库和行为集；状态集存储机器人对当前牌局的认识，是形成目标的依据；记忆库表示机器人对已经发生的事件的记忆，包含自己手中牌、玩家已出牌、不确定牌，其中不确定牌可能在牌堆中，也可能在别的玩家手中；规则库则存储牌局规则，如赢牌的判断方法；行为集中为当前机器人可以执行的行为提示，如吃牌、杠牌、出牌，机器人的行为必须从行为集中选择；更新器负责根据当前状态集、记忆库以及规则更新目标集和状态集。目标为Agent可以达到的某种理想状态，目标集中有多个目标，每个目标的实现难度不同，有的永远不能实现。筛选器对目标集进行筛选，得到一个或一组具有共性的目标；分解器根据策略进行目标分解，得到诸多可一步达到的状态，存入意图集；最后匹配器将行为集中的行为与意图集中的意图相匹配，做出可执行的动作交由执行器执行。在该结构中，规则库、记忆库、行为集、状态集和策略库共同构成机器人的信念。

3 机器人实现

3.1 麻将值表示

麻将牌值用一个字节表示，高4位表示花色，其中0-万，1-条，2-筒，3-箭或风，低4位表示牌值，序数牌低4位值大小即为牌值大小。若花色值为3，则牌值1～7依次表示为东南西北中发白。

3.2 狀态集

对于相同花色的一个牌的序列，可以通过将其中的一些牌剔除并增加一些牌的方式，使该序列能够组成m*AAA+n*ABC的完整形式。剔除牌的张数和需要获得牌的张数组成了p=（m，n）的形式，可以称之为出取对。其中m为出数，表示剔除牌的张数；n为取数，表示需要取得牌的张数。

玩家手中牌最多有4种花色，将每种花色牌的状态用如下五元组表示：

其中，A为该花色牌组成的序列。在赢牌状态下，可以将玩家手中牌的花色按是否是对子的花色分为两类；Ar为当不把该花色作为对子花色时，按出牌优先级由低到高重排后的序列 ；p为达到赢牌状态需要完成的出取对；Ar′为当不把该花色作为对子的花色时，按出牌优先级由低到高重排后的序列；p′为达到赢牌状态需要完成的出取对。endprint

玩家的状态集表示为：

3.3 目标集

设padd=p0+p1+p2+p3，pwini=padd-pi+pi′。玩家的目标是赢牌，当一个或多个pwini（i=0，1，2，3）出数和取数之和为0时，即为赢牌状态。玩家希望的赢牌方式组成了目标集。在实现中，用一个字节表示目标集，只利用目标字节的低4位，每一位上置位和清零分别表示对该位代表的赢牌方式是否坚持。例如，0x03表示玩家的目标是以万字牌或条子牌为对子的赢牌方式。

3.4 策略库

策略库中分为3部分内容：①计算出取对的方法，供更新器调用；②目标筛选方法，目标集中目标达成的可能性取决于当前状态，这部分方法从目标集中选择一个“合理”的目标，供筛选器调用；③目标分解方法，最终得到一个出牌序列，供分解器调用。具体策略将在下文作详细分析。

3.5 意图集

由筛选器得到花色的重排序列Ar和Ar′为玩家出牌提供了优先级，p和p′为出牌张数和取牌张数，二者共同组成了玩家的意图集。

3.6 行为集

行为集为机器人当前可以选择的动作，在实现中用一个字节表示，字节中的每一位分配给一个动作，置位为可以执行，清零为不可执行，匹配器即可将行为集字节与定义的动作及操作判断为是否可以执行。

3.7 执行器

执行器将要执行的动作及牌值按规定的协议打包好后，调用外部接口将动作请求发送给游戏逻辑控制单元。

4 策略分析

4.1 重排算法

玩家手中的牌按花色分成了4个序列A0、A1、A2、A3，下标表示花色。重排算法表示为：

R：A → （Ar，p）

A为重排之前牌的序列，Ar是重排后的序列，p=（m，n）为出取对。算法步骤为：

对于风字牌和箭字牌：①初始化Ar为空，p=（0，0）；②先将张数为3或4的牌依次从A中取出3张放入Ar；③剩余牌中张数为2且可以再得的牌取出放入Ar，每放一次取数加1 ；④剩余牌中张数为2且不可以再得的牌取出放入Ar，每放一次出数加2；⑤剩余的牌全为单张，按照可再得张数从多到少放入Ar，每放一次出数加1；⑥结束。

对于序数牌，每次按牌值从小到大遍历：①初始化Ar为空，p=（0，0）；②将三连张且不多余的牌取出按顺序放入Ar；③将3 或4张的牌取出3张，按顺序放入Ar；④将三连张有多余的牌按完整的三连张取出按顺序放入Ar；⑤将2张且可以再得的牌取出按顺序放入Ar，每次取数加1；⑥将2张且不可以再得的牌取出按顺序放入Ar，每次出数加2；⑦剩余的牌全为单张，按照可再得张数从多到少放入Ar，每放一次出数加1。

对手中牌按花色分别重排，得到一组重排后的序列Ar0、Ar1、Ar2、Ar3和一组出取对p0、p1、p2、p3。

4.2 手中牌状态计算

出取对比较算法：设M=（p1，q1），N=（p2，q2），若p1+q1*2N，否则M≤N。

设A为玩家手中某一花色所有牌的组成序列，Ar为重排后的序列，p为重排后得到的出取对，Ar′为从中挑出一张或两张相同牌值的牌后的重排序列，p′为对应的出取对。下面介绍由A得到Ar′和p′的算法。

若A为空，则Ar′为空，p′=（0，0）；若A不为空，设A中牌按牌值从小到大无重复排列成a1a2…an，出取对初始值为p′=MAX=（14，14）。

（1） 初始值i=0，Ar′为空。

（2） i=i+1，若i>n，则转到（7）。

（3） 若手中仅有1张ai且不可能再得一张，则转到（2）。

（4） 少计一张ai对剩余该花色牌进行一遍重排，得到一个出取对（m，n）和序列 At，将p′与（m，n+1）比较，取小的值为p′，Ar′=At。

（5） 若ai的张数仅有1张，则转到（2），否则转到（6）。

（6） 少计两张ai对该花色剩余牌进行一遍重排，得到一个出取对（m，n）和序列 At，将p′与（m，n）比较，取小的值为p′，Ar′=At，然后转到（2）。

（7） 结束。

按上述步骤得到4个花色的另一组重排后的序列Ar0′、Ar1′、Ar2′、Ar3′和一组出取对p0′、p1′、p2′、p3′。当某种花色牌的记忆发生变动时，仅对该花色的状态si作更新即可。

4.3 目标筛选策略

目标筛选即从各花色中选择一个，本设计中的策略是先由pwini（i=0，1，2，3）得到4个出取对，然后选出出数与取数之和最小的花色i。

4.4 目标分解策略

基本筛选方法即为目标分解策略。选择目标花色i后，对于不为i的花色j，达到目标需要将Ar中后pj的出数张牌打出，并得到pj的取数张牌与该花色剩余的牌组成三连张或三同张的组合。对于花色i，达到目标需要将Ar′中后pi′的出數张牌打出，并得到pi′的取数张牌与该花色剩余的牌组成三连张或三同张的组合。这些出与取的目的即组成了意图集。

5 结语

本文从人的思维推理过程角度对麻将游戏机器人进行研究，引入BDI推理模型构造麻将游戏机器人。通过分析麻将游戏规则，提出一种基于BDI推理模型的机器人结构，并对机器人的各个组件作了详细的设计描述，最后提出一种麻将游戏推理策略。本设计的优点在于实例化的BDI推理模型结构清晰，对真实玩家作了模拟，并且策略集中的方法可以替换，使设计具有可扩展性。更进一步的研究需求是引入情绪、性格等非确定性因素，以体现机器人的个性化。

参考文献：

[1]M E BRATMAN.Intention，plans，and practical reason[M].Cambridge University Press，1987.

[2]COHEN P，LEVESQUE H.Intention is choice with commitment[J].Artificial Intelligence，1990，42（3）：213-261.

[3]RAO A S，GEORGEFF M.BDI agents from theory to practice[C].Proceedingsof the first Conference on Multi-agent System，San Francisco，USA：ACM Press，1995： 312-319.

[4]张晓君，周昌乐.情感等级BDI主体模型研究[J].模式识别与人工智能，2013，7（26）：615-622.

[5]李明峰，李全军，查亚兵，等.基于BDI的CGF通信行为建模[J].系统仿真学报，2012，24（5）：1076-1081.

[6]陈童洋，韩玉合，谷新蕾，等.基于BDI的智能垃圾清理系统[J].软件，2012，33（9）：61-62.

[7]徐心和.棋牌游戏与事件对策[J].决策与控制，2007，22（7） ：787-789.