一类非完备信息博弈的信息模型

一类非完备信息博弈的信息模型马骁;王轩;王晓龙【摘要】近年来随着对非完备信息博弈研究的不断深入,如何表示、处理博弈过程中的信息成了新的问题.提出了信息空间的概念,指出了信息集与信息空间的关系.首次采用二分图构建了口型非完备信息游戏的通用信息模型，并在此模型基础上研究了信息获取方法，引入Markov模型进行信息处理•通过在四国军棋上的实验验证了通用信息模型在获取、管理非完备信息上的有效性，并证明了Markov网络在非完备信息处理中的有效性.期刊名称】《计算机研究与发展》年(卷),期】2010(047)012【总页数】10页(P2100-2109)【关键词】非完备信息博弈;信息空间；Markov网络;二分图;四国军棋【作者】马骁;王轩;王晓龙【作者单位】哈尔滨工业大学深圳研究生院智能计算研究中心,广东深圳,518055;哈尔滨工业大学深圳研究生院智能计算研究中心,广东深圳,518055;哈尔滨工业大学深圳研究生院智能计算研究中心,广东深圳,518055【正文语种】中文【中图分类】TP1810引言多年来针对机器博弈的研究在完备信息游戏上取得了令人瞩目的成功,许多游戏被彻底“解决”［1］掉.相比完备信息博弈,本文着重研究的非完备信息博弈是一种存在更加广泛的博弈.在诸如战争、股票市场这样的现实博弈环境下,参与者往往无法获得其决策所需要的全部信息,仅能利用其掌握的部分信息作出决策,这样的博弈被称作非完备信息博弈(imperfectinformationgame).非完备信息博弈具有博弈树、世界数更为巨大、估值函数更为复杂等特点.在非完备信息机器博弈上,国外的研究主要集中在扑克和桥牌上［2］.从20世纪60年代起桥牌机器博弈的研究就已展开,1998年后Ginsberg的桥牌程序GIB开始在各项比赛中获得优异成绩，目前GIB已经具有相当于人类桥牌“专家”的水平［3］.Billings等人的TexasHold'em程序在2003年也具有了击败较强实力人类选手的能力［4］.上述两类非完备信息游戏都是牌类游戏,其特点与棋盘类游戏有很大不同•近年来，一种被称为Kriegspiel［5］的“不可视”的国际象棋游戏成为了新的非完备信息博弈研究对象,这显示棋盘类非完备信息博弈研究日益受到人们的重视.国内的非完备信息起步相对较晚,但是中国特有的四国军棋为非完备信息的研究提供了良好的实验平台,带来了国内博弈研究的新浪潮.夏正友等人在文献［6］中提出了一种应用模糊集对军棋子粒进行猜测的方法.王轩教授等人在文献［7］中对四国军棋的搜索算法和估值函数的学习进行了探索.此外,相关的文献还有文献［8-9］.国际上与四国军棋类似的棋类研究还有Stratego.信息是非完备信息博弈的关键因素,它决定了信息集［10］中的节点个数和节点出现概率•节点出现概率则是基于博弈扩展式表达(gameextensiveform)的多种算法(IMP-minimax,MC-sampling,vectorminimaxing等)的重要参数.然而目前针对信息集中节点出现概率的研究并不多见,在四国军棋上仅文献［6］提出了一种子粒猜测方法,文献［11］有所提及,而在桥牌和扑克上没有专门的研究.出现这种情况是由于已有的非完备信息博弈研究对象主要集中在桥牌和扑克上,这两种游戏的非完备信息满足自然分布特性,信息获取直接,对信息处理的要求较低,节点概率可通过组合排列公式计算.然而,随着研究的深入,更加复杂的非完备信息博弈对非完备信息的处理能力提出了更高要求.寻找一种通用模型来表示并最终处理非完备信息成为亟待解决的问题•本文引入了I型和口型非完备信息博弈概念,针对口型博弈提出了一种基于二分图的通用信息模型,在此基础上研究了四国军棋的信息获取效率,及基于Markov网络的子粒猜测模型.1i,n型非完备信息机器博弈及其信息模型为形式化研究非完备信息机器博弈，首先引入一些概念.1•信息集(informationset)[10].博弈树中满足以下条件的多个节点的集合被称为信信息集中的所有节点属于同一个玩家.对于信息集中的任何两个节点x和y,x和y的儿子节点数相同.对于信息集中的任何两个节点x和y,如果x/y,x和y中的任何一者不能是对方的祖先.2•非完备信息博弈(imperfectinformationgame」IG).如果一棵博弈树中所有信息集都只有一个节点那么称此博弈为完备信息博弈,不满足该条件的称为非完备信息博弈.3•世界(world).—个世界是非完备信息博弈的一个可能结果[12],如图2中w1和w2即为该博弈过程的两个世界，世界的概念是针对博弈树的平整形式而言的.图1和图2描述的是具有两个世界的博弈树,图1是普通形式的博弈树,而图2将这两个世界垂直放置以简化博弈树.图1中,根节点为随机节点;具有相同标号的节点属于同一个信息集;方块节点属于玩家1,圆形节点属于玩家2,叶子节点上的数值表示玩家1的收益(在零和博弈中仅需标出一方的收益,本文中的所有举例都为零和博弈).图2中的a,b,e对应图1中标号分别为7,5,6的节点;c,d,f,g对应图1中的123,4.可以看出图2中的每个节点都满足信息集的定义,并且每个信息集都包含两个节点.Fig.1ExtensiveformoftheIIGgametree.图1非完备信息博弈树扩展形式Fig.2FlattenformoftheIIGgametree.图2非完备信息博弈树平整形式4•非完备信息空间(imperfectinformationspace).非完备信息博弈中的所有世界构成了该博弈的非完备信息空间,简称信息空间.将所包含世界的个数称为这个博弈的信息空间大小.由信息集的定义第3条并参照图1,信息集中的每一个节点都拥有一棵独立于该信息集中其他节点的子树,因此同一信息集中的每个节点都对应于非完备信息空间中的不同世界.进而,任何一个信息集都唯一对应非完备信息空间的一个子集合,我们将与一个信息集对应的非完备信息空间子集称作该信息集的信息空间.信息集的信息空间决定了从某一个信息集出发玩家的在不同策略下可能获得的收益,在IIG中决策点所处的信息集是玩家决策的唯一依据•因此，有必要选择合适的模型来记录博弈过程中玩家所处信息集的信息空间变化.该模型应具有3项基本功能:1)能够区分不同的信息集信息空间.2)能够通过博弈中产生的信号,方便地更改玩家所处的信息集信息空间.3)可以枚举信息集信息空间中独立世界.此外,真实博弈中的信息集往往拥有亿万计的世界,信息模型需要高效的表示形式.显然,对于一般的非完备信息博弈,寻找满足条件的信息模型是困难的,因此本文着重研究了应用范围较广的I,H型非完备信息博弈.满足下面条件1),2)的非完备信息博弈被称为I型非完备信息博弈：1)博弈的非完备信息空间X由n维构成，即X=(x1,x2,x3,...,xn),xiY且xiH.3)对于所有xi,|xi|=1.I型非完备信息博弈中非完备信息被分解为n个非完备信息元素xi,元素间满足约束条件2),元素的可取值为Y的幕集•例如，桥牌的非完备信息空间就是由未知纸牌在另外3家的分布构成的,X=(x1,x2,x3),Y=｛所有未知的纸牌｝.I型游戏是一种适用范围很广的非完备信息博弈模型,目前较为流行的5种非完备信息游戏中,桥牌、扑克Stratego和四国军棋都属于该类型.如果I型非完备信息博弈同时满足条件3),我们称其为口型非完备信息博弈.口型博弈限定了信息元素xi的维度，将纸牌类游戏排除在外.这是因为纸牌类游戏仅仅关心哪些牌在哪一家的手中,并不关心某人握牌的顺序(规则中握牌的顺序不影响出牌)，在此类游戏中信息元素xi的维度大于1;而像军棋这样的游戏中，玩家关心的不是某一方总共有什么子粒,而是具体到每一个子粒都是什么,因此此类游戏中|xi|=1.当博弈同时满足条件2),3)的时候,X中的每一维xi都对应Y中的一个元素，因此有凶=|丫|二n.口型非完备信息博弈的通用信息模型：我们引入图论中的二分图(bipartitegraphs)作为其信息模型，记二分图B={X,Y,E}为非完备信息口型博弈信息模型，其中EcXxY,X=(x1,x2,x3,...,xn),xi是博弈中各个信息元素，丫=(y1,y2,y3,...,yn),yi是博弈信息元素可能的一种取值•记PM(B)为二分图B的完美匹配(perfectmatching)的个数.命题1.B可以表示口型非完备信息博弈中的信息，且此博弈的非完备信息空间大小为B的完美匹配数.证明•首先，由条件1),3)可以得到X-Y是映射，又因为2)对于X的某个取值，任意jHk都有xjn保证了映射为满射，因此X-Y为双射•根据二分图的定义可知二分图完美匹配是顶点集U-V的双射，因此可由B表示X-Y,且B的完美匹配数为X-Y的映射个数，即信息空间大小•证毕.命题2•若V|xi|=ci,ci为常数.1型非完备信息博弈的信息可由通用信息模型B表示.证明•设X=(x1,x2,x3,...,xn)为I型非完备信息博弈,|xi|=ci,ci为常数•可将X扩展为乂=(x11,x12,...,x1c1,x21,...,xncn),由条件2)可知|X[=|Y|X满足口型非完备信息博弈条件，设B为乂的通用信息模型,B-X'•由乂的构造过程可知乂-X,因此B-X.证毕.在映射X^fX中，每个xi都由ci维的向量映射为一个集合，信息空间缩小为原来的1/ci,所以X的信息空间大小为•命题2中的条件部分对于大多数I型非完备信息博弈都满足，桥牌、扌卜克中的信息都满足该条件•鉴于口型非完备信息博弈通用信息模型可以表示大部分i,n型非完备信息博弈，本文将围绕其进行研究，在下面简称其为通用信息模型.通用信息模型中的信息获取:非完备信息博弈过程中玩家所拥有的信息处于动态过程中,随机节点的引入和对手不可见的走步都会导致不确定性的增加,而博弈过程中的一些信号则会导致不确定性减小•对于目前多数博弈，在参与者的决策点下方都不存在随机节点及不可见走步,因此本节主要讨论由博弈信号导致的信息获取•通用信息模型的信息保存在边集E中•在非完备信息博弈中,参与者通过观测博弈过程中产生的信号对E中的元素进行操作，从而达到管理信息的目的•比如，在桥牌中某家出了一张牌为草花J,所有的观测者都可将模型中与该张牌相连的其他边去掉，只留与草花J相连的边•很明显,经此修改后的二分图完美匹配数将会下降,模型的信息空间也将减小,即完成了信息获取的过程•在不同博弈中的博弈信号并非都如桥牌中这样明确,例如在四国军棋中,某个子吃掉了观测者的工兵根据规则，该子可能是司令到排长中的任何一个类型,在修改E的时候，该棋子与炸弹、工兵、地雷和军旗相连的边会被去掉,其他的边保留•非完备信息获取可表示为如下两过程:通用信息模型的信息处理:信息处理的目的是通过对模型的计算获取某一匹配出现的概率或者某一信息要素的概率分布•完成这个目标的难度在具有自然的均衡概率分布的游戏上和人为的非均衡分布的游戏上相差很多•对于前者,可用式(1)(2)计算，其中B-ij表示由B去掉节点xi,yj和与其相连的所有边后得到的子图•对于后者，则需要一个能够高效处理高维联合概率分布的模型.式⑴中m表示二分图的任意一个匹配,P(m)为该匹配出现的概率•式(2)中P(xi=yj)表示满足xi与yj相连的所有匹配出现的概率.2四国军棋中的非完备信息问题四国军棋是在中国普及率较高的一种棋类,其吃子和移动规则与二人军棋相同,由于篇幅限制本文不详细介绍，可参见文献[6].本文选择四国军棋来检验我们通用信息模型主要原因有3点:1)暗棋四国军棋(参与者不能看到对家和对手的棋子类型)的信息空间巨大,据我们的模型计算其初始信息空间为3.58x1053,远高于桥牌Declarer方的1.04x107.2)四国军棋中棋子由人类摆放,其分布不均衡.3)四国军棋的游戏规则使得博弈过程中信息获取效率不高•以上3条原因使四国军棋的信息处理较其他游戏更加困难,同时信息处理的重要性也更大.通用信息模型应用于四国军棋,主要得益于其表示能力和信息获取的能力,由于军棋布局不满足自然分布,因此不能直接采用完美匹配数来计算某一匹配概率,这一缺陷我们将在第3节采用Markov模型来弥补.四国军棋中信息的变化是由于对子粒的碰撞结果的观测.不同棋子进行碰撞获取信息的预期也不同,比如炸弹与任何子碰撞的结果都是对掉,因此获得信息的能力较差,平均为0.12b,而团长和营长可以获得最大的信息收益，为1.4b,这与人类选手的用子习惯相一致•四国军棋开局时一方的信息量为59.3b,盘中某方与对手一方的平均碰撞次数为10~20次，由上述数据估算军棋博弈至游戏结束时的平均信息在30b以上,这要远高于桥牌和扑克,后者结束时信息为0.四国军棋中对于碰撞的处理体现了玩家获取能信息能力的强弱•例如，棋子A吃掉了我方的军长,可以判定对方为司令.但如果碰撞的双方都不是自己的棋子时,或者有一个较长的碰撞序列,这时就需要从逻辑上和历史上对碰撞信息进行处理.因此,我们将四国军棋的观测分为3个等级:1级观测仅对与有己方棋子直接参与的碰撞进行观测;2级观测在1级观测的基础上增加了对碰撞双方棋子都非观测者情况下的信息处理;3级观测在2级观测的基础上采用回溯机制增加了对碰撞历史一致性的保证.四国军棋信息获取规则.L1:if（棋子Pi移动过）delete{eij|yj二地雷};if（棋子Pi的移动方式非普通子移动方式）delete{eij|yjH工兵};if（棋子Pi死后,Pi方的军旗变明）delete{eij|yjH司令};if（棋子Pi死后,Pi方的军旗没有变明）delete{eij|yj二司令};if（棋子Pi死后,Pi方的游戏没有结束）delete{eij|yj二军旗};if（棋子Pi与己方的棋子Pk碰撞,被吃掉）delete{eij|yj»Type（Pk）};if（棋子Pi与己方的棋子Pk碰撞，吃掉Pk）delete{eij|yj<Type（Pk）};if（棋子Pi与己方的棋子Pk碰撞，对掉）delete{eijM^Type（Pk）}.L2:if（棋子Pi与非己方的棋子Pk碰撞,被吃掉）delete{eij|vekjeE,yj>yk};if（棋子Pi与非己方的棋子Pk碰撞，吃掉Pk）delete{eij|vekjeE/yj<yk};if（棋子Pi与非己方的棋子Pk碰撞，对掉）delete{eij|eij|vekjeE/yj=yk}.L3:if（棋子Pi死掉,Pi之前曾经吃掉非己方棋子Pk）delete{ekl|veijeE,yl>yj}.上述规则中的观测对象Pi都为非己方棋子•算符,>,<分别为二元关系算符，表示两种类型棋子碰撞后的结果不是对掉、被吃掉和吃掉，算符二#则表示前项代表的棋子类型是否为后项,Type（Pk）为棋子Pk的真实类型.3基于MarkovNetworks的四国军棋棋子猜测模型本文第1节已经讨论了概率分布是否满足自然均衡条件对通用信息模型信息处理的重要影响.四国军棋的布局由人类完成,为了最大化博弈收益子粒之间存在支援和保护的关系,子粒分布明显不均衡.因此我们需要寻找一个高效的概率模型来对通用信息模型中存储的信息进行处理,输出与实际概率更加接近的概率分布.目前与四国军棋棋子猜测相关的文献仅有文献［6］.文献［6］中提出了一种基于模糊集和模糊近似关系的邻接棋子猜测模型,这与本文的研究方法有几点不同.1)文献［6］中通过模糊集将12种棋子映射为7种,降低了猜测的难度.2)文献［6］中采用相邻棋子的近似关系,棋子的相邻关系并不一定直接导致它们之间具有相关性,所以此假设属于经验设定,本文采用机器学习方法,其结果可能揭示一些超越人类一般认知的发现.3)由于一个棋子可能具有多个相邻棋子,文献［6］中的方法没有阐述如何从多个相邻近似关系中选择最为可信的棋子种类.4)本文的研究对于所有的棋子进行猜测,而不是仅对邻接有观测的棋子猜测,二者的测试范围上存在差异.Markov网络(Markovnetworks,MNs)［13］是一种无向图模型，能够高效地表示变量集上的联合概率分布.Markov网络由两部分组成:一是表示节点间的依赖关系的无向图;二是保存节点的联合概率的参数集.Markov网络是可分解的图模型(decomposableGM),其概率可由式(3)(4)计算：Markov网络广泛地应用于图像处理等领域•军棋的棋子布局与一个由许多像素组成的图片有很多相近的地方,每个像素都受到周围像素的影响,每个棋子也是;像素间的影响有时候是超距离的,而对于军棋也同样如此.如图3中的22和24号节点,因为必有一个是军旗，所以也存在很强的联系•此外，在模型选择的过程中,MNs的无向特性，也使其较贝叶斯网络和隐Markov模型更加适用于本文的环境，因此我们将图像领域的模型引入机器博弈中,第4节第的实验结果将证明模型选择的有效性.Fig.3ThestructureoflearnedMN.图3学习获得的Markov网络结构图4显示了通用信息模型如何同Markov网络结合起来，上面的空间表示信息模型空间，下面的为Markov网络空间•信息模型空间中是一个典型的二分图，所有的边都存在于X和Y之间，对于X中的每个节点都存在一个邻接向量，由大括号标出(图中仅标出一个，其他省略).Markov网络空间由随机变量节点和连接这些节点的无向边构成，每个随机节点拥有一个值向量(由小括号标出)•信息模型中的顶点集X被映射为Markov网络的节点，顶点xi的邻接向量映射为Markov网络中该节点的值向量.因为二分图的顶点集X内不存在边，所以顶点xi的邻接向量为|Y|维,Markov网络中每个节点可取值为|Y|个.Fig.4ThemappingfrominformationmodeltoMN.图4信息模型同Markov模型的映射关系Markov网络的结构通过学习的方法获得，目前较常用的图模型结构学习方法分为基于打分(score-based)[14-15]的方法和基于独立性检测的方法(independence-based)[16-17].后者具有无需搜索和便于验证的优点,考虑到网络中各节点的连接在博弈中具有现实意义,我们采用基于独立性检测的方法来学习网络结构.边选择指标是互信息(mutualinformation)相对于较常用的卡方指标,互信息具有可累加的特性,便于计算.同时,文献[18]中证明卡方实际上为对数似然度的近似值,而文献[19]证明互信息MI与对数似然度的比值一定，因此可以使用互信息作为独立性检测的指标.考虑到高阶独立性检测对学习样本的规模和计算时间都有较高要求,我们将独立性检测的最高阶数限定为2,为了确保推理的效率,网络的复杂程度也作了限制,使得生成的连接树(junctiontree)的树宽不大于6•首先计算网络中两个节点间的所有二阶互信息,选择最小值作为这两个节点间边的权重,然后按权重由大至小的顺序加入边,直至新生成网络的树宽超过6.上述设置下,通过对5672个不同的真实布局的学习,得到了如图4的网络结构.可以看到网络中直接相连的节点多数位于相邻的铁道线上,后两排的节点具有较为密集的连接,网络基本保持对称,大本营(节点22,24)中的棋子相关性较强.此外,连接节点的边并没有完全左右对称,这是因为游戏是按照顺时针进行的,阵型左右翼受到攻击的概率并不相同所导致的.这些特点都与目前人类玩家对于军棋的认识相一致.在推理方面，我们采用标准的推理过程，即由三角化后的Markov网络构建JunctionTree,然后进行推理•军棋中对棋子观测的结果往往是不确定的,大部分的棋子只能确定一个范围(值向量中存在多于一个1),针对这个问题时,我们采用贝叶斯网络中对于不完全数据处理方法，并有效解决该问题.4实验及分析为了验证本文提出的通用信息模型在信息获取和信息处理上的有效性,实验随机选取了200个真实的人类对战存档,将在不同观测等级下对不同的观测对象采用不同的阈值进行预测的结果进行了对比.表1中的数据显示了通用信息模型中|E|随棋局进行的变化趋势•其中L,U,R分别代表观测对象相对于观测者的位置丄evel是观测等级，表1中各项为在相应的走步数i下|Ei|/|EO|之值•数据显示四国军棋中对于上家和下家(L,R)的观测要明显比对家(U)有效，这是由于观测者无法通过直接与对家碰撞获取信息•第2个现象便是1级观测与2级观测的效果相差明显大于2级观测与3级观测的差,这似乎与人的一般认识相悖.通过对真实对局的深入分析，发现主要原因是3级观测利用一个棋子被杀后获取的新的信息来更新之前被这个棋子杀掉的其他棋子的信息•例如，玩家i1的棋子A首先杀死了i2的棋子B,最后被i3的棋子C杀死,一种情况:当i2与i3相等时，即B与C是同一玩家的棋子，该玩家由于掌握B的全部信息，因此不能从3级观测中获得额外的信息;另一种情况,C是炸弹或者司令这种获取信息量较小的棋子，更新的信息难以对B的信息产生增益•在实际对局中上述两种情况十分普遍，这直接导致3级观测的效果低于预期.TablelDensityoftheEdgesinInformationModel表1边集稀疏度表LStepURLevel=1Level=2Level=3Level=1Level=2Level=3Level=1Level=2Level=310.99780.99770.99770.99890.99860.99860.99830.99810.9981310.93820.92960.92900.97100.95150.95020.93840.92980.9293610.87270.85440.85270.93810.89500.89100.87450.85550.8540910.81960.79330.79030.91170.84780.84080.82220.79510.79221210.77420.74180.73750.88940.80750.79750.77840.74390.73971510.73700.69970.69440.86850.77220.75970.74200.70200.69661810.71050.66820.66220.85390.74680.73230.71380.66990.66352110.69220.64630.63920.84500.72940.71310.69460.64850.64102410.67910.63180.62420.83870.71920.70210.68130.63340.62582710.67340.62340.61560.83500.71190.69500.67150.62240.61543010.66860.61690.60880.82860.70320.68650.66170.61240.6057Markov网络输出各个棋子位置对于不同棋子的似然度，我们选择满足阈值条件的似然度最高的棋子类型(比如网络会输出位置i对应团长1的概率和团长2的概率,我们将两个概率加起来作为位置i对应棋子类型是团长的概率)作为猜测结果•采用准确率(precise)和支持率(Sup)作为评测指标，准确率是指猜测子粒类型正确的概率，支持率是指在当前走步下满足猜测条件的比率•猜测准确率和支持率计算式6),其中N代表满足条件的猜测次数,thre为阈值,MAP(m)为棋子m的最大后验概率•本文中实验的主要目的是为了验证Markov模型在子粒猜测上的表现，因此要求网络仅仅输出一个最可能的结果供检测•实际上当阈值小于0.5时，若不采用最大后验概率进行选择,网络有可能输出2个或以上的可能结果,若依此计算准确率,将高于本文中给出的准确率，也就是说本文给出的是一个准确率下限•若网络输出多个结果,则结果的二次选择和并行搜索方法将对博弈策略产生重要影响,应同时讨论,这超出了本文的研究范畴,也是本文要求网络仅仅输出一个最可能的结果供检测的原因.图5~7中1~600为对上家观测的结果,601~1200为对家观测结果,1201~1800为下家观测结果•图5中的3条曲线自下向上为1~3级观测曲线•由于真实对局的步数上限大多在350以内,因此可仅对此前的数据进行分析.图5中的3条曲线自下向上为1~3级观测曲线，图5中还显示随着走步的增多,1,2级的猜测准确率差距越来越大,而且对于对家的观测差距尤为明显,这是因为2级观测获取的信息在不断累积，也是因为2级观测对获取对家的信息更为有效.Fig.5Preciseunderthreeobservinglevelswiththreshold0.1.图5阈值为0.1时3种观测等级下的猜测准确度Fig.6Precisewithdifferentthreshold.图6不同阈值下准确度随走步变化Fig.7Supportwithdifferentthreshold.图7不同阈值下支持度随走步变化图6和图7是在观测等级为3时不同阈值下的准确率和支持率.图6中自下至上是阈值为0.1,0.3,0.4,0.6,0.7的曲线,图7中曲线顺序变为自上至下.可以看到越高的阈值其猜测准确度越高,其支持度则越低.高于0.7阈值的猜测准确率都在90%以上,其曲线与走步数无明显关系,由于很高的猜测准确率,在博弈中这一部分的棋子猜测可以作为真实棋子类型考虑.于是,该模型为四国军棋博弈的风险可控策略搜索提供了一个支持平台,即玩家可以根据某个棋子的最大后验概率和所处的博弈阶段根据图6计算其风险概率,以一定的风险因子控制此次搜索对全局的影响,对于高概率事件可采用完备信息博弈的搜索方法进行局部搜索.5结论非完备信息博弈是人工智能研究的新方向,在非完备信息博弈中玩家所掌握的信息随博弈的进展而动态变化,当博弈信号较为复杂时,表示、处理非完备信息变得困难.本文通过分解非完备信息空间，提出了I，口型非完备信息博弈,这两种博弈在现实世界中具有广泛的应用•针对口型非完备信息博弈提出了通用信息模型，通用信息模型解决了非完备信息的表示、获取问题,并将信息集中世界出现的概率同二分图的完美匹配联系起来.由于引入了二分图作为信息模型,可将二分图研究中的uniquelyrestrictedmatchings[20],minimalblockers问题的研究成果很好地应用于非完备信息博弈的信息处理.四国军棋具有巨大的非完备信息空间和复杂的博弈信号,本文通过对实战军棋对局的信息处理证明了信息模型在现实问题中的可用性.四国军棋中的世界分布不具均匀性，因此本文中将图像领域的Markov模型引入到博弈中形成军棋的子粒猜测模型,实验结果证明了图模型在人类布局行为分析预测上的有效性.本文中讨论的信息获取都是根据棋规观测得到的确定信息.然而四国军棋的信息获取还有一个重要途径,就是对玩家的行为分析(对那些根据规则不直接获取信息的走步的分析).这个问题将是我们接下来的研究重点.参考文献vandenHerikHJaap,UiterwijkJosWHM,vanRijswijckJack.Gamessolved:Nowandinthefuture[J].ArtificialIntelligence,2001,134:277-311SchaefferJ.Agamutofgames[J].AIMagazine,2001,22(3):29-46GinsbergML.GIB:Imperfectinformationinacomputationallychallenginggame[J].JournalofArtificialIntelligenceResearch(JAIR),2001,14:303-358BillingsD,BurchN,etal.Approximatinggame-theoreticoptimalstrategiesforfull-scalepoker[C]//ProcofIJCAI-03.SanFrancisco:MorganKaufmann,2003ParkerA,NauD,SubrahmanianVS.Game-treesearchwithcombinatoriallylargebeliefstates[C]//ProcofIJCAI-05.Denver:ProfessionalBookCenter,2005XiaZY,HuY,WangJ,etal.Analyzeandguesstypeofpieceinthecomputergameintelligentsystem[G]//LNCS3614:FuzzySystemsandKnowledgeDiscovery,SecondIntConf(FSKD2005).Berlin:Springer,2005:1174-1183WangXuan,XuZhaoyang.TheapplicationofTD-learninginimperfectinformationgames[C]//2007ChinaWorkshoponComputerGames.Chongqing:CAAI,2007:55-58(inChinese)(王轩，许朝阳•时序差分学习在非完备信息机器博弈中的应用[C]//2007中国机器博弈学术研讨会.重庆:中国人工智能学会,2007:55-58)XiaZY,ZhuY,LuH.EvaluationfunctionforSiguogamebasedontwoattitudes[C]//LNCS4223:Procofthe3rdIntConfonFuzzySystemsandKnowledgeDiscovery.Berlin:Springer,2006:1322-1331LuHui,XiaZhengyou.AspirationwithtimersearchalgorithminSiguo[C]//Procofthe6thIntConfonComputersandGames.Berlin:Springer,2008:264-274FrankI,BasinDA,MatsubaraH.Findingoptimalstrategiesforimperfectinformationgames[C]//Procofthe15thNationalConfonArtificialIntelligence(AAAI98).MenloPark:AAAIPress,1998:500-507WangJinyi.ResearchonJunqigameswithMonte-Carlosampling[D].Shenzhen:ShenzhenGraduateSchool,HarbinInstituteofTechnology,2005(inChinese)(王金一•基于蒙特卡罗抽样的军棋机器博弈的研究[D]•深圳:哈尔滨工业大学深圳研究生院,2005)FrankI,BasinDA.Atheoreticalandempiricalinvestigationofsearchinimperfectinformationgames[J].TheoreticalComputerScience,2001,252(1/2):217-256JordanMI.LearninginGraphicalModels[M].Cambridge,MA:MITPress,1999LamW,BacchusF.LearningBayesianbeliefnetworks:AnapproachbasedontheMDLprinciple[J].ComputationalIntelligence,1994,10:269-293HeckermanD.AtutorialonlearningBayesiannetworks,MSR-TR-95-06[R].LosAngeles,CA:MicrosoftResearch,1995SpirtesP,GlymourC,ScheinesR.Causation,Prediction,andSearch.AdaptiveComputationandMachineLearningSeries,2nded[M].Cambridge,MA:MITPress,2000JiJunzhong,LiuChunnian,YanJing.AfastBayesiannetworkstructurelearningalgorithm[J].JournalofComputerResearchandDevelopment,2007,44(3):412-419(inChinese)(冀俊忠,刘椿年，阎静•一种快速的贝叶斯网结构学习算法J].计算机研究与发展,2007,44(3):412-419)KuHH,KullbackS.Loglinearmodelsincontingencytableanalysis[J].TheAmericanStatistician,1974,28(4):115-122YaramakalaS.FastMarkovblanketdiscovery[D].Ames,Lowa:LowaStateUniversity,2004GolumbicMC,HirstT,LewensteinM.Uniquelyrestrictedmatchings[J].Algoritmica,2001,31(2):139-154MaXiao,bornin1979.PhDcandidateincomputerscienceandtechnologyoftheHarbinInstituteofTechnology,Harbin,China.Hiscurrentresearchinterestsincludeimperfectinformationgames.马骁,1979年生,博士研究生,主要研究方向为非完备信息博弈.WangXuan,bo