C/C++中国象棋程序入门与提高

第1章绪论

1.1机器博弈

1.1.1Tic-Tac-Toe游戏

1.1.2国际象棋机器博弈

1.1.3机器博弈发展趋势

1.2中国象棋程序

1.2.1中国象棋博弈程序组成

1.2.2中国象棋程序研究现状

1.2.3全国计算机博弈锦标赛

1.3C/C++基础知识

1.3.1结构体

1.3.2联合体

1.3.3枚举

1.3.4指针

1.3.5面向对象程序设计

1.4数据结构基础知识

1.4.1线性表

1.4.2栈和队列

1.4.3树

1.4.4查找

1.4.5排序

1.5算法分析基础知识

1.5.1算法描述

1.5.2算法时间复杂度分析

第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.2.4局面评估

第3章局面表示

3.1简单的表示方法

3.2扩展数组表示

3.2.1棋盘表示

3.2.2棋子表示

3.2.3二维数组与一维数组

3.3字符串表示局面

3.3.1棋子表示

3.3.2棋盘表示

3.3.3走方表示

3.3.4走棋步数

3.4不同表示方法的转换

3.4.1一维数组转换成FEN串

3.4.2FEN串转换成一维数组

第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.4简化合理位置数组

4.5棋子数组

4.6将军检测

4.7如何更快地生成走法

4.7.1事先生成法

4.7.2位行位列

第5章局面评估

5.1简单的局面评估算法

5.2带棋子数组的评估

5.3新的价值数组

5.4位置分值

5.5灵活性分值

5.6更为复杂的局面评估

5.7知识与速度

第6章基本搜索算法

6.1搜索树

6.2深度优先搜索与广度优先搜索

6.3简单的两步搜索

6.4极大点与极小点

6.5结点的层次

6.6极大极小搜索算法

6.7局面变换

6.7.1用局部变量来保存局面

6.7.2用全局变量来保存局面

6.8走法栈

6.9获取最佳走法

6.10完整的搜索过程

6.11合并极大点与极小点搜索

6.12负极大值搜索

6.13极大极小搜索时间分析

6.14搜索剪枝

6.15Alpha-Beta搜索

6.16Alpha-Beta搜索时间分析

6.17alpha一直小于beta吗？

第7章人机博弈

7.1基本知识

7.1.1程序流程

7.1.2棋局状态

7.1.3图形界面开发工具

7.2VC++工程

7.2.1创建VC++工程

7.2.2VC++工程文件

7.3棋盘显示

7.3.1加载图片

7.3.2棋盘显示

7.4计算机走棋

7.4.1添加类

7.4.2添加类的成员

7.4.3添加走法结构

7.5走法显示

7.6棋手走棋

7.7时间处理

7.7.1计时策略

7.7.2WM_TIMER消息

7.7.3显示时间

第8章机器对弈博弈引擎

8.1UCCI协议

8.1.1通信方式

8.1.2引擎状态

8.1.3指令

8.1.4反馈

8.2常用指令和反馈

8.2.1position

8.2.2banmoves

8.2.3go

8.2.4bestmove

8.3管道

8.3.1创建管道

8.3.2读写管道

8.4UCCI棋盘表示

8.4.1棋盘的坐标表示

8.4.2走法转换

8.5博弈引擎

8.5.1引擎程序运行方式

8.5.2通信处理

8.5.3协议处理

8.5.4工作流程

8.6界面程序

8.6.1功能描述

8.6.2加载引擎

8.6.3卸载引擎

8.6.4常用功能

第9章置换表

9.1置换表

9.2哈希表

9.2.1存储

9.2.2查找

9.2.3冲突

9.2.4冲突处理方法

9.2.5影响哈希表效率的因素

9.3Zobrist键值

9.4哈希函数

9.5结合置换表的Alpha-Beta搜索

9.6结点深度

9.7Alpha结点和beta结点

9.8最佳走法

9.9获胜局面

9.10超出边界的Alpha-Beta搜索

9.11哈希表的冲突处理策略

9.12清空哈希表

第10章算法分析及测试技术

10.1测试内容

10.2测试用例设计

10.2.1开局

10.2.2中局

10.2.3残局

10.3测试代码

10.3.1负极大值搜索

10.3.2Alpha-Beta搜索

10.3.3结合置换表的Alpha-Beta搜索

10.4测试结果分析

10.4.1死亡结点

10.4.2置换表的不稳定性

10.4.3三种算法对照分析

第11章时间控制策略

11.1带时限的搜索算法

11.2平均时间分配

11.3迭代深化(IterativeDeepening)

11.3.1限定时间内究竟能搜索多深

11.3.2迭代深化

11.3.3迭代深化时间分析

11.4动态时间分配

11.5结合置换表的限时搜索

第12章启发式搜索策略

12.1杀手启发(KillerHeuristic)

12.2历史表启发(HistoryHeuristic)

12.3走法排序

12.3.1吃子走法和不吃子走法

12.3.2新的走法数组

12.3.3吃子走法价值

12.3.4不吃子走法的价值

12.3.5走法排序

12.4克服水平线效应

12.5空着

12.6开局库

12.6.1开局库文件

12.6.2开局库在内存中的存储

12.6.3读取开局库文件

12.6.4获取开局库走法

12.6.5修改相关函数

12.7残局库

第13章更多搜索策略

13.1PVS主要变例搜索

13.2MTD(f)算法

13.3后台思考

13.4最小树

13.5你的策略

13.6博弈程序的智能水平

参考文献

　　本书作者多年从事C、C++、VC++、数据结构、算法分析与设计的教学工作，同时也有多年的软件开发经验。此书以提高C/C++程序设计能力为主要目标，深入浅出地介绍中国象棋博弈中的基本算法，分析算法实现的关键技术，再逐步介绍各种高级技巧，使读者能够迅速领会象棋程序的特点，自己动手写出更高效的程序。所有算法均配有示例程序，使读者能够由浅入深地掌握中国象棋程序的要领。将编程与下象棋的实践紧密结合，有较强的趣味性。读者如果具有一定的数据结构基础知识就更容易理解本书。　　本书由浅入深地介绍了中国象棋博弈程序的各个基本知识点，以实际案例来促进读者对算法的理解，提高实际编程能力。主要内容包括：中国象棋博弈，局面表示，走法表示及生成走法，局面评估，基本搜索算法，人机博弈，机器对弈，置换表，算法分析及测试技术，时间控制策略，启发式搜索策略，更多搜索策略。　　本书适用于在校计算机专业本科学生及研究生，以及程序设计、算法、博弈和人工智能的爱好者及专业人士。