资源描述：
《中国象棋计算机博弈系统评估函数的自适应遗传算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第26卷第10期东北大学学报(自然科学版)Vol126,No.102005年10月JournalofNortheasternUniversity(NaturalScience)Oct.2005文章编号:100523026(2005)1020949204中国象棋计算机博弈系统评估函数的自适应遗传算法实现王 骄,王 涛,罗艳红,徐心和(东北大学信息科学与工程学院,辽宁沈阳 110004)摘 要:使用自适应遗传算法解决中国象棋计算机博弈问题·将博弈问题分解为搜索引擎、走法生成、评估函数和开局库四大模块,然后将自适应遗传
2、算法引入到评估函数中,通过锦标赛算法对评估函数中的参数组合进行自动调整和优化·设计并开发了基于上述方法的离线自学习系统,实验结果证明提高了程序的棋力·关 键 词:中国象棋计算机博弈;博弈树;评估函数;锦标赛算法;自适应遗传算法中图分类号:TP181文献标识码:A在过去的半个世纪里,世界各地的学者花费点和根节点之间的最大距离,称为搜索深度·整个了大量的心血对于计算机博弈包括奥赛罗、博弈树描述的是从当前局面出发,包含所有可能checker、国际象棋进行研究·这是因为计算机博的对弈过程的搜索树·中国象棋计算机博弈问题弈是人
3、工智能的一块试金石,各种搜索算法、模式也就转化为寻求最佳路径的问题·识别及智能方法在计算机博弈中都可以得到广泛对于树中的每一个节点来说,红黑双方都会的应用·在长时间的研究中,涌现出大量令人震惊从子节点中选择最有利于自己的分枝·因为博弈的成果,1997年“深蓝”战胜卡斯帕罗夫的比赛就树中值的传递是由下至上的,这就要求对叶子节在全世界范围内引发了震动·在以上的三种棋类点表示的局面必须有一个极为准确的打分·对于中,计算机的水平都已经达到了世界冠军的水平·局面最为准确的估计莫过于已经分出胜负的情近年来,中国象棋计算机博弈也逐
4、渐引起众况,即建立在叶子节点分出胜负的完全博弈树·多学者的关注,这是因为中国象棋是世界上历史144中国象棋的完全博弈树大概有10个节点,建最为悠久的棋类,而且它的空间复杂性和树的复立这个博弈树已经远远超出了当代计算机的处理[1]杂性都要高于以上的三种棋类·能力·惟一的解决方法就是让博弈树扩展到计算机运算可以接受的深度,然后对没有分出胜负的1 中国象棋计算机博弈问题描述叶子节点给出一个最为准确的打分,表示此局面中国象棋计算机博弈可以分解为4个主要部下取得胜利的可能性·[2]分:搜索引擎、走法生成模块、评估函数和开局Va
5、lue=ComputerValue-UserValue库·如果Value为正数,说明局面对电脑有利,为几乎所有的棋类问题,都可以用博弈树来描负则对用户有利·[3]述·博弈树是把计算机和用户所有可能走法和Value这个打分是由评估函数计算得到的·局面罗列出来的一颗树·红黑双方交替地按合理而按照中国象棋的走法规则生成合理走法将树展走法把树展开,树的每一个节点都表示某一个特开,是走法生成模块的功能·搜索引擎则是尽可能定局面·根节点表示的是当前需要计算的局面,中缩小树的规模,避免一切冗余的计算·间节点表示的是对弈过程中的某一
6、个局面,叶子开局库是独立于博弈树之外的模块[4],开局节点是树的最底端,表示可以推导的局面·叶子节库存储了大量的专家棋谱,如果根节点的局面在收稿日期:2005202201基金项目:国家自然科学基金资助项目(60475036);教育部博士点基金资助项目(20040145012)·作者简介:王 骄(1978-),男,辽宁沈阳人,东北大学博士研究生;徐心和(1940-),男,辽宁沈阳人,东北大学教授,博士生导师·950东北大学学报(自然科学版) 第26卷开局库可以查询到,则提取开局库的对应走法而2.2
7、适应度函数的计算锦标赛算法不必展开树·可以避免在开局时由于搜索深度的众所周知,遗传算法在进化搜索中基本不需不足而带来战略上的失误·要外部信息,仅以适应度函数(fitnessfunction)为评估函数是模式识别和智能算法应用最为广依据,利用种群中每个个体的适应度函数来进行泛的领域·不管多么复杂的评估函数,都可以表示搜索·一般而言,适应度函数是由目标函数变换而为一个多项式·评估函数一般来说必须包括5个成的·但是象棋的评估比较复杂,很难像一般优化[1]方面的要素,分别是固定子力值、棋子位置值、问题那样找到真实准确的目标函
8、数,因此本文设棋子灵活度值、威胁与保护值、动态调整值·每一计了一个专门用于棋类优化问题的适应度函数计方面的值又是由许多参数值构成的,例如固定子算方法锦标赛算法·力值就包括7类棋子的值·即使最简单的评估函首先,要对自己开发的计算机博弈软件进行数也有20多个参数,将这些值线性地组合在一起拓展,拓展后的程序包含了两个评估函数,但是搜得到最终的评估值,
