中国象棋计算机博弈关键技术研究

摘要

人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。 计算机博弈是人工智能领域中一个重要的课题，国际象棋计算机博弈已经取得了巨大的成功，而中国象棋计算机博弈却远远落后。“棋天大圣”是东北大学人工智能与机器人研究所自主开发的中国象棋计算机博弈软件，取得了第11届世界电脑象棋奥林匹克竞赛中国象棋组的冠军。本文通过结合“棋天大圣”的研究成果，阐述了一个可以达到人类特级大师水平的中国象棋程序的设计和实现原理。 本文对中国象棋计算机博弈的关键技术进行了分析和介绍，并提出了一些新的思想和算法，以及基于数据测试集的分析和检验。其中包括以下几点。 第一，介绍了中国象棋状态空间的数据表示方法，介绍了对状态空间的数字表示和布尔表示，提出了用棋盘编码数组、棋子编码数组、映射数组数字表示状态空间，用新型数据结构路向行向比特向量与比特棋盘相结合布尔表示状态空间的新方法。在这些描述方法共同作用下，程序具有很高的运行效率，大大节省了计算时间。 第二，详细介绍了当今流行的各种着法生成算法，提出了路向行向比特向量与模板法相结合，并且辅以预置表作为辅助进行着法生成的新方法。着法生成的速度获得很大的提升。 第三，介绍了棋类搜索领域的搜索算法及其分类，给出了多种搜索算法的融合方式，以及在中国象棋计算机博弈领域应用的创新。 第四，结合“棋天大圣”的审局函数，介绍了审局函数的概念、组成和计算的方法。提出了小子同形表这种新的计算方法，可以对引擎起到良好的加速作用。 第五，本文就开局库的原理做出了介绍，提出了理想开局厍并做了深入的探讨。对开局库自学习算法原理和成果进行了总结。 第六，提出了残局处理系统的新概念，将残局处理系统划分为残局知识库与残局数据库。对自行设计的残局知识库的原理、结构、实现方法做出了详细的介绍。 第七，创造性地将自适应遗传算法、神经元网络结合TD(λ)算法两种机器学习算法引入审局函数中，详细的介绍了与审局函数的结合、测试的方法以及取得的成果。本文的研究在中国象棋计算机博弈领域处于前沿，结合本文的研究成果可以创建高水平的博弈软件，而且在一系列电脑之间的比赛和人机挑战赛中，也得到了印证。本文的成果和结论，对于其它中国象棋计算机博弈程序，具有一定的参考价值。

目录

文摘

英文文摘

声明

第一章引言

1.1研究动机

1.2研究背景

1.3研究内容

1.4本文组织结构

第二章中国象棋状态空间的表示方法

2.1象棋博弈问题的状态空间描述

2.1.1问题状态描述

2.1.2系统性质分析

2.2棋盘棋子编码

2.2.1棋盘坐标编码

2.2.2棋子种类编码

2.2.3棋子个体编码

2.3棋盘空间状态的数字表示

2.3.1棋盘索引数组

2.3.2棋子索引数组

2.3.3映射数组

2.4棋盘空间状态的布尔表示

2.4.1路向行向比特向量

2.4.2比特棋盘

2.5数据结构之间的对应关系及其更新过程

2.5.1数据结构之间的对应关系

2.5.2数字表示数据结构的更新

2.5.3布尔表示数据结构的更新

2.6其它相关表示方法

2.6.1 FEN格式

2.6.2 PGN格式

2.6.3旋转比特棋盘

2.7小结

第三章中国象棋计算机博弈着法生成

3.1着法生成概念

3.1.1着法算子

3.1.2着法表示方法

3.1.3着法分类

3.2着法生成辅助-预置着法表

3.3各种流行着法生成算法介绍

3.3.1棋盘扫描法

3.3.2射线法

3.3.3模板匹配法

3.4路向行向比特向量与预置着法表的结合

3.4.1以路向行向比特向量为索引的预置着法表

3.4.2以路向行向比特向量为索引的预置表的存储方式

3.5折叠比特棋盘法

3.5.1折叠的意义

3.5.2折叠的方法

3.5.3折叠的证明

3.5.4折叠与展开

3.6各种着法生成方法对比分析

3.7小结

第四章博弈搜索算法研究

4.1搜索算法分类

4.2穷尽搜索算法

4.2.1极大极小值算法(Minimax Algorithm)

4.2.2负极大值算法(Negamax Algorithm)

4.2.3深度优先(depth_first search)和广度优先(breadth_first search)

4.2.4 α-β搜索

4.2.5渴望窗口搜索(Aspiration Window)

4.2.6 PVS(Principal Variation Search)/Negascout搜索

4.3裁剪算法

4.3.1无风险裁剪算法

4.3.2有风险裁剪算法

4.4延伸算法(Search Extendsion)

4.4.1静止期搜索(Quiescent Search)

4.4.2将军延伸(Check Extension)

4.4.3唯一着法延伸(One_Reply Extension)

4.4.4兑子延伸(Recapture Extension)

4.4.5杀棋延伸(Mate Extension)

4.5启发式搜索算法

4.5.1静态启发信息

4.5.2动态启发式信息

4.5.3启发式算法的辅助——迭代深化

4.6同形表(Transposition Table)

4.6.1同形表实现原理

4.6.2同形表的结构

4.6.3同形表的写入和读取

4.6.4同形表的裁剪算法和启发式算法

4.6.5同形表性能测试

4.7并行搜索算法

4.7.1 DTS搜索算法

4.7.2 APHID搜索算法

4.8 小结

第五章中国象棋计算机博弈审局函数研究

5.1审局函数概念

5.2审局函数包含的内容

5.2.1棋子固定价值审局

5.2.2小子审局函数

5.2.3子力配合值

5.2.4将的安全审局

5.3小子同形表

5.3.1小子同形表可行性分析

5.3.2小子同形表查询与更新

5.3.3小子同形表的结构

5.3.4小子使用方法

5.3.5效率对比

5.4小结

第六章开局库设计与开局库自学习

6.1引言

6.2开局库的重要性

6.3开局库的计算机自动生成

6.3.1最好为先扩展法的基本原理(Best-First Expansion)

6.3.2脱谱扩展法的基本原理(Drop-Out Expansion)

6.4统计开局库的设计与使用

6.4.1统计方式设计

6.4.2数据结构设计与应用

6.4.3统计方法的科学探讨

6.5理想开局库

6.5.1理想开局库的提出

6.5.2理想开局库的设计

6.5.3理想开局库的问题

6.6开局库自学习

6.6.1开局库自学习系统

6.6.2自学习存在的问题

6.6.3开局评价体系

6.7小结

第七章残局处理系统

7.1中国象棋残局特点分析

7.2中国象棋计算机博弈残局系统

7.3残局知识库

7.3.1残局知识库入口

7.3.2残局知识库的出口

7.3.3残局知识库对“势”的判定

7.3.4残局知识库对“形”的判定

7.3.5残局知识库在对搜索引擎的影响

7.4残局数据库

7.4.1残局数据库的调用

7.4.2残局数据库的数据表示

7.4.3残局数据库的分类

7.4.4残局数据库的索引

7.4.5残局数据库的构造

7.5难点分析

7.5.1残局知识库难点分析

7.5.2残局数据库难点分析

7.6小结

第八章机器学习算法在审局函数中的应用

8.1基于自适应遗传算法的审局函数

8.1.1遗传算法

8.1.2适应度函数的计算——锦标赛算法

8.1.3加快优化进程的相关举措

8.1.4遗传操作过程

8.1.5自适应遗传算法

8.1.6实验结果

8.2人工神经元网络结合TD(λ)算法在审局函数中的应用

8.2.1人工神经元网络

8.2.2用BP网络结构表示审局函数

8.2.3 TD(λ)算法

8.2.4获得训练数据

8.2.5实验结果

8.3 小结

第九章结论与展望

参考文献

致谢

攻读博士期间发表的学术论文、参加和完成的科研工作及获得的奖励

附录 “棋天大圣”运行界面

个人简介