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

摘要

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

目录

文摘

英文文摘

绪 论

第一章中国象棋计算机博弈问题的研究

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并行博弈处理的研究

本章小结

结束语

攻读学位期间发表的学术论文

参考文献

致 谢