1、厦门大学本科毕业论文 I 中国象棋人机对弈的研究与实现 摘要 机器博弈被认为是人工智能领域最具挑战性的研究方向之一 。 国际象棋的计算机博弈已经有了很长的历史 ,并且经历了一场波澜壮阔的 “搏杀 “， “深蓝 “计算机的胜利也给人类留下了难以忘怀的记忆 。 凭借设计优良的算法和计算机的快速运算能力，计算机可以在人机对弈中表现出相当高的“智能”。 中国象棋是一个标准的博弈问题 ， 中国象棋计算机博弈的难度绝不亚于国际象棋 ， 在国际象棋成熟技术的基础上 ,结合在中国象棋机器博弈方面的多年实践 ,总结出一套过程建模、状态表示、 走法 生成、棋局评估、博弈树搜索、开局库 与残局库开发、系统测试与参数
2、优化等核心技术要点 。 关键词 中国象棋 人工智能 博弈树 Alpha-Beta 搜索 历史启发 Windows。 厦门大学本科毕业论文 II Abstract Man-machine Game is one of the most challenging topic a classic topic in Artificial Intelligence. The chess game between machine and man has a long history and experienced a magnificent fighting. The victory of “Deep Bl
3、ue“ computer gived us a unforgettable memory. Relying on fine-designed algorithms and the fast operation ability, computers can display high “intelligence“ in playing chess. Chinese chess is a standard game problem, and the difficulty of which is no less than chess absolutely. On the basis of chess
4、computer game technology, we can summarize key technologies of process modeling, move generation, evaluation, game tree searching, open library and so on. This paper will introduce how to realize a Chinese Chess program. Key words Chinese Chess Artificial Intelligence (AI) Game Tree Alpha-Beta Searc
5、h History Heuristic Windows 厦门大学本科毕业论文 III 目录 引言 .1 第一章 概述 .2 1.1、人机博弈的要点 .2 1.2 棋盘表示 .3 1.3 走法产生器 .3 1.4 搜索技术 .3 第二章 棋盘表示 .5 2.1 基本表示方法 .5 第三章 走法产生 .8 3.1 走法生成器 .8 3.2 判断走法是否符合规则 .10 3.3 判断将军 . 11 3.4 全部生成 OR 部分生成 . 11 第四章 搜索技术 .13 4.1 博弈树 .13 4.1.1 博弈树的评价 .13 4.2 负值最大搜索 .14 4.2.1 广度优先和深度优先搜索 .14 4
6、.2.2 负值最大的分析：分枝因子和深度 .15 4.2.3 负值最大算法的实现 .16 4.3 AlphaBeta 搜索 .16 4.3.1 浅的裁剪 .16 4.3.2 深的裁剪 .17 4.3.3 分析 .18 4.3.4 Alpha-Beta 算法的实现 .19 4.4 负值最大搜索与 Alpha-Beta 搜索算法的比较 .20 4.5 迭代加深 .20 第五章 估值函数 .22 5.1 估值函数都包含些什么 .22 第六章 程序辅助部分 .23 6.1、界面基本框架 .23 6.1.1 画图部分 .23 6.1.2 界面交互部分 .23 6.1.3 电脑响应部分 .24 6.2 悔
7、棋、还原 .25 6.3 设置难度，设置搜索引擎 .26 6.3.1 设置难度 .26 6.3.2 设置搜索引擎 .28 厦门大学本科毕业论文 IV 第七章 总结 .30 第八章 程序运行 截图 .31 致谢 .36 参考文献 .37 附录 .38 厦门大学本科毕业论文 V Content Preview.1 Chapter 1 Overview .2 1.1.Key Points of Man-machine Game .2 1.2 Board Representations .3 1.3 Move Generation .3 1.4 Search Techniques .3 Chapter
8、 2 Board Representations.5 2.1 Basic Representations.5 Chapter 3 Move Generation .8 3.1 Move Generator .8 3.2 Legal Move.10 3.3 Threat King. 11 3.4 Which Approach to Generate . 11 Chapter 4 Search Techniques.13 4.1 Game Tree .13 4.1.1 Game Tree Evaluation.13 4.2 Max-Negative Search .14 4.2.1 Breadth
9、 First Search and Depth First Search .14 4.2.2 Analsis of Max-Negative Search： Branching Factor and Depth .15 4.2.3 Implementation of Max-Negative Search .16 4.3 AlphaBeta Search .16 4.3.1 Fleet Cutting.16 4.3.2 Deep Cutting .17 4.3.3 Analysis .18 4.3.4 Implementation of Alpha-Beta Search .19 4.4 Co
10、mparison of Max-Negative Search and Alpha-Beta Search .20 4.5 Iterated Deepening.20 Chapter 5 Evaluation Function .22 5.1 What does Evaluation Fuction Contain .22 Chapter 6 Auxiliary Part .23 6.1 Basic Framework of Graphic User Interface .23 6.1.1 Paint .23 6.1.2 Interactive.23 6.1.3 Computer Respon
11、sing .24 6.2 Back Move and Undo Back Move .25 6.3 Settings .26 厦门大学本科毕业论文 VI 6.3.1 Set Difficulty .26 6.3.2 Set Search Engine .28 Chapter 7 Conclusion.30 Chapter 8 Running Screenshot.31 Acknowledgement .36 References .37 Appendix .38 厦门大学本科毕业论文 1 引言 1997 年 ,IBM 公司的超级计算机“深蓝”与 当时 的国 际象棋世界冠军卡斯帕洛夫进行了一场大
12、肆渲染的比赛。这次被卡斯帕洛夫称作“终于来临的一天”的比赛以深蓝的胜利而告终。 IBM公司将“深蓝”的获胜称作是人工智能领域的一个里程碑。 中国 象棋是一种完全知识博弈（ Game of Perfect Information），意思是指参与双方在任何时候都完全清楚每一个棋子是否存在，处于何处。只要看看棋盘，就一清二楚。 跳棋、围棋、黑白棋等都是完全知识博弈。而扑克、麻将等则不是完全知识博弈，因为你不清楚对方的牌。 我 现在 的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对 弈程序。 该程序功能包括： 人机 对战 ； 设置难度； 悔棋操作； 整个程序的实现可分为两大部分： 一、计算机
13、引擎部分 该部分实现了如何让计算机下中国象棋，其中涉及人机博弈的基本理论及思想，是该程序的核心部分，同时也是本项目研究的重点所在。 二、界面及程序辅助部分 只有 有下棋引擎尚不能满足人机交互的基本要求，因此我们还需要一个 可视化的界面来作为实现程序的载体 ，同时提供一些诸如悔棋，计时之类的附属功能（程序辅助）使程序更友好 。 厦门大学本科毕业论文 2 第一章 概述 1.1、 人机博弈的要点 人机对弈的程序 至少 要包括下列组件： . 棋盘的表示方法，即局面在存储器中的存储方法，程序是根据它来分析局面的； . 掌握规则，即什么样的 走法 是合理的，如果程序连不合理的 走法 都不能检测出来，那么对
14、手就可以利用这种 走法 来欺骗程序； . 找出所有合理 走法 的算法，这样程序就可以从这些 走法 中找到最好的，而不是随便找一种 走法 ； . 比较方法，包括比较 走法 的方法和比较局面的方法，这样程序就可以选择最佳的 走法 ； 用户界面 ，有了它，程序才能用 。 整个程序的基本框架如下： 图 1-1 程序流程框架 厦门大学本科毕业论文 3 1.2 棋盘表示 棋盘表示就是适用一种数据结构来描述棋盘以及棋盘上的棋子，不同的棋盘表示会直接影响到程序的时间以及空间复杂度。中国象棋通常是使用一个二维数组。我这里使用一个有 182个元素的一维数组来表示。其中 90 个元素来表示棋盘上的格子。 本文的第
15、三 章将探讨棋盘表示的方法及其细节。 1.3 走法产生器 博弈的规则决定了那些走法是合法的。对于某些游戏来说，这很简单，比如五子棋，任何棋盘上没有被棋子的格子上落子都是合法的。而中国象棋，规则相对复杂，比如兵过河前不能横走，炮需要隔子才能吃，蹩马腿，象眼等等。 走法产生是博弈程序中 一个相当复杂而且耗费运算时间的一个环节。不过通过良好的数据结构可以有效地提高生成的速度。 本文的第 四章 将探讨棋盘表示的方法及其细节。 1 1.4 搜索技术 对于计算机来说，直接通过棋盘信息判别走法的好坏并不精确。除了输赢这样的局面可以通过规则来判别外，其他的判断只能做一个大致的估计。 判别两种走法孰优孰劣的一个
16、好方法就是观察棋局走下去的结果。也就是向下搜索若干步，然后比较发展下去的结果。为了避免差错，我们假定对手的思考也和我们一样，也就是我们想到的内容，对手也想到了。这就是极大极小搜索算法的基本原则。 极大 极小搜索算法的时间复杂度是 O(bn).这里 b 是分之因子（ branching factor），指棋局在各种情况下的合法走法数的平均值； n 是搜索的最大深度。 显然对于象棋这种分之因子很大的棋类游戏，时间开销会随着 n 的曾大会积聚的增长，不出基层就会超出计算机的处理能力，这将导致在有限时间内得不到令人满意的结果。 Alpha-Beta 剪枝、迭代深化、历史启发等搜索算法的改进将效率提高了几个数量级。本文的厦门大学本科毕业论文 4 第 五 章将介绍博弈树搜索的基本原理和方法。 1 1.5 估值（ Evaluation） 然而，现有的计算机的运算能 力仍然十分有限。不可能一直搜索到分出胜负的那一步，在有限搜索深度的末端，我们用什么方法来评价局面的优劣呢？我们用一些我们对中国象棋的一些经验和规则来做出不是很准确的量化的评价。 写出一个好的估值函数并不是一件轻松的事，它需要你对所评估的棋类相当了解，最好事一个经验丰富的高手。然后还要进行无数次的试验后，才能得到一个令人满意的估值函数。 本文将在第 六 章介绍估值函数。
