西游记纸牌游戏中的人工智能分析.doc

“西游记纸牌游戏”中的人工智能分析摘要 “斗地主纸牌游戏”因其玩法简单、娱乐性强、老少皆宜的特点，在近几年开始风靡全国，迅速成长为最受国人喜爱的牌类游戏之一。如今，许多成熟的AI技术逐步应用到商业游戏中，取得了激动人心的结果，对游戏产业的发展和Game AI 的发展起到了决定性的推动作用。兴趣使然，作者将AI技术与中国传统纸牌游戏结合，开发了一款基于安卓平台的人机交互游戏app“西游记纸牌游戏”。本文基于作者的项目“西游记纸牌游戏”，以“西游记纸牌游戏”的游戏规则为基础，对“西游记纸牌游戏”AI程序的各个必要部分进行如下分析、设计：1、 设计基于安卓手机平台的智能NPC。基于游戏规则，综合考虑机器玩家个性化、多样化、智能化等多个维度来对游戏NPC进行设计开发。大大提高游戏的趣味性、玩家的挑战性、对手的神秘性，从而提高游戏的可玩性。2、 提出通过权值矩阵来存储玩家手牌权值 大小，再结合手牌划分 评估机器玩家手牌强度。将纸牌信息量化，使其可计算、可比较，计算得出的手牌权值大小和手牌强度将作为机器玩家是否叫牌、如何拆牌及出牌，系统评估的重要依据。3、 提出基于树搜索的不完全信息判断方法。我们将判断过程分为两个阶段进行求解，第一阶段使用动态更新的博弈信息和合作博弈的知识来判断下一步行为策略；第二阶段把已有的实例训练构造成一棵决策树，先对已构造的决策树进行完全搜索，将结果作为下一步行为。如果搜索结果为空，则采取第一阶段的方法寻找行为策略。这个判断方法对算牌分析和拆牌分析起到了重大作用。4、提出基于博弈的规则决定合理出牌的方法。出牌方法的产生，依赖于几个条件决策：座次和身份、算牌分析结果、出牌规则和自身的拆牌倾向。而出牌规则的满足属于基本条件，座次和身份直接影响着各部分的权值分配，算牌分析则是通过当前已知的所有信息对其余两家手牌和策略的一种估算及预测，拆牌倾向性直接由拆牌方案给出出牌期望。综合以上条件，从而有针对性地给出合理的出牌方案。关键词 西游记纸牌游戏 拆牌算法 AI技术 Game AI1引言 计算机博弈（也称机器博弈），是一个挑战无穷、生机勃勃的研究领域，是人工智能领域的重要研究方向，是机器智能、兵棋推演、智能决策系统等人工智能领域的重要科研基础。它包括两大应用场景棋类博弈和牌类博。国际计算机博弈已经有了很长的历史，并且经历了一场波澜壮阔的搏杀，深蓝计算机的胜利也给人类留下了难以忘怀的记忆，近年来，桥牌、扑克游戏也成为人工智能研究的热点问题。国内的计算机博弈虽然起点低，困难大，但对于棋类博弈已日趋成熟。在我国，在线牌类游戏数量较多，其中“斗地主”作为中国广泛流传且具有中国特色的纸牌游戏最受欢迎。“西游记纸牌游戏”是对“斗地主”的创新化和趣味化，它属于不完全知识博弈 范畴。中国的牌类游戏历史悠久、流传广泛、人气居高，但它的计算机研究却困难重重。将相关的人工智能技术应用到“西游记纸牌游戏”，不仅使游戏生动灵活，极具商业价值和学术价值，更是对祖国传统文化的继承与发扬。2. 问题描述2.1“西游记纸牌游戏”基本规则：一共54张牌，3为沙僧，8为八戒，5为悟空，10师傅，小王为观音，大王为如来，2为pass牌，其余牌按大小分为小妖怪到大妖怪。2为PASS，可以通过上家出的任意牌，不包括如来和观音。玩家出牌阶段可以选择出单牌，对牌，三张相同牌，四张相同牌。双王大过四张相同牌，四张相同牌大过三张相同牌，三张相同牌大过任何单牌，对牌，多张相同牌也可以压过多张相同牌，前提是单张牌时要大于对方。如来和观音组合出牌，大于其他任何牌。初始阶段，一副牌54张，一人17张，留三张做底牌，在确定地主之前玩家不能知道底牌。图 1 游戏流程图玩家1（电脑）随机从一家玩家开始，依次轮流随机发牌，直到留下三张做底牌。叫牌后选定地主，开始出牌。有一个玩家牌出完，则所在方胜出。地主为一方，其余两家为一方。发牌/叫牌/出牌发牌/叫牌/出牌玩家2（电脑）玩家3发牌/叫牌/出牌2.2“西游记纸牌游戏”的判定规则： 有一个玩家牌出完，则所在方胜出。规定地主为一方，其余两家为一方。 统计每位玩家积分区内扣置的牌数，一张即为一分，玩家最终所获分数，依据分数的多少，确定玩家在游戏榜的排名。 2.3西游记纸牌游戏基本知识2.3.1发牌 一副牌 54 张，一人 17 张，留 3 张做底牌，在确定地主之前玩家不能看底牌。2.3.2叫牌 叫牌按出牌的顺序轮流进行，叫牌时可以选择 “取经 ” 、“ 不取 ” 。如果有玩家选择 “取经 ” 则立即结束叫牌，该玩家为地主；如果都“不叫”，则系统随机指明三位玩家其中一家为地主 。2.3.3牌型2.3.3.1牌型定义如下：火箭：即双王（如来和观音），最大的牌；Pass: 2为PASS。炸弹：四张同数值牌（如四个3，即四个沙僧）；三张牌：数值相同的三张牌（如三个“J”字妖怪）；对牌：数值相同但花色不同的两张牌（如红怪4+黄怪4）；单牌：单个牌（如5，即孙悟空）；单顺：五张或更多的连续单牌（如：4 5 6 7 8或7 8 9 10 J Q K），不包括2点和双王；双顺：三对或更多的连续对牌（如：3 3 4 4 5 5、7 7 8 8 9 9 10 10 J J），不包括2点和双王；三顺：二个或更多的连续三张牌（如：3 3 3 4 4 4、5 5 5 6 6 6 7 7 7 8 8 8），不包括2点和双王；三带一：仅限三张悟空牌+一张单牌或一对牌，如：5 5 5+6或5 5 5+9 9，不包括2点和双王；四带（一）二：仅限四张悟空牌两张单牌或两对牌），如：5 5 5 538或5 5 5 5+6 67 7，不包括2点和双王。2.3.3.2牌型大小 各牌型的大小定义如下：火箭最大，可以打任意其它的牌；PASS牌为2，可以通过上家出的任意牌，不包括如来和观音。炸弹比火箭小，比其它牌大，都是炸弹时按牌的分值比大小；除火箭和炸弹外，其它牌必须牌型相同且总张数相同才能比大小；单牌按分值比大小，依次是大王小王过大妖唐僧中妖孙悟空八戒沙僧小妖，不分花色(玩家牌的布局由系统按从大到小的顺序，依次排列)；对牌、三张牌都按分值比大小；顺牌按最大的一张牌的分值来比大小； 带牌仅用于出牌，不能用于接牌，炸弹中分值大过5的和火箭可接带牌。3. 相关人工智能技术3.1设计基于安卓手机平台的智能NPC前面我们谈到要基于游戏规则，综合考虑NPC个性化、多样化、智能化等多个维度来对游戏NPC进行设计开发。NPC智能化就是要求它模拟人的思维、行为，能够对环境作出适当反应或自主参与某一项活动。在本游戏中，NPC智能化指机器玩家能识别自己和其他玩家的扮演的角色和立场，通过对自己手牌和当前牌局的分析判断，完成叫牌、拆牌、出牌、让牌的动作。NPC个性化、多样化则指的是NPC的性格特征，具体体现于角色在候牌、取经 、出牌时的反应差异。比如，性格暴躁的角色，性格温和的角色，和古灵精怪的角色，面对同样的情形，他们的反应肯定不一样。而多样化的人物设定，让游戏变得更加逼真有趣。NPC智能化我们在后面的内容中将做分条详细地介绍，这里我们先对NPC个性化、多样化做具体地设计与分析。综合考虑性格的复杂性、作者精力的局限性和本游戏的实际需要，我们在此只做大体分类设计。下面给出一张表格来了解本文NPC的性格特征分类：图3 NPC的性格特征分类表性格特征候牌取经出牌NPCid分类催促频率取经概率出牌风格1标准型1次/15s0.5标准2犹豫型1次/20s0.1犹豫3耐心型1次/25s0.3求稳4急躁型1次/10s0.9快攻作者将NPC的性格特征融合进游戏流程中，通过一张图来帮助大家理解：执行行为5执行行为4执行行为3执行行为2发生行为1性格特征分析逻辑A被中断，由行为1触发判断正在执行逻辑ANPC触发真实玩家图 5 NPC个性化的游戏流程图NPC性格特征设计好后，接下来就是NPC的投放，本文主要从两个方面进行考虑:1、时间段：不同的时间段，玩家的流量不同，AI的投放数量也会对应有波动；2、区域：不同的区域、游戏场地，AI投放的数量、质量也会有区别。3.2手牌权值评估1，牌型的面值评估首先我们将扑克牌进行编码，转化为数值型数据。表 扑克牌编码表花色红牌黑牌绿牌黄牌编码abcd点数沙僧4悟空67八戒9师父2观音如来编码12345678131415每张扑克牌用一个数组来表示，花色、点数、编号、单张面值、所属玩家ID是扑克牌数组的属性，用数组表示自己当前的手牌、其他玩家打出的手牌，数组元素表示单张扑克牌，单张面值也就是单张牌值大小等于编号顺序大小，用CardValue表示。接下来我们进行牌型的面值评估，初步的方法是直接给出各种牌型的面值，牌型的面值KindValue=（CardNumber*CardValue），其中，KindValue是指牌型的面值，CardNumber指该牌型的牌所具有的牌的张数，CardValue指单张时候牌的面值。2牌型关系的评估牌型间的关系也是手牌估值的重要内容之一，我们根据牌型关系给每种牌型附一个牌型关系值动态变量，可以将某个牌型很有可能被敌方压住看成是一个不利因素。例如手中持有34567的顺子，但是没有顺子回手，这时我们可以根据该顺子的面值与恶劣的牌型关系导致的负牌型关系值之和来刻画。牌型关系的评估应该考虑到该谁出牌和地主农民的座次问题。如果自己是农民，且是地主的下家，恶劣的牌型关系比较轻；如果是地主的上家或者是地主，牌型关系更加恶劣。3实时更改相应参数因子。因为牌类游戏属于不完全信息博弈，变数太多，情况极其复杂。玩家手中的牌和牌池里打出的牌随时都在更新，那么相关预测参数也要相应更新。故可以通过后验法来实时调整预测参数。例如：A、B（自己）、C玩家，在A出了333（编号3代表悟空）+4的时候，参看自己手上没有3，这样的情形下，原本猜测C方有一个7的可信度为1。可是在经过几局的后验之后，可能出现A有含7的顺子，而C没有7的情形。从而可根据这种情形在总局数中的比例，适当调整这个可信度。玩家手上的牌数也是牌型权值评估要考虑的因素，例如，当三方手上的牌较少时，长顺子的权值会更高。这就需要动态、实时地调整预测参数了。 w1,1 w1,2 w1,3 W1，m 定义非负实数权值矩阵W= w2,1 w1,2 w1,3 W1，m ，wi,j 表示第i类牌 wn,1 wn,2 wn,3 Wn，m型牌型面值落在vj-1,vj）区间的手牌权值。设玩家手中的牌集合为X，牌型数目为M，也就是说X中的元素可以分成M个类别，同一类别中的元素是按照相同规则组合而成。设每轮出牌的策略空间为S，表示在规则允许的范围内，出牌的牌型选择的集合。设B为X的一个划分。我们用fi(X)|B来表示第i类牌型手牌权值的和，则fi(X)|B =( fiv0,v1)(wi,1 )|B ，fivk-1,vk)(wi,m)|B) （3.2.1）其中Xa,b)为牌型面值坐落在左闭右开整数区间a,b)中的手牌； Wi,j(玩家握有i类且牌型面值落在vj-1,vj）区间的手牌)fivj-1,vj)(wi,j)|B= 0(玩家没有i类且牌型面值落在vj-1,vj）区间的手牌) 用高维向量的表示方法来计算单手均值函数，用h(X)|B表示。相关定义：评估向量 f(X)|B =( f1(X)|B，f2(X)|B fM(X)|B) （3.2.2）手牌X在划分B下的评估函数F(X)|B为评估向量与向量（1,1,1，1）的内积： F(X)= f(X)|B（1,1,1，1）= fivj-1,vj)(wi,j)|B （3.2.3） 则单手均值函数h(X)|B= （3.2.4）