中国象棋计算机博弈数据结构与评估函数的研究和实现

摘要

计算机博弈被认为是人工智能领域最具有挑战性的研究方向之一。人工智能的先驱们曾表明,如果掌握了下棋的本质,也许就掌握了人类智能行为的核心,计算机博弈为人工智能提供了一个良好的试验场所。国际象棋的计算机博弈已经有了很长的历史,并且取得了巨大的成绩,而历史悠久的中国象棋的计算机博弈才刚刚起步,很多技术还不够成熟。随着对人工智能技术的深入研究,越来越多的学者把目光放在了中国象棋博弈的研究上,并把其看作是相关研究的重点之一。 本文在大量阅读国际象棋成熟技术的基础上,结合中国象棋计算机博弈近年来的发展实践,对计算机博弈核心技术中的数据结构和评估函数进行了深入地研究与探讨。数据结构是计算机博弈实现的基础,构架一个好的数据结构对整个引擎的速度影响巨大,对后续博弈技术的实现有着决定性的作用。而除了搜索之外,评估函数是计算机博弈中最重要的部分,也是最人性化的一部分,它在很大程度上决定了博弈水平的高低。鉴于此,本文的主要研究内容如下： (1)分析总结了计算机博弈的关键技术要点,包括数据结构、博弈树搜索技术、评估函数等。 (2)研究并设计了适合中国象棋计算机博弈的棋局表示方法和着法生成方法,即数据结构。解决了如何把棋盘分布信息和棋盘状态信息编码进计算机的问题,并使用着法生成辅助数据结构加速了着法生成。 (3)深入研究了评估函数的构成,对评估函数建立数学模型,分析研究了一些可应用于估值优化的方法和策略。在设计系统的评估函数时,主要采用手工调整方法进行估值参数优化,并在评估函数中使用藐视因子和局势因子来调整着法路径的选择,有效地提高了对弈获胜率。 (4)系统的开发和实现。

目录

文摘

英文文摘

声明

1绪论

1.1研究背景

1.1.1中国象棋计算机博弈的发展历程

1.1.2象棋博弈过程的建模

1.2数据结构和评估函数在中国象棋博弈中的作用

1.3本文的主要工作

2数据结构

2.1.局面表示

2.1.1棋盘表示

2.1.2棋子表示

2.1.3棋盘分布信息表示

2.1.4棋盘状态信息表示

2.2着法生成

2.2.1模板匹配法

2.2.2预置着法表

2.2.3测试实验研究

2.3小结

3博弈树展开与搜索

3.1博弈树的展开

3.2博弈树搜索

3.2.1极大极小值搜索算法

3.2.2 a-β剪枝搜索

3.2.3其他搜索算法

3.3小结

4评估函数

4.1评估函数与博弈性能

4.2评估函数建模

4.2.1固定子力值的评价

4.2.2棋子位置值的评价

4.2.3棋子灵活度的评价

4.2.4棋子的协调性、威胁与保护

4.2.5特殊棋型的评价

4.2.6 对战术的评价

4.2.7评估函数模型

4.3估值参数优化

4.3.1手工调整

4.3.2机器自学习

4.4参数优化策略

4.4.1藐视因子

4.4.2局势因子

4.5全动态调整估值参数

4.6评估函数优劣的测试

4.7小结

5博弈系统开发与实现

5.1系统程序的主要组件

5.1.1数据结构

5.1.2评估函数

5.1.3用户界面

5.2测试平台

6总结及展望

致谢

参考文献