计算机软件与理论硕士论文-基于数据库自学习的中国象棋研究.pdf

河北大学 硕士学位论文 基于数据库自学习的中国象棋研究 姓名：邢胜 申请学位级别：硕士 专业：计算机软件与理论 指导教师：王熙照;翟俊海 20090601 摘要 摘要 中国象棋的计算机博弈研究起步较晚，但是发展较快。到目前为止出现了许多优秀 的中国象棋软件，如许舜钦及其团队的“e l p ”、上海计算机博弈研究所黄晨的“象眼“ 等。但是这些象棋软件大多数是通过优化数据结构和改进搜索策略等方法提高棋力，虽 然也具有较高的博弈水平，但是有自学习能力的却很少。 本文通过引入数据库存储计算机判断失误的对手着法和局面值，从而使象棋软件能 够转变策略，避免再次的判断失误，实现自学习能力。 象棋博弈树搜索是中国象棋计算机博弈的关键技术之。但是博弈树的搜索在没有 记忆的情况下不能实现学习，而记忆要借助数据库来实现。付强在其论文中应用了数据 库记录计算机所走的最好着法和其局面值，并使用加强学习修改局面值以达到学习的目 的。 但是在象棋软件输棋的情况下，主要是由于对对手走棋判断失误造成的，所以记录 那些与计算机预想不同的对手着法和展开博弈树后的返回值，再从中选择造成输棋结果 的关键着法和值。当下次搜索到相同着法时，将数据库中该着法下的值取出，继续搜索 使象棋软件实现策略的转变，达到自学习的目的。 关键词数据库博弈树搜索零和公式关键着法自学习 a b s t r a c t a b s t r a c t t h er e s e a r c ho fc h i n e s ec h e s sc o m p u t e rg a m es t a r t sl a t e rt h a nc h e s s ，b u td e v e l o p s q u i c k l y s of a rt h e r e a r em a n ye x c e l l e n tc h i n e s ec h e s sp r o g r a m s ，s u c ha st h e “e l p d e v e l o p e db ys h u n c h i hh s ua n d h i st e a m ，t h e “e l e p h a n te y e d e v e l o p e db yc h e nh u a n ga n d s oo n m o s to ft h ee x i s t i n gc h i n e s ec h e s sp r o g r a m sa r ei m p r o v e dt h r o u g ho p t i m i z i n gt h ed a t a s t r u c t u r ea n di m p r o v i n gt h es e a r c hs t r a t e g y s e l f - l e a r n i n gp r o g r a m sh a v er a r e l ya p p e a r e d t h i st h e s i sp r o p o s e sam e t h o dt h a tc a nc h a n g es t r a t e g ya n da v o i dm a k i n gt h es a m e m i s t a k e st h r o u g hs e a r c h i n gt h ed a t a b a s ew i t l lw h i c hi ts t o r e st h eo p p o n e n tm o v e m e n t c o m p u t e rh a sm i s j u d g e da n dt h ep o s i t i o n v a l u e i no t h e rw o r d s ，i th a st h ea b i l i t yo f s e l f - l e a r n i n g g a m e - t r e es e a r c hi so n eo ft h ek e yt e c h n o l o g i e si nc h i n e s ec h e s sc o m p u t e rg a m e g a m e - t r e es e a r c hc a na c h i e v es e l f - l e a r n i n g 、析t l lad a t a b a s e f uq i a n gp r o d u c e dam e t h o d w h i c hu s e dd a t a b a s et or e c o r dt h eb e s tm o v e m e n ta n dp o s i t i o nv a l u e ，t h e na m e n d e dt h e p o s i t i o nv a l u eb yr e i n f o r c e m e n tl e a r n i n gt oa c h i e v et h ep u r p o s eo fs t u d y t h a tc h i n e s ec h e s ss o f t w a r el o s tg a m ei sm a i n l yb e c a u s eo ft h eo p p o n e n tm o v e m e n t c o m p u t e rh a sm i s j u d g e d i nt h i st h e s i s ，t h eo p p o n e n tm o v e m e n t sw h i c ha r ed i f f e r e n tf r o m w h a tc o m p u t e rf o r e c a s t sa n dt h er e t u l t lv a l u eo fg a m e t r e ea r er e c o r d e da n dt h ek e y m o v e m e n ta n dt h ev a l u et h a tc a u s ef a i l u r ea r ec h o s e n w h e nm e e t i n gt h es a m em o v e m e n t ，i t w i l lr e a dt h ev a l u eo ft h em o v e m e n ta n dc o n t i n u et os e a r c h i tw i l lc h a n g et h es t r a t e g ys ot h a t i ta c h i e v e st h ea b i l i t yo fs e l f - l e a r n i n g k e yw o r d s d a t a b a s eg a m e - t r e es e a r c hz e r o s u mf o r m u l a s e l f - l e a r n i n g ； i l 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名：i 率鱼生 日期：鲨! 窒年互月卫日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密a 。 ( 请在以上相应方格内打“ ) 保护知识产权声明 本人为申请河北大学学位所提交的题目为( 勘蝴序台c 翻的斗闯锄究 的学位论文，是我个人在导师( t - 熙熙) 指导并与导师合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人： 盈坚目生日期：丑年三月卫日 作者签名： 导师签名： 日期：堡2 年l 月卫日 日期：迥年丘月l 日 第1 章绪论 第1 章绪论 1 1研究背景和意义 机器博弈被认为是人工智能领域最具挑战性的研究方向之一也是最受公众关 注的研究领域之一。计算机博弈被普遍认为是人工智能的“果蝇”：因为人类对机器博 弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。 计算机博弈又主要以国际象棋的研究为主且历史悠久。由机器博弈的创始人香 侬教授提出为象棋博弈编程的方案到”深蓝”计算机的胜利说明了计算机博弈技术的 发展和成熟。由于中国象棋计算机博弈技术比国际象棋难度更高，吸引了不少计算 机博弈研究者将注意力转向了中国象棋。 中国象棋的计算机博弈研究起步较晚，但是发展较快。1 9 8 5 年，台湾大学的许舜钦 教授开始了全面的研究工作，随后对中国象棋计算机博弈的研究逐步展开。到目前为止 出现了许多优秀的中国象棋软件，如许舜钦及其团队的“e l p ”、中山大学涂志坚的“纵 马奔流”、东北大学的“棋天大圣”、上海计算机博弈研究所黄晨的“象眼”等。 目前，大多数中国象棋软件主要通过改进数据结构，提高计算机运行速度等方法提 高象棋软件的棋力，而很少有象棋软件有学习能力，这里的学习能力指象棋软件在下输 的情况下，对手重复着法，软件会转变策略，不再走失败的老路。而学习需要记忆和改 进，我们用数据库来做这项工作。在以往用数据库同搜索结合的方法中，数据库中记录 计算机走的好的着法，当下次碰到相同局面时，直接给出着法。这种方法并不能使象棋 软件具有学习能力，只是能够加快象棋的下棋速度，如同象棋软件中的开局库。 长沙理工大学的付强在其论文中应用了数据库记录计算机所走的最好着法和其局 面值，并使用加强学习修改局面值以达到学习的目的。 而象棋软件输棋的情况下，主要是由于对对手走棋判断失误造成的，所以选择造成 输棋结果的关键着法对于象棋软件的学习很重要，本文通过引入数据库存储计算机判断 失误的对手着法和局面值，再从中选择造成输棋结果的关键着法和值，从而使象棋软件 能够转变策略，避免再次判断失误，实现自学习能力。 河北大学t 学硕士学位论文 1 2 国内外研究现状 目前实现自学习能力的方法有以下几种： 1 应用加强学习 1 ) 加强学习同神经网络结合( r b p ) 2 ) 加强学习同数据库结合 3 ) 瞬时差分t d 算法 2 自适应遗传算法 3 二次估值法 4 博弈树同数据库结合 其中最主要的是应用加强学习的t d 方法。 1 2 1加强学习同神经网络结合( i m p ) 1 9 6 7 年，s a m u e l 的c h e c k e r s ( 西洋跳棋程序) 是增强学习在棋类中应用的意义最重 大的例子，它可能是最早的加强学习在棋类游戏中的应用。s a m u e l 经过几个不同版本的 c h e c k e r s 程序实验，该程序采用类似值迭代、瞬时差分和q 学习的训练机制，来学习用线 性函数表示的值函数，通过大量训练，使他的程序达到中等偏上的水平。 使用增强学习的棋类中最成功的就是g e r a l dt e s a u r o 在1 9 9 5 年推出的西洋双陆棋 t d g a m m o n 。它使用增强学习的方法训练由神经网络表示的评估函数，能够从零知识 纯粹靠自己和自己下西洋双陆棋与观察结果中进行学习，通过1 5 0 万盘棋的学习，最后 达到人类中世界冠军的水平。 在国际象棋方面，j o n a t h a nb a x t e r 通过把t d g a m m o n 中使用的方法同国际象棋的博 弈树结合形成了t d l e a f ( a ) 。t d l e a f ( a ) 被引入到象棋程序蹦g h t c a p 中，在3 天的3 0 8 盘对弈后使象棋程序的等级分由1 6 5 0 提高至u 2 1 5 0 ，相当于专家的水平。 国外也有将这种方法使用于中国象棋的研究，但是过于简化，变成一种状态十分有限 的游戏。首先，训练用的棋盘格式是缩减了的，只有4 4 格的范围，其次，棋子也只有马和 帅两个棋子，由马来将军，帅躲避。最后得到的结果是经过训练的由神经网络控制的马能 够主动地将军。 国内也有一些相关研究，王一非，哈尔滨工程大学硕士，2 0 0 7 年在其毕业论文中详 细的说明具有自学习功能的计算机象棋博弈系统的研究与实现。他建立一个9 0x 4 0xl 2 第1 章绪论 的b p 网络，输出层的节点数是1 ，其范围是从1 到+ 1 。并且约定隐含层和输出层的神经 元激活函数均使用s 型函数。使用线性编码即使用棋盘上每个交叉点所放棋子的固定子 力值作为输入，使用正负号区分红黑，空位用零表示。并提出了应用r b p 的缺点：神经 网络需要很大的运算量，自学习过程需要很长的时间，收敛时间过慢。 1 2 2 加强学习同数据库结合 长沙理工大学硕士付强2 0 0 6 年在基于激励学习的中国象棋研究中提到了使用加 强学习同数据库结合的方法实现中国象棋的自学习能力，通过数据库记录最好的着法， 并用加强学习修改局面值。经过2 万多盘的学习，已经下败了采用三层搜索的传统象棋 软件。 1 2 3 顺时差分t d 算法 1 9 9 9 年c h r i s s z e t o 的论文中，为了优化中国象棋中的参数，先将所有棋子子力值都 置为相同，配合a l p h a b e t a 搜索使用t d 算法通过自主学习修正的棋子子力值。在经过 2 5 0 盘游戏训练后，将得到的修正后的棋子子力值保存下来，使用相同的搜索引擎与走法 生成模块的前提下，与h t l a u 通过经验与试算估计得出的经典棋子子力值进行游戏， 取得了五局三胜一平一负的成绩，说明对棋子子力值的优化是成功的。 1 3 本课题研究的主要工作 通过阅读文献资料，利用数据库结合博弈树的搜索算法，实现中国象棋的自学习。 长沙理工大学的付强在其论文中应用了数据库记录计算机所走的最好着法和其评 估值，当下次遇到相同局面时，直接从数据库中读取着法。当计算机输棋时，使用加强 学习修改局面值以达到学习的目的。 我们想对这种方法进行改进。拟使用数据库记忆与计算机预想不同的对手的着法， 在计算机赢了情况下不作处理，只当计算机输棋的情况下，对对手实施着法后的局面进 行博弈树的搜索，将其值赋给刚才存储的着法上。当计算机下次搜索到这个局面时，直 接把值传给博弈树参与搜索。 这种方法与原方法相比，不用加强学习方法( 因为加强学习中的学习率是人为确定所以 存在主观因素) 就能使计算机在下输的情况下，重复原棋谱，会在关键步上做出战略调 整。从而实现象棋软件的学习功能。 河北大学t 学硕十学位论文 1 4 本文组织 全文的组织结构可以概括如下： 第1 章绪论。介绍计算机博弈的研究背景、意义和国内外研究现状。 第2 章计算机博弈关键技术的介绍。在简要阐述计算机博弈的基本思想后，对计 算机博弈的关键技术的四个主要方面进行了详细的论述。 第3 章论述传统的线性估值函数，并分析其意义和优缺点。提出了改进方法即用 零和公式代替传统估值函数。 第4 章提出用数据库同博弈树搜索相结合，实现象棋软件的自学习能力。 第5 章对提出的方案进行实验验证，通过对已有软件的改进来实现。 第6 章结论与展望。对所做的研究工作进行总结，并对今后的研究工作提出建议。 4 第2 章计算机博弈关键技术 第2 章计算机博弈关键技术 用计算机进行棋类博弈的历史始于上世纪五十年代，是从国际象棋的机器博弈问题 开始的。 早在计算机发展的初期，1 9 5 0 年s h a n n o n 就首先提出了为象棋博弈编程，让计算机 实现机器博弈的方案，s h a n n o n 也因此成为机器博弈的创始人。由于当时的计算机发展 水平比较低，直至1 9 5 8 年，才由i b m 推出了第一台能同人下棋的计算机i b m 7 0 4 。 i b m 7 0 4 每秒钟只能搜索2 0 0 步，甚至达不到初学者的水平，当时有人预言，计算机将 无法击败一位年仅1 0 岁的棋手。 随着计算机硬件水平的飞速发展和软件技术的不断进步，计算机棋手的能力稳步提 高。1 9 7 3 年，b s l m ea n d a t k i n s 开发出了c h e s s 4 0 程序作为国际象棋博弈程序的基础， 1 9 7 9 年国际象棋的软件4 9 达到专家级水平。1 9 8 3 年，k e nt h o m p s o n 开发了国际象棋硬 件b e l l e ，达到了大师水平。1 9 8 8 年，卡内基梅隆大学开发出的国际象棋软件“深思”击 败了丹麦特级大师拉尔森。1 9 9 7 年，i b m 推出的“深蓝”电脑击败了世界棋王卡斯帕罗夫， 成为计算机智能挑战人工智能发展的一个里程碑。 由此我们也可以看到国际象棋的计算机博弈技术已经比较完善和成熟了，而中国象 棋博弈软件的研究大多结合国际象棋取得的研究成果和本身独特的规则、特点来开发 的。 中国象棋的计算机博弈研究起步较晚，但是发展较快。1 9 8 5 年，台湾大学的许舜钦 教授开始了全面的研究工作，随后对中国象棋计算机博弈的研究逐步展开。到目前为止 出现了许多优秀的中国象棋软件，如许舜钦及其团队的“e l p ”、中山大学涂志坚的“纵马 奔流”、东北大学的“棋天大圣”、上海计算机博弈研究所黄晨的“象眼”等。 相比较国际象棋棋盘的8 行8 y u ，中国象棋有1 0 行9 列总计9 0 个交点，显然中国象棋 的运子空间更大。而且中国象棋的着法更为特殊( 如蹩马脚、压象眼等) ，棋局变化也更 加复杂，表1 显示的是国际象棋( c h e s s ) 、中国象棋( c h i n e s ec h e s s ) 、日本将棋( s h o g i ) 、围 棋( g o ) 几种棋类遍历搜索的复杂度对比，表中的数字为复杂度的自然对数值。很显然， 中国象棋比国际象棋更复杂。 河北大学t 学硕十学位论文 表1 1 几种棋类的空间复杂度及树的复杂度 棋类空问复杂度树的复杂度 c h e s s5 0 1 2 3 c h i n e s ec h e s s5 215 0 s h o g i 7 1 2 2 6 g o1 6 04 0 0 在各种棋牌博弈当中，象棋是一种完全知识博弈，即参与双方在任何时候都完全清 楚每一个棋子是否存在，位于何处。 首先了解中国象棋的博弈过程，中国象棋分为红黑双方，双方的走棋交替进行，都 想吃掉对方的“将”或“帅”，而又使自己尽量损失最少。图1 给出了象棋博弈状态演化过程 图 图2 1 象棋博弈状态演化过程图 s 表示的是棋局状态，s 0 表示初始状态，s f 表示终局，或红胜，或黑胜，或和棋。q 表示红方或黑方的着法( 下标奇数代表红方走棋，偶数代表黑方走棋) 。 着法便是弈棋者的决策，全部可能的走法是通过着法生成器给出的。当该计算机走 棋时，计算机会以当前局面为根将所有的可能走法一一展开，然而这只是一层树，计算 机要想看得更远，就需要分析对手的走棋，于是在以展开的结点为根继续展开，这就是 博弈树的展开过程。弈棋者按照这样的思维方式，必然展开一棵规模庞大的、根在上而 叶在下的博弈树。对博弈树的搜索采用极大极小搜索，是因为对弈双方都要寻找使自己 利益最大且又最能钳制对方的着法，这便形成了极大极小过程。当搜索到叶子节点时用 局面评估函数评估棋盘局面，按照极大极小的原则选出最优，向上回溯，给出这一局面 的父节点的估值，然后再继续向上回溯，一直到根节点，最佳走棋就是这样搜索出来的。 根据上面的计算机博弈基本思想，可以确定一个计算机博弈系统的一般构成。具体 包括以下几部分：棋盘的表示，着法生成，搜索算法，评估函数。 6 第2 章计算机博弈关键技术 2 1 棋盘的表示 通常，首先按照棋子类型给双方的棋子编码( 如表2 1 所示) ，接下来用一个二维数 组来描述棋盘及其上棋子的信息。例如，可以用一个9 x 1 0 大小的二维数组来表示中国 象棋的棋盘，数组中每一个元素代表棋盘上的一个交点，其值表明这个交点上放置的是 一个什么棋子或是没有棋子，如图2 1 所示。 表2 1 中国象棋棋子编码 编码 l23 4 567 棋子黑将 黑车黑码黑炮黑士 黑象 黑卒 编码 891 0】l1 2 1 31 4 旗子红帅红牟红马红炮红仕红相红兵 e 口口蚤口务o 勺0 一+ 一十斗- 斟拿一卜斗一：- 一- l l 9 寸平十二 _ _ 勺一 分令斗令十9 9 ililll - 一上一j 一一j 一一上一一上一一l 一上一一 l訾罄 麓河 | 2 35 6165 32 o o o 0 o 0 o 00 o 40o0 0o 4 o 7 o 7 0 7 o 7 0 7 ooo000o 00 o o 0 oo0oo o 1 4o1 401 401 401 01 1 oo0 0o1 lo 0 o 0 o o o 00 o 91 01 2 1 3 8 1 3 1 21 09 图2 1 象棋棋盘及表不数组 设计一种数据结构来表示一种棋类游戏的状态往往要考虑三个方面的问题：l 、占用 的空间数量2 、操作速度3 、使用方便与否。紧凑的数据表示会赢得空间上的优势，这 往往也伴随着时间上的优势。复制3 2 个字节的棋盘信息无疑会快于9 0 个字节的棋盘， 但这并不意味着所有的运算和操作都会更快。使用3 2 个字节的数据表示，程序员在确 定一个棋子的位置时往往需要增加额外的移位操作以取出一个字节中含有的两个坐标 信息。 2 2 着法生成 走法产生是指将一个局面的所有可能的走法罗列出来的模块，也就是告诉其他部分 7 t 妙+ 业鸯一|00p扣l梦一|下卡击l_匆寸斗=科脚h 河北大学工学硕士学位论文 下一步可以往哪里走的模块。由于各种棋类规则的不同，走法产生的复杂程度也有很大 的区别。以中国象棋为例，假定现在有一个轮到红方走棋的局面。要列举出红方所有合 乎规则的走法。首先扫描棋盘，如果某一个位置上是一个红方棋子，则根据该棋子的类 型找出该棋子的所有可走位。比如象只可以走田字，马只可以走日字，兵不可后退只能 前进一步，用棋盘扫描法就要根据棋子的具体走法在棋盘上扫描有效区域。预置表法也 是最经常使用的着法生成方法，它的基本思想就是时间换空间的思想为了节省博弈过 程中的生成着法的扫描时间，将动子在棋盘任何位置、针对棋子的全部可能分布，事先 给出可能的吃子走法和非吃子走法的关系写入个预置表中，再通过查表，便很快可以 得到可行的着法，虽然这样需要占用一定的空间，但相对现在的硬件环境应该说还是可 以接受的，它可以将着法生成的速度提高几个数量级。 在进行走法产生的时候，往往伴随着搜索进行。对于一个局面的所有直接后继，你 可以有两种选择：一次产生一种走法然后搜索之：或者一次产生其所有走法然后搜索之。 由于存在着剪枝算法，对一个局面的某一走法搜索之后往往可能不再需要搜索其他后 继，也就是说：可能不用产生全部走法就能够完成搜索。一次产生一种走法看起来似乎 更有效率。但是，由于剪枝算法的剪枝效率很大程度上依赖于节点的排列顺序，往往一 次产生所有节点，然后以某种方法调整其排列顺序会使搜索效率大大提高。所以，在实 际使用中，绝大部分程序都是一次产生一个局面的全部走法，然后调整其搜索顺序。 2 3 搜索算法 计算机国际象棋对弈是一种双人完备信息的博弈过程，其核心思想并不复杂，实际 上就是对博弈树节点的估值过程和对博弈树搜索过程的结合。博弈程序的任务就是对博 弈树进行搜索找出当前最优的一步走棋。对博弈树进行极大极小搜索，可以达到这一目 的。极大极小搜索，是因为博弈双方所要达到的目的相反，一方要寻找的利益恰是一方 失去的利益，所以博弈的一方总是希望下一走棋是儿子节点中取值最大者，而另一方恰 恰相反，这便形成了极大极小过程。整棵博弈树非常庞大，且不同棋类有所不同，分支 因子大的如围棋的博弈树显然要比分支因子小的如国际象棋的博弈树要大得多，所以， 不能也没有必要做到搜索整棵博弈树的所有节点，对于一些己经确定为不佳的走步可以 将以它为根节点的子树剪掉。而且，搜索也不必真的进行到分出胜负的棋局，只需要在 一定深度范围内对局面进行评估即可。只有搜索空间缩小到一定程度，搜索才可以真正 8 第2 章计算机博弈关键技术 的进行。当搜索进行到一定深度，用局面评估机制来评估棋盘局面，按照极大极小的原 则选出最优，向上回溯，给出这一局面的父节点的估值，然后再继续向上回溯，一直到 根节点，最佳走棋就是这样搜索出来的。 在这个过程中，最为重要的是搜索算法，高效的搜索算法可以保证用尽量少的时间和 空间损耗来达到寻找具有最佳值的走步。但是真的想要提高博弈程序的棋力，还必须有 一个好的局面评估机制，即估值算法作后盾。就是说，用这个估值算法评估的局面价值 必须是客观的、正确的，可以准确的评估局面的优劣以及优劣的程度。 2 3 1博弈树的基本概念和思想 它与一般决策树的不同点则在于它的决策主体不是一方，而是相互对立的双方，即 红方和黑方。图2 2 就是一个博弈树的结构。 图2 2 展开的4 层博弈树 图中方节点代表轮到红方走棋的状态，圆节点代表轮到黑方走棋的状态。节点间的 连线便对应于一个个着法。博弈树上的每一个节点都代表一个棋局，根节点是当前时刻 的棋局，它的儿子节点是假设再走任一合法着法得到的各种局面，孙子节点是在儿子节 点的局面下让对方行一步棋得到的各种棋局，以此类推，构造整棵博弈树，棋手就是要 在众多的叶子节点上挑选一个评价最好的局面作为自己的选择，从而反推得到当前的着 法。像这样从根部向下递归产生的一棵包含所有可能的对弈过程的搜索树，成为完全搜 索树。此过程类似于在一个状态图中寻求从初始状态通向终了状态的过程。只是状态图 搜索仅有一个主体参加，仅是单方面做出的路径选择。而博弈树的搜索则有对立的双方 参加，一方只能做出一半选择，而这半选择的目的是使对方远离其竭力靠近的目标。 也就是说状态图搜索是纯粹的或树( o r t r e e ) ，而博弈树搜索是与或树( a n d o r t r e e ) 。像 q 河北大学工学硕十学位论文 这样的完全博弈树非常庞大，在实际的情况下，由于建立完全博弈树在理论上是可行的， 但是由于具体棋类的分枝因子很大，盲目搜索所能达到的层数十分有限，所以不可能建 立到棋局的结束，搜索也不必真地进行到分出胜负的棋局，只需要在一定深度范围内对 局面进行评价即可。于是搜索的目标便成为如何在有限深度的博弈树中找到评估值最高 而又不剧烈波动的最佳状态，所谓“不剧烈波动”就是说最佳棋局不是在进行子力交换与 激烈拼杀的过程当中当搜索进行到一定深度，用评估函数来评价棋局，按照极大极小的 原则选出最优，向上回溯，一直到根节点，最优走步就是这样搜索出来的。 2 3 2 极大极小值算法 香农( c l a u d es h a n n o n ) 教授早在1 9 5 0 年首先提出了“极大极小算法”( m i n i m a x a l g o r i t h m ) ，从而奠定了计算机博弈的理论基础。极大极小值搜索算法 ( m i n i m a x a l g o r i t h m ) 是解决博弈树问题的基本方法。假设红方为电脑走棋方，它的着法选 择是要在其全部子节点中找到评估值最大的一个，即实行“m a x 搜索”而对方黑方 在奇数层的着法选择则是在其全部子节点中要找到评估值最小的一个，即实行“mi n 搜 索”这便形成了极大极小过程。在象棋博弈中，极大极小值算法体现在始终站在博弈一 方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方 ( 有利于另一方) 的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间价值 分数。在这一方行棋的时候，选择价值极大的儿子节点走步，另一方行棋则选择价值极 小的儿子节点走步。这就是象棋博弈当中的一个极大极小过程。 2 3 3 负极大值法 负极大值法是对极大极小值算法的一种优化，它仅仅是一种更好的表达形式，负极 大值算法的核心在于：父节点的值是各子节点的值的负数的极大值。极大极小值算法总 是一方试图取极大值而另一方试图取极小值，也就是说，总是要检查哪一方要取极大值 而哪一方又要取极小值，进而执行不同的动作。k n u t h 和m o o r e 在1 9 7 5 年提出了负极大 值( n e g a m a x ) 方法，消除了两方的差别，而且简捷清楚。那么使用负极大值法，博弈的 双方都取极大值。以下是负极大值算法的代码( 并给出相应的注释) ： i n tc n e g a m a x e n g i n e ：n e g a m a x ( i n td e p t h ) i mc u r r e n t = 2 0 0 0 0 ； i ms c o r e ； 1 0 第2 章计算机博弈关键技术 i n tc o u n t ，i ； b y t e t y p e ； i = i s g a m e o v e r ( c u r p o s i t i o n d e p t h ) ； i f ( i ! = 0 1 r e t u r ni ； i f ( d e p t h e v e l u a t e ( c u r p o s i t i o n ，( m _ n m a x d e p t h d e p t h ) 2 ) ； c o u n t = m _ _ p m g 一 c r e a t e p o s s i b l e m o v e ( c u r p o s i t i o n ，d e p t h ，( m _ n m a x d e p t h - d e p t h ) 2 ) ； f o r ( i - o ；i m _ m o v e l i s t d e p t h i ) ； s c o r e = - n e g a m a x ( d e p t h 1 ) ； u n m a k e m o v e ( & m _ p m g 一 m _ m o v e l i s t d e p t h i ，t y p e ) ； i f ( s c o r e c u r r e n t ) c u r r e n t2s c o r e ； i f ( d e p t h = = = m _ n m a x d e p t h ) m c m b e s t m o v e = m _ _ p m g - m _ m o v e l i s t d e p t h i ； ) ) r e t u r nc u r r e n t ； 2 3 4 a l p h a b e t a 搜索算法 上述的极小极大值搜索过程中，遍历了整棵的博弈树，每一个节点都访问了一次， 然后尽可能选择最好的线路。这样的搜索算法虽然好理解，但效率非常低，搜索量非常 大。每次搜索更深一层时，树的大小就里指数式增长。例如六层搜索的局面就接近二十 亿个，而十层的搜索就超过两干万亿了。以目前计算机的运行能力，最小最大搜索方 法无法做到很深的搜索，因为有效的分枝因子实在太大了。 在实际的博弈过程中，人类一般不会去考虑那些没有意义的走法。比如，很少有人 河北大学t 学硕士学位论文 会在开始的步法内去移动“将”，“士”等棋子。所以也可以让计算机去模拟人类这种行为， 达到分析较少的节点仍能得到最优解的情况。这里就要通过去除那些冗余的数据来减少 数据量。 c i 鲰坎 m a x m i n m a x 图2 3a 舅枝 图2 3 所示的是一棵a 剪枝的片断，首先从前三个叶子节点中选出最小值4 传到父 亲节点，由于根节点的第二个分支的叶子节点2 2 ，一定不会取到第二个分支，所以 把第二个分支剪掉，第三个分支同样被剪掉。 bj 舛车立 1 v i i n 图2 41 3 舅枝 不同于0 c 剪枝，p 剪枝是奇数层取最小值，偶数层取最大值。图2 4 所示的是p 剪 枝的片断，剪枝的原理是相似的。 a l p h a b e t a 搜索可以省略许多节点的搜索。对于每一个被省略的节点实际上节点下 面的子树也被忽略掉了。所以a l p h a b e t a 搜索的节点远少于极大极小算法所遍历的节 点。这也意味着对搜索同一棵树来说，a l p h a b e t a 搜索所花费的时间比极大极小算法更 少。1 9 7 5 年k n u t h 和m o o r e 给出了a 1 3 正确性的数学证明。a 1 3 剪枝算法的节点数目如 公式2 1 和2 2 所示。 n d = 2 b 驯2 - 1d 为奇数 ( 2 - 1 ) n d = 2 b d + 1 7 2 + b d _ 1 坨一1 d 为偶数 ( 2 - 2 ) 1 2 第2 章计算机博弈关键技术 其中d 为搜索深度，b 为分枝因子。在不使用0 c p 剪枝时，需要搜索的节点数目是 n d = b d 。所以最理想情况下q p 剪枝算法搜索深度为d 的节点数相当于搜索深度为 d 2 的不做任何剪枝节点数。王晓春通过实验比较了q - p 搜索和负极大值搜索( n e g a m a x ) ， 表3 和表4 是两者在时间消耗和搜索节点数目上的比较： 表2 2 a l p h a - b e t a 和负极大值引擎每走一步的平均时间花费m s 酞星鍪 1 层2 层3 层4 层 n e g a m a x l3 01 2 4 04 4 6 6 0 a l p h a b e t a 11 02 0 01 9 4 0 表2 3a l p h a - b e t a 和负极大值引擎每走一步的平均叶节点数目 心星鍪 l 层2 层3 层4 层 n e g a m a x 4 51 5 0 06 8 0 4 52 4 1 6 2 3 4 a l p h a - b e t a 4 55 1 01 0 5 3 71 0 3 4 5 7 以下是a p 剪枝算法的c 伪码： i n ta l p h a b e t a ( n p l y , n a l p h a ，n b e t a ) i f ( g a m eo v e r ) r e t u r ne v e l u a t i o n ；胜负已分，返回估值 i f ( n p l 尸o ) r e t u r ne v e l u a t i o n ；叶子节点返回估值 i f ( i sm i nn o d e ) 此句用于判断当前节点是何种节点 是取极小点的节点 f o r ( e a c hp o s s i b l em o v em ) 对每一可能的走法m m a k e m o v em ；生成新节点 s c o r e = a l p h a b e t a ( n p l y 一1 ，n a l p h a ，n b e t a ) 递归搜索子节点 u n m a k em o v em ；撤销搜索过的节点 i f ( s c o r e = n 1 3 e t a ) r e t u r nn a l p h a ；a l p h a 剪枝，抛弃后继节点 洞北大学t 学硕士学何论文 ) ) r e t u r nn b e t a ；返回极小值 ) e l s e 取极大值的节点 f o r ( e a c hp o s s i b l em o v em ) 对每一可能的走法m m a k em o v em ；生成新节点 s c o r e = a l p h a b e t a ( n p l y 1 ，n a l p h a , n b e t a ) 递归搜索子节点 u n m a k em o v em ；撤销搜索过的节点 i f ( s c o r e n a l p h a ) 取极大值 n a l p h a = s c o r e ； i f ( n a l p h a - - l l b e t a ) r e t u r nn b e t a ；b e t a 剪枝，抛弃后继节点 ) ) r e t u r nn a l p h a ；返回极大值 ) ) 2 4 估值函数 上述提到的搜索算法搜到的值就是使用评估函数对叶节点局面的估值。估值函数是 对棋局的综合评估，它在很大程度上依赖于具体的经验知识。传统的评估函数考虑棋局 的很多方面，诸如各棋子子力价值，棋子的灵活度，棋子受到的威胁和保护，棋子之间 的配合等等。最后的评估值就是这些因素的多项式和。我们将在下一章详细描述传统评 估函数及其对它的改进。 2 5 本章小结 本章是对整个博弈系统的组成做了一个简要的和当前的基础理论进行论述，同时， 1 4 第2 章计锋机博弈关键技术 也为后面章节论是什么棋类，一个博弈系统主要由以上几个部分子表示、走法生成、搜 索算法和估值函数。对于棋有很多种表示方法，但是其本质都是一样的，即使示建模； 走法的生成，就是罗列出所有可能的走法走的棋盘位置，为了加快速度，也可以用预置 表法的部分，但所有的优化都是在基础的极大极小搜索弈系统的核心，也是本文的重要 研究要点。 河北大学工学硕士学位论文 第3 章评估函数的改进 在中国象棋对弈中，如果计算机能够穷尽所有的情况，那么只通过搜索就能够得到 最好的走步，但是由于不可能穷尽所有的情况，所以搜索的深度是有限的。当搜索到一 定深度时，对节点要进行优劣的判断，于是需要对一定深度的叶子节点进行评估。即用 估计值代替实际的搜索，传统的评估方法一般都采用静态评估函数。 3 1评估函数的主要因素 由于搜索引擎不能搜索到棋局分出胜负的情况，所以对一定深度的局面进行评估显 得十分重要，评估函数要客观公正地给出评价，而这些在很大程度上依赖于具体的游戏 规则和该游戏的经验知识，但是有些知识并不十分可靠。例如，传统来说“炮”的子力价 值大于“兵”的价值，但是在大师的手中，“兵”有着不次于“炮”的作用。评估函数要考虑 的情况很多，传统的方法包括以下几个因素： ( 1 ) 棋子的价值：就是棋盘上评估双方都有哪些棋子在棋盘上，对于不同的棋子给出不 同的值，例如可以让一个兵的价值为1 0 0 ，一个炮的价值为3 0 0 ，一个车的价值为5 0 0 等等。将的价值为无限大( 通常用一个远大于其他棋子的数) 。这些值反映了一个棋局最 基本的情况。一方的棋子价值总值就是该方棋盘上现有棋子的子力价值之和。表5 即为 中国象棋各棋子的子力值： 表5 中国象棋各棋子子力值 l 丘 炮马 奎 相 士 将 l 、 i 3 0 03 5 0 3 5 05 0 02 5 02 5 01 0 0 0 ( 2 ) 棋子的位置：对于同样的一个棋子，处在棋盘的不同位置它的价值也是不同的。例 如一个兵，没有过河之前，它的作用并不大，所以它的位置评估值在自己的半个局面里 比较低，但是兵过河后，它越靠近九宫，它的位置值就越大。如图3 1 是兵的位置评估 值。 1 6 第3 章评估函数的改进 0 3 691 2 9 630 1 83 6 5 68 01 2 08 05 63 61 8 1 42 64 26 08 06 04 22 61 4 1 02 03 03 44 03 4 3 02 01 0 61 21 81 82 01 81 81 26 20 8 0 80802 00 2040 200 0 0 0000000 000000000 ooooooo0o 图3 1 兵的位置评估值 ( 3 ) 棋子的灵活度评估值，棋子的灵活性是指棋子的活动范围，就是棋子可走步数的多 少。一个棋子的活动能力越强，其价值越高，因为棋子可移动的步数越多，那么它可逃 避攻击的范围越大。每个棋子对于每一可走步相应地给出一固定值。这个棋子灵活性， 就是它所有合法走步数目乘上这一固定值得到的。表6 给出了每个棋子每一步的灵活度。 表6 每个棋子每一步的灵活度 l丘 炮马 查 相士 将 、 1 561 2 611o ( 4 ) 棋子关系评估值，棋子间的关系包括对弈双方棋子之间的威胁，己方棋子之间的保 护和配合。在不同关系下，评估值也要相应变化。当受到敌方棋子威胁的棋子，其价值 就要相应降低。受到己方棋子保护的棋子，其价值要相应升高。一些由棋子组成的某些 形状一般被认为是安全的，以中国象棋为例：如连环“马”，双“相”连环。组成该形的棋 子价值应增大。 ( 5 ) 定势。一些特殊的形势应作为特例予以识别，并赋予准确的估值。以中国象棋为例： 如双“炮“ 将军，在许多情况下就是将死了的，应返回极值，但仅使用一般的规则估值 则仅仅认为只是一个“炮”将军。 上述几点因素综合起来构成了一个比较客观的评估函数。一般是将上述诸元以一个 多项式的形式结合起来。假定价值及灵活性等诸元用x 、y 、z 、k 等变量表示。而每种 因素在估值函数中所占的比重为a 、b 、c 、d ，则总的估值就为： s c o r e = 统y + b y + c z + 矗k ( 4 1 ) 对于一方棋子价值，对应的式子公式( 4 2 ) 如下： x = 嗨+ v 马+ v 炮+ v 妻 ( 4 - 2 ) 其中，v 车，v 马，v 炮分别对应车、马、炮等的价值。 1 7 河北大学t 学硕十学位论文 公式( 1 ) 只是构成了一方的价值总和。因为中国象棋有红方和黑方，所以一个局面的 总估值v a l u e 就是红方和黑方的价值差。如公式4 3 所示： v = v a l u e 陀d v a l u e 6 ，口以( 4 3 ) 局面总的评估值再结合搜索算法就可以对树进行搜索。显然，总值为正对我方有利， 负值对对方有利绝对值的大小说明双方棋势的差距评估