（计算机应用技术专业论文）四国军棋智能系统定式库及开局匹配研究与实现.pdf

；l q 1-一 1汨 l 产 1 n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s t h eg r a d u a t es c h o o l c o l l e g eo fi n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y r e s e a r c ha n d i m p l e m e n t a t i o n ： t h ej o s e k i d a t a b a s e & o p e n i n g m a t c h i n g 。c p u t e rsigin o mu t e rb i g u o a t h e s i si n c o m p u t e rs c i e n c ea n dt e c h n o l o g ye n g i n e e r i n g b y s h im i n a d v i s e d b y a s s o c i a t ep r o f e s s o rl i un i n g z h o n g & x i a z h e n g y o u s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro f e n g i n e e r i n g j a n u a r y , 2 0 1 0 j 一 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：漫么 日 期：冱丛埠 南京航空航天大学硕士学位论文 摘要 人机博弈是人工智能的一个重要研究领域，其中不完全信息的人机博弈能够模拟现实复杂 世界中不确定环境下的决策，因此越来越受到关注。四国军棋是一种典型的不完全信息游戏， 其特点是不仅需要在对手和同盟棋子信息不确定的情况下做出决策，而且需要考虑与同盟的合 作问题。目前四国军棋人机博弈研究存在的两个主要问题是：一、尽管针对四国军棋本身特点 进行了搜索算法的研究，但是搜索的深度和结果，都还是难以令人满意：二、由于基础性研究 还不够深入，目前没有好的评价函数。这两大瓶颈严重地影响了四国军棋人机博弈系统智能水 平的高低。因此，有必要从其它方面入手对四国军棋开展研究。 本文围绕四国军棋的人机博弈展开深入的研究与分析，主要工作如下： 1 )参考同棋的定式库技术、中国象棋和国际象棋的开局库技术和残局库技术，将定式库技术 引入四国军棋的人机博弈研究。设计与实现了四国军棋的定式库以及相应的定式库开发系 统，并在人机博弈系统中使用定式库技术米进行最优策略的决策。定式库技术在四国军棋 博弈系统中的应用，降低了博弈系统对搜索算法的依赖，避免系统单纯依靠搜索算法而犯 战略上的低级错误。 2 ) 针对棋手所用布局的倾向性和范围性，本文提出了一种基于样本的策略指导方法一开局 匹配算法。该算法主要应用于开局阶段，根据开局阶段获得的少量信息，对待选的样本库 进行快速地筛选，从而得到当前布局的假想布局，指导最优策略的决策。 3 )针对四国军棋的不完全信息特征，提出了四国军棋的蒙特卡罗算法。该算法通过单样本条 件下的最优策略在整体样本条件下的模拟游戏，选出表现最好的策略作为最优策略。四国 军棋的蒙特卡罗算法通过模拟游戏将不确定因素从评价函数中剥离出来，为评价函数的设 计提供了新的思路。 4 ) 由于原有实验平台n h o p ev i & v 2 版本所采| j 的系统框架主要侧重于博弈搜索，而且其智 能模块的过程化的编程方式也使其可扩展性受到限制。定式库技术、开局匹配技术与原有 的系统框架存在冲突，同时，为了增强实验平台的可扩展性，本文设计与实现了n h o p ev 3 。 n h o p ev 3 实验平台在设计的过程中采用了面向对象的设计方法，同时注重结构设计的天 然性和合理性，使得新的实验平台易于理解和扩展。 关键词：四国军棋，定式库技术，开局匹配，蒙特卡罗算法，n h o p ev 3 四国军棋智能系统定式库与开局匹配技术设计与实现 a b s t r a c t g a m e - p l a y i n gi sa ni m p o r t a n td o m a i nf o ra r t i f i c i a li n t e l l i g e n c er e s e a r c h g a m e sw i t hi m p e r f e c t i n f o r m a t i o nt h a tc a ns i m u l a t ed e c i s i o nm a k i n gu n d e rt h eu n c e r t a i n t yo ft h er e a lw o r l da r eb e c o m i n g m o r ea n dm o r ep o p u l a r s i g u oi sat y p i c a li m p e r f e c ti n f o r m a t i o ng a m e ，w h e r ec o m p l e t i n gp l a y e r s m a k ed e c i s i o nu n d e rc o n d i t i o n so fu n c e r t a i n t ya n dh a v et oc o o p e r a t ew i t hl e a g u i n gp l a y e r s f o rt h e m o m e n t ，t h e r ea r et w om a j o ri s s u e si ns i g u oc o m p u t e rg a m e p l a y i n gr e s e a r c ha sf o l l o w s ：f i r s t ，t h e s e a r c ha l g o r i t h mo fg a m e - t r e ei ss t i l li m p e r f e c ta n dc o u l dn o ts e a r c hd e e pe n o u g h ，t h o u g hal o to f e f f o r t sh a v eb e e nm a k e ni nt h i sa r e a s e c o n d ，o n eo ft h eb a s i ce l e m e n t si nc o m p u t e rg a m e p l a y i n g r e s e a r c h ：c o n s t r u c t i o nm e t h o do fe v a l u a t i o nf u n c t i o ni ss t i l ln o ts og o o d t h o s et w om a j o ri s s u e s h a v es e r i o u s l ya f f e c t e dt h ed e v e l o p m e n to fs i g u oc o m p u t e rg a m e - p l a y i n gr e s e a r c h t h e r e f o r e ，i ti s n e c e s s a r yt os t a r tf r o mo t h e ra s p e c t so fr e s e a r c ho n t h es i g u o t h i sp a p e rh a sm a d ed e t a i lr e s e a r c ha b o u ts i g u oc o m p u t e rg a m e - p l a y i n ga n dt h em a i nw o r l ( s a r ea sf o l l o w s ： 1 1 r e f e r e n c et ot h ed a t a b a s eo f j o s e k ii ng o ，m eo p e n i n g - b o o k t h ee n d g a m e l i b r a r yi nc h e s s c h i n e s ec h e s s ，t h i sp a p e ri n t r o d u c e st h et e c h n o l o g yo fj o s e k i - d a t a b a s ei n t os i g u oc o m p u t e r g a m e p l a y i n g t h i sp a p e rp u t st h o s ep a r t i c u l a rp a r t i a lc o n d i t i o n sw i t hr e l a t i v es t r a t e g i e si n t h e d a t a b a s eo fj o s e k ia n dm a t c h e sj o s e k it of i n dt h eb e s tc h o i c eb e f o r es e a r c ha l g o r i t h m w i t ht h e d a t a b a s eo fj o s e k i ，t h eg a m e - p l a y i n gs y s t e mi ss m a r t e rt h a nb e f o r e 2 ) s p e c i f i ct ot h et e n d e n c ya n dr a n g e a b i l i t yo f t h el a y o u t su s e db yo n ep l a y e r , t h i sp a p e ri n t r o d u c e s an e ww a yb a s e do ns a m p l e st om a k et h eb e s tc h o i c e ：q u i c km a t c h i n ga l g o r i t h m q u i c k m a t c h i n ga l g o r i t h mi sm a i n l ya p p l i e di nt h es t a g eo fo p e n i n g u s i n gt h ei n f o r m a t i o ng a i n e db y t h es t a g eo fo p e n i n g ，w es c r e e nt h o s es a m p l e sq u i c k l ya n df i n a l l yg e tas a m p l et h a ti st h em o s t q u a l i f i e dt og u i d et h ed e c i s i o n - m a k i n go f t h eb e s tc h o i c e 3 ) a i m a tt h ei m p e r f e c t i n f o r m a t i o nf e a m r eo fs i g u og a m e ，t h i sp a p e ru s e sm o n t ec a r l oa l g o r i t h m t os i m u l a t eg a m e - p l a y i n ga n df i n d st h eb e s tc h o i c ef o rt h ec u r r e n ts i t u a t i o n i nt h i sw a y , t h e e v a l u a t i o nf u n c t i o ni sn ol o n g e rc o n n e c t e dw i t ht h ep r o b a b i l i t i e s m o n t ec a r l oa l g o r i t h m p r o v i d e san e ww a y t od e s i g nt h ee v a l u a t i o nf u n c t i o n 4 ) s i n c et h ep r e v i o u sp l a t f o r m sn h o p ev 1 & v 2 a r ed e s i g n e df o rt h es e a r c ha l g o r i t h m ，t h e ya r e n o ta d a p t e dt ot h et e c h n o l o g yo fj o s e k i d a t a b a s e ，q ma l g o r i t h mo rm o n t ec a r l oa l g o r i t h m ， t h e r e f o r ew ed e s i g na n di m p l e m e n tn h o p ev 3 n h o p ev 3i sd e s i g n e dw i t ho o pa n dc o u l db e 南京航空航天大学硕士学位论文 e a s i l ye x p a n d e d k e y w o r d s ：s i g u o ，t h et e c h n o l o g yo fj o s e k i d a t a b a s e ，o p e n i n gm a t c h i n g ，m o n t ec a r l o ，n h o p ev 3 四国军棋智能系统定式库与开局匹配技术设计与实现 南京航空航天人学硕十学位论文 目录 第一章 绪论1 1 1 人机博弈与四国军棋1 1 1 1 人机博弈简介1 1 1 2 四国军棋简介2 1 1 3 研究的关键点5 1 2 定式库技术简介6 1 2 1 定式库技术概要6 1 2 2 围棋定式库7 1 2 3 中国象棋的开局库8 1 2 4 中国缘棋的残局库9 1 3 开局匹配技术简介1 0 1 3 1 蒙特卡罗算法1 1 1 3 2 桥牌的蒙特卡罗算法1 1 1 3 3 罔棋的蒙特卡罗算法1 2 1 4 本文主要工作和结构一1 2 第二章四国军棋的定式库设计与开发1 4 2 1 四国军棋定式库简介1 4 2 2 四国军棋人机博弈系统的组织结构1 s 2 3 四国军棋定式库设计1 6 2 3 1 基本信息1 7 2 3 2 特征信息1 8 2 3 3 定式描述2 1 2 4 四国军棋定式库实现一2 2 2 5 四围军棋的定式匹配过程2 5 2 6 四围军棋定式库的自动扩展2 7 2 6 1 基于对称的定式扩展2 7 2 6 2 基于空节点的定式扩展2 9 2 7 本章小结3 0 四国军棋智能系统定式库与开局匹配技术设计与实现 第三章开局匹配的设计与实现3 1 3 1 开局匹配技术的简介一3 1 3 2 开局匹配技术在系统结构上的位置3 2 3 3 概率更新过程3 3 3 3 1 先验概率3 3 3 3 2 概率更新3 5 3 4 差异度3 6 3 4 1 差异度介绍3 6 3 4 2 四国军棋棋局差异度计算3 7 3 s 高差异度样本空间下的快速匹配3 9 3 6 实验与分析4 1 3 6 1 样本布局库变化4 2 3 6 2 实验总结4 4 3 7 低差异度样本空间下的蒙特卡罗算法4 4 3 8 本章小结一4 7 第四章 可扩展的四国军棋实验平台( n h o p ev 3 ) 设计4 8 4 1 实验平台n h o p e 及存在的问题4 8 4 1 1 n h o p e 系统4 8 4 1 2 存在的问题4 8 4 2 n h o p ev 3 系统需求设计4 9 4 2 1 系统的功能需求4 9 4 2 2 系统的界面需求4 9 4 3 n h o p ev 3 系统总体设计5 0 4 3 1 系统框架5 0 4 3 2 系统流程5 2 4 4 n h o p ev 3 系统详细设计5 4 4 4 1 棋局基本信息。5 5 4 4 2 对战平台5 5 4 4 3 智能模块5 6 4 4 4 人机交互界面5 7 4 5 系统的运行界面一5 7 4 6 本章小结5 8 南京航空航天大学硕士学位论文 第五章 总结与展望5 9 参考文献6 1 致谢一6 6 在学期间的研究成果及发表的学术论文6 7 四国军棋智能系统定式库与开局匹配技术设计与实现 图清单 图1 1 四国军棋的棋盘3 图1 2围棋定式树8 图2 1 系统框架与基本流程1 6 图2 2 基本信息表示举例1 8 图2 3m a x 推理流程图2 1 图2 4 定式举例2 2 图2 5 定式数据库2 3 图2 6 定式库开发界面2 4 图2 7 定式存储举例2 4 图2 8 数据处理模块类图2 5 图2 9 定式匹配过程2 6 图2 1 0 对称的棋盘2 8 图2 1 1 基于对称的定式扩展2 9 图2 1 2 基于空格的定式扩展3 0 图3 1 开局匹配在系统中的位置3 3 图3 2 棋子的先验概率分布3 4 图3 3 快速匹配算法流程3 9 图3 4 样本库布局数的变化趋势4 2 图3 5 样本库布局熵的变化趋势4 3 图3 6 样本库差异度的变化趋势4 4 图3 7 蒙特卡罗算法流程4 s 图3 8 蒙特卡罗算法的搜索过程4 5 图3 9 两种不同的组合方式4 7 图4 1 n h o p ev 3 的系统框架5 0 图4 2 策略模块的系统组成5 1 图4 3n h o p ev 3 的系统流程5 3 图4 4 n h o p ev 3 的系统类图5 4 图4 5 棋局基本信息类5 5 图4 6 对战平台类5 6 南京航空航天大学硕+ 学位论文 图4 7 智能模块类5 6 图4 8 人机交互界面类5 7 图4 9n h o p ev 3 的运行界面5 8 表清单 表2 1 棋子基本信息描述p k i n d 1 7 表2 2 最大值最小值表2 0 表3 1 棋子胜负表3 8 表3 2 棋子差异度表3 8 表3 3 差异度取值列表4 3 南京航空航天大学硕+ 学位论文 第一章绪论弟一早 三石下匕 四国军棋是国内非常受欢迎的一款棋类游戏。与围棋、中国象棋不同，四国军棋是不完全 信息博弈游戏。四国军棋的人机博弈研究就是基于不确定信息完成相关信息的分析与整理，并 在此基础上完成最优策略的决策。四国军棋的人机博弈研究为现实世界中的不确定性问题提供 了新的平台与思路。 1 1 人机博弈与四国军棋 1 1 1 人机博弈简介 入机博弈是人工智能的一个重要的研究领域，人机博弈的主要研究内容是利用人工智能领 域的知识技术来实现人与机器的对弈【i 】。一方面，人机博弈将人工智能领域中的理论和方法应 用到博弈游戏中，提高了博弈程序的智能水平。另一方面，所谓游戏实际上是对现实生活的抽 象模拟，人机博弈为人工智能领域中出现的新的方法、理论提供了一个进行模拟和测试的平台。 人机博弈领域的大量研究成果为人工智能领域提供了很多概念和方法，解决了许多实际问题， 普遍应用于航空调度、天气预报、资源勘探、军事博弈、金融调控等领域。 自计算机诞生之日起，西方学者就开始研究棋类游戏的人机博弈。1 9 5 0 年，c e s h a n n o n 发 表了人机博弈领域的奠基性文章【2 】，提出了对棋类游戏博弈程序的描述。1 9 5 7 年，b e m s t e i n 利 用深度优先搜索算法，在i b m 7 0 4 机上开发出第一个完整的国际象棋( c h e s s ) 程序【3 1 。1 9 5 9 年， a l s a m u e l 从机器学习的角度【4 】对西洋跳棋( c h e c k e r ) 进行研究，其设计的博弈程序具有学习 能力。1 9 7 0 年，a z o r b r i s t 在他的博十论文【5 l 里从模式识别的角度对围棋( g o ) 博弈进行研究， 编写出第一个完整的同棋程序。二十世纪七八十年代，学者们认识到博弈程序的智能水平与搜 索深度有很大关系【6 】，于是开始大量研究各种搜索算法。八十年代米，随着空着剪枝，单步延 伸等高级搜索算法的研究和机器学习方法的发展【6 1 ，机器智能得到了很大的提高，并逐渐大 规模地向人类智能发起了挑战。1 9 8 9 年，第一届计算机奥林匹克大赛在英国伦敦正式开幕，人 机博弈在世界上的影响也日益广泛。1 9 9 4 年，跳棋程序c h i n o o k t l 刀挑战了跳棋世界冠军 m a r i o nt i n s l e y 。1 9 9 7 年，i b m 的d e e pb l u e t s l 打败了保持十几年世界棋王头衔的g a r r y k a s p a r o v 1 9 】，成为人工智能领域的一座里程碑。随后，黑白棋( o t h e l l o ) 程序l o g i s t e l l o 也 打败了黑白棋世界冠军t a k e s h im u r a k a m i 【2 们。 国际上，人机博弈主要研究两洋跳棋、国际象棋和黑白棋，经过专家学者几十年的努力， 取得了很大的成就。国内的人机博弈研究起步较晚，主要研究中国象棋和围棋。目前，中国象 1 四国军棋智能系统定式库与开局匹配技术设计与实现 棋博弈程序的智能水平已经达到大师级别，比较著名的有象棋世家2 、棋天大圣、象棋奇兵等。 围棋博弈程序的智能水平与人类还有很大距离，由于其高复杂度的状态空间，目前还是一个充 满挑战性的研究课题。在国内，只有陈志行教授的围棋程序“手谈”经常活跃在大赛上，但其智 能水平仅仅是业余级别。 博弈类游戏根据游戏过程中玩家掌握的信息的不同，可以分为两大类：完全信息博弈游戏 和不完全信息博弈游戏。完全信息博弈游戏中参与游戏的各方所掌握的信息是一致的、对称的。 常见的完全信息博弈游戏有国际象棋、中国象棋、围棋等。与此相对，不完全信息博弈游戏中 参与游戏的各方无法完全掌握其他玩家的信息，各方掌握的信息是不一致的、不对称的。此类 游戏常见的有桥牌、扑克等。 完全信息人机博弈的主要研究对象是两人零和游戏( 参与者只有两人，一方的得分是另一 方的失分，总和为零) ，所获得的主要研究成果有：m c a m p b e l l 等描述了国际象棋d e e pb l u e 的 体系结构及其实现【1 8 】；m b u r o 描述了黑白棋程序l o g i s t e l l o t 2 2 1 中具有自我学习能力的估价 函数；v v a n s h e l e v i c h 描述了六角棋( h e x ) 程序h e x y 中基于演绎规则的局面评价方法【2 3 】： h i i d a 等描述了日本象棋( s h o g i ) 的研究状况和技术难点【2 4 】，并预言在2 0 1 0 年日本象棋程序 能与世界冠军相抗衡；m m u l l e r 描述了围棋研究的技术现状和面临的挑战【2 5 1 。 不完全信息人机博弈的研究起步较晚，进展也很缓慢，但西方学者在西洋陆战棋 ( b a c k g a m m o n ) 、桥牌( b r i d g e ) 和扑克( p o k e r ) 等游戏的研究中也取得了一定的成绩。西洋 陆战棋属于随机游戏，g t e s a u r o 引入即时差分学习等方法设计了西洋陆战棋程序 t d - g a m m o n 2 6 1 ，在1 9 9 8 年的计算机冠军赛上赢了世界冠军。m l g i n s b e r g 引入分区搜索技 术和蒙特卡罗随机抽样等方法到桥牌程序g i b t 2 刀中，使得该程序所向披靡地赢得了2 0 0 0 年计 算机奥林匹克桥牌比赛的冠军。2 0 0 2 年，d b i l l i n g s 等设计的德克扑克程序p o k i t 2 s l 在对手建模 上采用统计学习的方法，目前其智能水平达到了职业中级。 2 0 0 2 年，h j a a nv a nd e nh e r i k 等纵观人机博弈的发展历史，从状态空间和博弈树的复杂度 角度探讨了人机博弈的研究进展，并高瞻远瞩地预测未米十年人机博弈的发展趋势【。文中指 出对于博弈树或状态空间复杂度相对较低的博弈来说，通过蛮力搜索或基于知识库的方法就能 得到解决，而对于状态空间和博弈树的复杂度都很高的博弈来说，由于计算机的处理能力有限， 采用蛮力搜索和知识库的方法都难以解决。因此，人机博弈的研究尤其是不完全信息人机博弈 的研究需要引入新的理论和方法。 1 1 2 四国军棋简介 四国军棋是我国深受欢迎的棋类游戏之一。四国军棋游戏支持两人对战，也支持四人同时 游戏。进行四人游戏时，四个人分别占据棋盘四边，相对的两家两两结为同盟，相互配合进行 2 、 南京航空航天大学硕士学位论文 战斗；两人游戏时，则分占棋箍的上下两边，相互作战。四国军棋的棋盘如图1 1 所示。 1 1 2 1 游戏规则 图1 i四国军棋的棋盘 四国军棋可以分为红、蓝、灰、绿四方， 长、旅长、团长、营长、连长、排长、工兵、 布局限定： 1 ) 布局时行营必须为空。 2 ) 炸弹不能放在第一行。 3 ) 地雷只能放在最后两行。 4 ) 军旗必须放在大本营内。 行棋规则： 任意一方拥有1 2 种棋子：军旗、司令、军跃、师 地雷、炸弹，共2 5 个棋子。 3 四国军棋智能系统定式库与开局匹配技术设计与实现 1 ) 行棋可以分为移动和吃子两种，两者都无法跨越棋子而进行。 2 ) 公路线上的棋子只能走一步。 3 ) 铁路线上的棋子不限定步数，但只能直走或经过弧形线，不能转直角弯。 4 ) 行营内若有棋子，则敌方棋子无法进入行营进行吃子。 5 ) 大本营内的棋子无法弭进行移动。 6 ) 工兵在铁路线上不受直角弯的限制，能够到达铁路线上相连的任何一个节点。 7 ) 地雷不能移动。 吃子规则： 1 )四国军棋棋子的大小顺序如下：司令 军长 师长 旅长 团长 营长 连长 排长 工兵， 大的棋子吃小的棋子，若两者相同，同归于尽。 2 ) 地雷小于工兵，大于所有上述其他棋子。 3 ) 炸弹与任何棋子相遇时，同归于尽。 4 ) 如果一方的司令死亡，则该方的军旗暴露。 胜负判断： 幸存的一方为胜家，军旗被扛或是无棋可走都会被判负。 1 1 2 2 游戏特点 四国军棋是典型的不完全信息博弈游戏，需要在不确定对手和同盟棋子信息的情况下做出 决策，同时还要考虑同盟之间的合作问题以及可能存在的欺骗行为。与象棋等其他游戏相比， 它有以下四个特点： 1 不完全信息博弈 开局时，玩家不知道对手及同盟方的布局，只能依据经验猜测。随着游戏的进行，也只能 通过棋子的拼杀获得部分棋子信息( 通过第三方裁判获知棋子之间“大于”、“小于”或“同归于尽” 的关系) 。与牌类游戏相比，四国军棋玩家获得的信息更少，因为牌类游戏中玩家打出的牌是可 见的。 2 布局的不确定性与相关性 在象棋等游戏中玩家的布局是固定的，并且都是相同的；在牌类游戏中玩家手上的牌具有 随机性，并且没有位置的概念：在四国军棋中玩家按照自己的思路和喜好完成布局安排。一般 情况下布局中的棋子存在着一定的相关性，可能是攻击型的强强组合，也可能是协防型的环环 相扣，甚至是空城计似的故弄玄虚，这些相关性隐藏在布局之中，有待玩家在游戏的过程中凭 借白己的经验逐步判断和发现。通过布局的相关性来减少布局不确定性的影响，是四国军棋高 手必备的素质。 4 、 南京航空航天大学硕士学位论文 3 合作与欺骗 作为暗棋，欺骗是四国军棋不可避免的话题。如何充分地利用信息的不对称性进行欺骗， 赢得额外的战斗实力并最终影响战争的天平，这是四国军棋游戏胜负的关键。另一方面，合作 也是四国军棋的特色之一。同盟双方良好的合作，可以战胜实力更为强劲但默契不足的对手。 如何在暗棋的情况下准确地探知对方的意图，并做出行之有效的反应，这是一个四国高手所应 具有的素质。 4 博弈复杂度 四国军棋棋盘的大小是1 7 1 7 ，玩家在棋盘上的行棋空间很大，并且由于四国军棋的行棋 规则简单，使得玩家有大量的合法走法。1 v 1 模式下，玩家平均的行棋选择大约为1 5 0 种，2 v 2 模式下大约为9 0 种。这就使得四国军棋的博弈树复杂度非常高。另外，四国军棋不是收敛性游 戏。随着游戏的进行，棋子的灵活性逐渐增加，博弈树的复杂度并不会降低。分支大，不收敛， 四国军棋博弈树的这两个特性使得四国军棋的人机博弈问题很难通过博弈搜索算法得到完美的 解决。 1 1 3 研究的关键点 棋类游戏的人机博弈系统一般有四个基本组成部分【2 9 】：知识表示、走法产生器、搜索算法 1 3 2 1 和估价函数，四国军棋人机博弈系统同样包含这四个部分。但是，作为不完全信息人机博 弈系统，四国军棋人机博弈系统无法完全掌握对方的信息，因此在知识表示和局面评估方面会 遇到一些困难。 四国军棋的知识表示可以分为棋盘信息表示和棋子信息表示。四国军棋的棋盘是1 7 1 7 的 大小，其中，不合法的落点1 6 0 个，合法的落点1 2 9 个。四国军棋的不合法节点可以分为两类： 不可到达节点和不可停留节点。四国军棋的合法落点可以分为四种类型：公路节点、铁路节点、 行营和大本营，而且铁路节点还可以进一步细分。这些不同类型的节点对应着不同的布局限制 和行棋规则，对其表示的优劣会直接影响到走法产生器的工作模式和效率。关于棋子信息的部 分，四国军棋的棋子可以分为四方，每一方有1 2 种共2 5 个棋子。除了常规棋子军长、师长、 旅长、团长、营氏、连长、排长外，还有：【兵、炸弹、地雷、司令等特殊的棋子，这些特殊棋 子会有一些特殊的行棋规则和胜负判断，对其的设计和表示也是一个需要注意的部分。另外， 四国军棋是不完全信息博弈游戏，游戏过程中需要不断地根据发生的事件进行深层次地信息挖 掘和整理。如何建立信息推理机制，如何存储相关的推理估计信息，这些都是四国军棋博弈研 究中的难点问题。 走法产生器的主要工作是根据相应的走法产生机制，生成棋局下所有棋子的合法走法。走 法产生机制主要与棋子所处落点的类型以及棋子的类型相关，具体的内容参考1 1 2 节。走法产 5 四国军棋智能系统定式库与开局匹配技术设计与实现 生器中需要考虑的主要是相关走法的存储问题。在建立博弈树进行博弈搜索的过程中，需要根 据推演中不同棋局下的不同走法进行模拟走棋和恢复还原，如何存储不同层次不同棋局下的走 法，这是一个值得讨论的问题。另个值得探讨的问题是，我们是不是真的需要产生所有棋子 的走法，并进行模拟走棋。对这个问题的研究或许可以从根本上解决四国军棋分支过多的难题。 如何识别关键棋子，如何在保证精简性的同时不会造成片面性的恶果，是这个问题研究的难点。 人机博弈程序的智能水平与博弈树搜索的深度有着最直接的联系。由于四国军棋的棋盘大， 行棋规则简单，使得四国军棋的走法很多，博弈树的搜索分支因而也非常庞大。四人游戏时， 四国军棋的一轮模拟实际上需要建立四层的博弈树。由于这些原因，限于目前计算机的处理能 力和存储能力，使得四国军棋的搜索深度有限。要提高四国军棋的智能水平，必须要根据四国 军棋游戏自身的特点设计高效的博弈搜索算法，及时剪去没必要扩展的节点，尽可能地提高博 弈搜索的深度。 估价函数是博弈程序的核心组成部分，博弈程序的智能水平与估价函数的准确性息息相关。 四国军棋估价函数的设计是四国军棋博弈程序中最困难的部分。这些困难性一方面来自于四国 军棋本身，四国军棋是不完全信息博弈游戏，玩家对于对手的棋子信息无法完全掌握，可能存 在的欺骗行为进一步加深了判断推理的难度：另一方面，我们对于四国军棋的基础性研究还不 够深刻透彻，对于棋子价值、棋子分布以及行棋中的一些信息分析都处于初等水平。 目前四国军棋人机博弈的研究已经有了一个良好的基础平台p 3 确】，建立了四国军棋的信息 推理机制3 6 1 ，并且根据四国军棋自身的特点设计和改进了四国军棋的搜索算法3 7 】【3 8 】。目前四国 军棋| 享弈程序存在的两个主要问题是：一、尽管已经改进了搜索算法，但是还是无法进行足够 深度的博弈搜索；二、没有一个好的估价函数。对于第一点，我们尝试用同样是人机博弈传统 技术的定式库技术来加以改善，减少人机博弈系统对博弈搜索的依赖，避免博弈程序因为搜索 深度不够而犯低级的战略错误。对于其中的第二点，目前还没有一个很好的解决方法，毕竟这 需要一定的时间积累和理论研究的不断推进，我们试图通过开局匹配来进行研究与分析。 1 2 定式库技术简介 1 2 1定式库技术概要 完全信息博弈技术经过半个世纪的探索和研究，创造了一系列的技术和方法，定式库技术 也是其中之一【2 9 】【3 9 】【4 0 1 。定式库技术广泛地应用于围棋的人机博弈系统。定式通常是指围棋中， 经过棋手长久以来的经验累积形成的在某些情况下双方都会依循的同定下法【4 。定式是一种让 下棋双方各自不吃亏的下法，也是下棋双方各自当前所能采取的最优策略【4 2 1 。在五子棋中类似 的固定下法也称作定式，由此推而广之，国际象棋、中国象棋中的开局库和残局库也可以看作 是广义上的定式库。开局库与残局库中记录的也都是下棋双方各自不吃亏的下法，是各自当前 6 、 南京航空航天人学硕士学位论文 的最优策略。同样的思路，可以将四国军棋中常见的特定局面以及对应的最优策略，作为定式 存储起来，形成四国军棋的定式库。定式库技术在四国军棋人机博弈程序中的应用可以减少博 弈搜索的次数，降低博弈程序对博弈树搜索的依赖。通过将某些局面下对应的战略最优策略存 入定式库，更可以避免博弈程序因为搜索深度不够而犯战略上的低级错误。 1 2 2 围棋定式库 围棋是一种完全信息博弈游戏，对弈的双方能够掌握当前棋局的所有信息，对于当前棋局 的认知是一致的。围棋的布局是一盘棋的轮廓，是一盘棋的关键所在，以后的策略变化都以其 为根基，其好坏直接影响到以后的中盘战斗以及全局的主动与被动。布局阶段非常重要的一个 环节就是定式的运用。所谓定式是指在布局阶段角部接触时双方认可的规范下法，是着法较为 合理，利益大致相当的局部定型。对于同棋的博弈程序来说，布局阶段棋局并不明朗，很难去 评价一个局面的好坏，如果单纯应用博弈树搜索技术往往会为了局部的小利益而造成战略上的 损失。定式是历代棋手智慧的结晶，每一个定式都凝聚着棋手的心血。将这些由围棋高手长期 经验积累而形成的局部定型存储起来，组成定式库，在游戏进行的过程中，通过检索定式库来 寻找匹配的定式以及对应的最优策略，这种最优策略生成技术被称为定式库技术。定式库技术 的应用避免了人机博弈系统在开局阶段犯战略上的错误。 围棋的定式库一般用有限状态机表示，可以采用z o b r i s t 哈希技术【4 3 1 进行编码实现。围棋定 式库一般通过下面的几个步骤进行实现【4 1 1 1 4 2 】： 1 ) 将围棋1 9 1 9 的棋盘的各个角部划分为1 0 1 0 的独立棋局。 2 ) 对各个独立棋局进行规格化处理：将每个独立棋局作旋转变换转化为棋盘的左上角， 同时对某些独立棋局作关于对角线的对称变换，以保证第一个棋子落于对角线的上方。 3 )用z o b r i s t 哈希技术对各个独立棋局进行编码，得到各个独立棋局的变换序列r = r i o ， r i l ，r i 2 ，对 。 4