混合博弈树算法在中国象棋人机博弈中的应用研究

论文摘要

计算机博弈是人工智能领域中最具有挑战性的科研课题之一。国际象棋的计算机博弈已经有了很长的历史,在1997年IBM公司的超级计算机“深蓝”与当时的国际象棋大师卡斯帕罗夫进行了一场大战,并以“深蓝”计算机战胜世界棋王卡斯帕罗夫(1997.5)而载入史册,因为它表明“计算机智能战胜了人类天才”。为了能够在这一新兴的人工智能领域取得更快更多的突破性进展,有力发挥机器博弈的“果蝇”作用,需要很好的明确当前机器博弈所面临的挑战。与国际象棋相比中国象棋的历史更为悠久,其博弈难度水平决不亚于国际象棋,但是涉足学者太少,而且参考资料不多。与国际象棋相比中国象棋的盘面规模更大、着法更为特殊、变化也更加复杂,同时象棋也是一种完全知识博弈,意思是指参与双方在任何时候都完全清楚每一个棋子是否存在,位于何处,只要看看棋盘,就一清二楚了。一个完备的中国象棋人机博弈系统一般包括以下组成部分:棋盘表示、搜索引擎、估值核心、开局库、残局库。本文通过对自行研制的象棋程序的数据表示、走法生成、搜索引擎、估值核心、开局库模块的描述与分析,阐述了此象棋程序的设计与实现的原理,提出了一种新的混合博弈树的搜索算法应用到中国象棋的程序中,明显的提高了程序的搜索效率;同时也设计了一种新的评估函数在中国象棋开局库中的应用,结合了利用共轭梯度求解二次最优的方法,尽可能的保证系统在开局阶段便处于优势,并使开局库具有一定的自学习能力,提高了博弈水平。

论文目录

• 摘要
• ABSTRACT
• 绪论
• 1. 课题研究背景
• 2. 本文的主要工作
• 3. 本文框架
• 本章小结
• 第一章 中国象棋计算机博弈问题的研究
• 1.1 国际象棋计算机博弈情况简述
• 1.2 中国象棋人机博弈问题的局面综述
• 1.3 中国象棋程序的研究
• 本章小结
• 第二章 中国象棋程序博弈树算法的研究
• 2.1 搜索算法的分类
• 2.2 基本搜索算法
• 2.3 高级搜索算法
• 本章小结
• 第三章 象棋程序的改进
• 3.1 一种新的混合的博弈树算法的提出
• 3.1.1 混合博弈树算法
• 3.1.2 混合博弈搜索树搜索算法的理论依据
• 3.1.3 混合博弈树算法试验结果分析
• 3.2 后台思考的应用
• 3.2.1 UCCI 通用引擎
• 3.2.2 后台思考
• 3.3 博弈系统的时间策略
• 3.4 棋盘与棋子的表示
• 3.5 博弈系统的评估函数
• 3.5.1 棋子的基本子力值和灵活度
• 3.5.2 棋子的威胁、保护、配合作战以及兵的状态
• 3.5.3 棋子的位置值与改进
• 3.5.4 状态评估的优化
• 3.6 博弈系统的博弈风格
• 本章小结
• 第四章 象棋程序开局库系统的研制与应用
• 4.1 计算机象棋开局库系统
• 4.1.1 盘面节点信息
• 4.1.2 数据结构的设计
• 4.1.3 棋谱文件格式
• 4.2 开局库中的评估函数
• 4.2.1 开局库与评估函数相结合的意义
• 4.2.2 开局库系统中评估函数的引入
• 4.2.3 设计流程
• 4.2.4 开局库引入评估函数的效果
• 本章小结
• 第五章 残局库及并行处理的应用
• 5.1 残局库系统
• 5.1.1 残局库的结构
• 5.1.2 博弈系统中残局库的应用
• 5.2 并行博弈处理的应用
• 本章小结
• 结束语
• 攻读学位期间发表的学术论文
• 参考文献
• 致谢