56基于剪枝策略的中国象棋搜索引擎研究

河北大学硕士学位论文基于剪枝策略的中国象棋搜索引擎研究姓名：裴祥豪申请学位级别：硕士专业：计算机软件与理论指导教师：王熙照;翟俊海20090501://://://://://://://://://://://://://://://://://://://://://://://://://://://://://://://基于剪枝策略的中国象棋搜索引擎研究作者：裴祥豪学位授予单位：河北大学相似文献(10条)1.会议论文褚泽永.黄鸿.黄远灿浅析中国象棋计算机博弈关键技术2006中国象棋计算机博弈的出来的关键技术是搜索算法和评估函数.其中搜索算法大多都是从α-β剪枝算法衍生出来的.α-β剪枝算法体现了人的思维方式;同样,在评估函数的设计中采用了人工智能方法.随着计算机技术的发展,机器的计算能力再加上模拟人类思维的算法,使得在中国象棋博弈中人类最终很难战胜机器.同时,中国象棋计算机博弈的研究对人工智能的发展也起到了推动作用.2.学位论文王骄中国象棋计算机博弈关键技术研究2006人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。计算机博弈是人工智能领域中一个重要的课题，国际象棋计算机博弈已经取得了巨大的成功，而中国象棋计算机博弈却远远落后。“棋天大圣”是东北大学人工智能与机器人研究所自主开发的中国象棋计算机博弈软件，取得了第11届世界电脑象棋奥林匹克竞赛中国象棋组的冠军。本文通过结合“棋天大圣”的研究成果，阐述了一个可以达到人类特级大师水平的中国象棋程序的设计和实现原理。本文对中国象棋计算机博弈的关键技术进行了分析和介绍，并提出了一些新的思想和算法，以及基于数据测试集的分析和检验。其中包括以下几点。第一，介绍了中国象棋状态空间的数据表示方法，介绍了对状态空间的数字表示和布尔表示，提出了用棋盘编码数组、棋子编码数组、映射数组数字表示状态空间，用新型数据结构路向行向比特向量与比特棋盘相结合布尔表示状态空间的新方法。在这些描述方法共同作用下，程序具有很高的运行效率，大大节省了计算时间。第二，详细介绍了当今流行的各种着法生成算法，提出了路向行向比特向量与模板法相结合，并且辅以预置表作为辅助进行着法生成的新方法。着法生成的速度获得很大的提升。第三，介绍了棋类搜索领域的搜索算法及其分类，给出了多种搜索算法的融合方式，以及在中国象棋计算机博弈领域应用的创新。第四，结合“棋天大圣”的审局函数，介绍了审局函数的概念、组成和计算的方法。提出了小子同形表这种新的计算方法，可以对引擎起到良好的加速作用。第五，本文就开局库的原理做出了介绍，提出了理想开局厍并做了深入的探讨。对开局库自学习算法原理和成果进行了总结。第六，提出了残局处理系统的新概念，将残局处理系统划分为残局知识库与残局数据库。对自行设计的残局知识库的原理、结构、实现方法做出了详细的介绍。第七，创造性地将自适应遗传算法、神经元网络结合TD(λ)算法两种机器学习算法引入审局函数中，详细的介绍了与审局函数的结合、测试的方法以及取得的成果。本文的研究在中国象棋计算机博弈领域处于前沿，结合本文的研究成果可以创建高水平的博弈软件，而且在一系列电脑之间的比赛和人机挑战赛中，也得到了印证。本文的成果和结论，对于其它中国象棋计算机博弈程序，具有一定的参考价值。3.期刊论文徐心和.王骄.XUXin-he.WANGJiao中国象棋计算机博弈关键技术分析-小型微型计算机系统2006,27(6)机器博弈被认为是人工智能领域最具挑战性的研究方向之一.国际象棋的计算机博弈已经有了很长的历史,并且经历了一场波澜壮阔的搏杀,深蓝计算机的胜利也给人类留下了难以忘怀的记忆.中国象棋计算机博弈的难度绝不亚于国际象棋,不仅涉足学者太少,而且参考资料不多.在国际象棋成熟技术的基础上,结合在中国象棋机器博弈方面的多年实践,总结出一套过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点,最后提出了当前研究的热点与方向.4.学位论文王涛中国象棋计算机博弈中的增强学习研究2006计算机博弈曾一直被称为是人工智能研究的“果蝇”，但对于有几千年历史的中国象棋的计算机博弈的研究却远远落后于其它棋类，为了改变这种局面，东北大学成立了“棋天大圣”中国象棋计算机博弈代表队。论文选题正是来源于在队内所做的研究工作。为了解决传统的线性评估函数对中国象棋局面的评估不够精确的问题，本文提出了两个解决方案：一个是使用TD(λ)增强学习算法优化传统的线性评估函数的可调参数；另一个是使用人工神经元BP网络替代传统的线性评估函数，然后使用TD(λ)算法训练该网络。一个中国象棋增强学习系统被设计用来实现这两个方案的学习过程。在该系统中可以使用TD(λ)算法进行四种形式的学习：专家棋谱数据库学习，自学习，固定对手学习和网络对战学习。为了验证学习的效果，设计了一个连线器用于将本系统连接到Internet上的一个网络对战平台—弈天棋缘，通过在网上擂台的等级来评价学习后的棋力提高程度。实验表明，使用TD(λ)算法训练BP网络的方案潜力巨大，值得进行更深入的研究；使用TD(λ)算法优化线性评估函数的方案实施效果很好，可以大大提高系统的棋力。5.会议论文王骄.徐长明.徐心和中国象棋计算机博弈残局处理系统2006残局是中国象棋计算机博弈面临的一个难点,为了加强引擎在残局时的棋力,重点研究了残局处理系统,引入了残局知识库与残局数据库概念,介绍了残局知识库的入口、出口、内部实现以及对搜索的影响和在中国象棋计算机博弈中的实现问题.6.期刊论文王骄.王涛.罗艳红.徐心和.WANGJiao.WANGTao.LUOYan-hong.XUXin-he中国象棋计算机博弈系统评估函数的自适应遗传算法实现-东北大学学报（自然科学版）2005,26(10)使用自适应遗传算法解决中国象棋计算机博弈问题.将博弈问题分解为搜索引擎、走法生成、评估函数和开局库四大模块,然后将自适应遗传算法引入到评估函数中,通过锦标赛算法对评估函数中的参数组合进行自动调整和优化.设计并开发了基于上述方法的离线自学习系统,实验结果证明提高了程序的棋力.7.学位论文何玉林瞬时差分方法在中国象棋计算机博弈中的应用2009与国际象棋相比较，中国象棋具有更大的棋子运动空间，并且中国象棋的着法更加特殊、棋局变化也更加复杂。在中国象棋计算机博弈中，对于设计一款优秀的博弈软件而言，最费时的就是评价函数的实现与调整。br　　在本文中，我们使用三层的全连接前馈式神经网络表示评价函数，瞬时差分方法是一种增强学习算法，它利用相邻状态之间的状态值之差逐步地更新值函数的权值。基于单输出的神经网络，通过将TD（λ）算法引入到中国象棋计算机博弈中，我们推导出了一套新的神经网络权值更新规则。我们使用专家棋谱作为训练样例，并利用新权值更新规则完成对网络的更新。br　　在训练神经网络的过程中，每份专家棋谱被重复地学习，直至评价函数对专家棋谱中每个局面给出的评价值达到稳定。通过实验验证，我们学习到的评价函数是可行有效的。并且，我们获得了评价函数的表现与三种参数之间的关系：评价函数表现与神经网络隐含层节点个数之间的关系、评价函数表现与学习率α之间的关系、以及评价函数表现与参数λ之间的关系。8.会议论文王骄.王愿博.王晓鹏中国象棋计算机博弈着法生成研究2006着法是博弈树展开的依据,着法生成的效率直接决定了博弈树的展开速度,对搜索引擎的效率影响巨大.本文就中国象棋计算机博弈中常见的着法生成方法做了介绍和分析,其中包括棋盘扫描法、射线法、路向行向比特向量法、模板匹配法、位棋盘法等,并就各种方法的优缺点做了对比与总结.9.学位论文郭峰中国象棋计算机博弈中的判别剪枝搜索研究2009本文作者针对中国象棋的计算机博弈存在一些问题，提出了一种利用象棋大师知识的新搜索剪枝算法，相关实验证明该方法在博弈树搜索中的有效性。br　　对于残局阶段的计算机博弈，有学者提出了利用残局库，但这些残局库往往很大，匹配一个残局需要很长的时间，也未必能匹配上，效果也不好。而一般的搜索引擎在对博弈树进行剪枝的时候仅仅依据的是叶子结点评估值，没有考虑残局模式。这和人类大师有点不同。象棋大师们的大脑记住了很多残局的模式，当他们在下棋的过程中，发现当前思考局面能够匹配某个残局模式，就会停止进一步的思考。受到这个思考过程的启发，本文作者设计了一种新的剪枝算法。在搜索引擎中加入了一些经典残局判别规则，来对博弈树进行剪枝。10.期刊论文周玮.王水涛.孙旸.ZHOUWei.WANGShui-tao.SUNYang中国象棋计算机博弈中的一种数据结构方法-计算机工程与应用2006,42(35)基于人工免疫算法提出了在中国象棋中建立哈希表的实用方法.该方法将棋面表示成一个10×9的矩阵,应用人工免疫算法抗原抗体互识别的形式模型和矩阵奇异值分解与形式模型的关系,得到具有稳定结合的最低结合能量抗原抗体对,根据这一抗原抗体对的某些表位和对位的组合得到哈希值,并随机产生10万个不同象棋棋面的样本空间,验证该方法的有效性,得到在样本空间中无冲突的结果.实践表明,该方法有较好的散列哈希值的能力,实现了计算机棋力的实际增长,在计算机象棋对弈以及其它领域的博弈研究中有实际的应用价值.本文链接：授权使用：吕先竟(wfxhdx)，授权号：781f06ff-e1c4-426a-ba94-9e1700e56740下载时间：2010年10月22日