基于扩展Alpha-Beta算法的中国象棋软件实现的研究

摘要

本文首先回顾了几种搜索算法：极大极小值算法，Alpha-Beta算法和基于Alpha-Beta算法的带验证的空着剪枝算法。其中带验证的空着剪枝算法是一种很高效的剪枝算法，能够在付出较小的成本的前提下，裁剪掉博弈树里大量没有实际意义的分枝，非常适用于中国象棋。 为了对剪枝算法进行研究，采用VisualC++设计了一个象棋程序，采用较合理的数据结构来表示棋盘、棋子。用来加快走法的生产。 置换表和历史启发技术，可以在搜索层数较多的情况下，排除很多冗余节点。将置换表技术与历史启发技术，与带验证的空着启发算法相结合，做为本软件的核心搜索算法。试验表明，这种算法搜索的节点数量较pvs与置换表和历史启发相结合算法搜索的节点数量要少5％左右。

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

第一章绪论

1.1人工智能与人机博弈

1.2深蓝与卡斯帕罗夫的大战

1.3人机博弈的要点

1.3.1棋盘和棋子的表示方法

1.3.2走法产生

1.3.3最佳走法的选择

1.3.4估值

1.4本文的主要工作

第二章棋盘和棋子的表示

2.1棋盘表示的基本知识

2.2二维坐标与一维坐标的比较

2.3冗余辅助点

2.4棋盘-棋子联系数组

2.5本文所采取的棋盘表示方法

第三章走法的产生

3.1如何产生走法

3.2利用数据结构和内存空间加快走法的生成速度

3.2.1短程棋子走法生成

3.2.2车和炮的走法生成

第四章搜索算法和辅助技术

4.1博弈

4.2博弈树

4.3极大极小值算法和负极大值算法

4.4Alpha-Beta剪枝

4.5 PVS搜索

4.6置换表

4.6.1.哈希表

4.6.2 Zobrist哈希技术

4.7历史启发

第五章C++语言程序设计

5.1C++程序

5.2动态内存分配和指针

5.3基于对象的设计

5.4封装性

5.5多态性

第六章空着剪枝的理论与应用

6.1空着剪枝的思想

6.2无等着棋面

6.3适应性空着裁剪和带检验的空着裁剪

第七章结束语

参考文献

致谢

作者简介