中国象棋人机对弈的研究与实现-毕业论文
厦门大学本科毕业论文I中国象棋人机对弈的研究与实现中国象棋人机对弈的研究与实现摘要 机器博弈被认为是人工智能领域最具挑战性的研究方向之一。国际象棋的计算机博弈已经有了很长的历史,并且经历了一场波澜壮阔的“搏杀“，“深蓝“计算机的胜利也给人类留下了难以忘怀的记忆。凭借设计优良的算法和计算机的快速运算能力，计算机可以在人机对弈中表现出相当高的“智能”。 中国象棋是一个标准的博弈问题，中国象棋计算机博弈的难度绝不亚于国际象棋，在国际象棋成熟技术的基础上,结合在中国象棋机器博弈方面的多年实践,总结出一套过程建模、状态表示、走法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点。关键词 中国象棋 人工智能 博弈树 Alpha-Beta 搜索 历史启发 Windows。厦门大学本科毕业论文IIAbstract 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 Blue“ 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 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 Search 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.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 悔棋、还原.25 6.3 设置难度，设置搜索引擎.26 6.3.1 设置难度26 6.3.2 设置搜索引擎28厦门大学本科毕业论文IV第七章 总结30第八章 程序运行截图31致谢36参考文献37附录38厦门大学本科毕业论文VContentPreview 1Chapter 1 Overview2 1.1.Key Points of Man-machine Game2 1.2 Board Representations3 1.3 Move Generation3 1.4 Search Techniques3Chapter 2 Board Representations5 2.1 Basic Representations.5Chapter 3 Move Generation8 3.1 Move Generator8 3.2 Legal Move.10 3.3 Threat King.11 3.4 Which Approach to Generate.11Chapter 4 Search Techniques.13 4.1 Game Tree13 4.1.1 Game Tree Evaluation .13 4.2 Max-Negative Search.14 4.2.1 Breadth First Search and Depth First Search.14 4.2.2 Analsis of Max-Negative Search：Branching Factor and Depth15 4.2.3 Implementation of Max-Negative Search16 4.3 AlphaBeta Search.16 4.3.1 Fleet Cutting.16 4.3.2 Deep Cutting17 4.3.3 Analysis18 4.3.4 Implementation of Alpha-Beta Search.19 4.4 Comparison of Max-Negative Search and Alpha-Beta Search20 4.5 Iterated Deepening .20Chapter 5 Evaluation Function .22 5.1 What does Evaluation Fuction Contain 22Chapter 6 Auxiliary Part23 6.1 Basic Framework of Graphic User Interface23 6.1.1 Paint.23 6.1.2 Interactive 23 6.1.3 Computer Responsing24 6.2 Back Move and Undo Back Move.25 6.3 Settings.26厦门大学本科毕业论文VI6.3.1 Set Difficulty26 6.3.2 Set Search Engine28Chapter 7 Conclusion.30Chapter 8 Running Screenshot.31Acknowledgement.36References37Appendix38厦门大学本科毕业论文1引言引言1997 年,IBM 公司的超级计算机“深蓝”与当时的国际象棋世界冠军卡斯帕洛夫进行了一场大肆渲染的比赛。这次被卡斯帕洛夫称作“终于来临的一天”的比赛以深蓝的胜利而告终。IBM 公司将“深蓝”的获胜称作是人工智能领域的一个里程碑。中国象棋是一种完全知识博弈（Game of Perfect Information），意思是指参与双方在任何时候都完全清楚每一个棋子是否存在，处于何处。只要看看棋盘，就一清二楚。跳棋、围棋、黑白棋等都是完全知识博弈。而扑克、麻将等则不是完全知识博弈，因为你不清楚对方的牌。我现在的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈程序。该程序功能包括：·人机对战；·设置难度；·悔棋操作；整个程序的实现可分为两大部分：一、计算机引擎部分 该部分实现了如何让计算机下中国象棋，其中涉及人机博弈的基本理论及思想，是该程序的核心部分，同时也是本项目研究的重点所在。二、界面及程序辅助部分只有有下棋引擎尚不能满足人机交互的基本要求，因此我们还需要一个可视化的界面来作为实现程序的载体，同时提供一些诸如悔棋，计时之类的附属功能（程序辅助）使程序更友好。厦门大学本科毕业论文2第一章第一章 概述概述1.11.1、人机博弈的要点、人机博弈的要点人机对弈的程序至少要包括下列组件： . 棋盘的表示方法，即局面在存储器中的存储方法，程序是根据它来分析局面的； . 掌握规则，即什么样的走法是合理的，如果程序连不合理的走法都不能检测出来，那么对手就可以利用这种走法来欺骗程序； . 找出所有合理走法的算法，这样程序就可以从这些走法中找到最好的，而不是随便找一种走法； . 比较方法，包括比较走法的方法和比较局面的方法，这样程序就可以选择最佳的走法； 用户界面，有了它，程序才能用。 整个程序的基本框架如下：厦门大学本科毕业论文3图 1-1 程序流程框架1.21.2 棋盘表示棋盘表示棋盘表示就是适用一种数据结构来描述棋盘以及棋盘上的棋子，不同的棋盘表示会直接影响到程序的时间以及空间复杂度。中国象棋通常是使用一个二维数组。我这里使用一个有 182个元素的一维数组来表示。其中 90 个元素来表示棋盘上的格子。本文的第三章将探讨棋盘表示的方法及其细节。1.31.3 走法产生器走法产生器博弈的规则决定了那些走法是合法的。对于某些游戏来说，这很简单，比如五子棋，任何棋盘上没有被棋子的格子上落子都是合法的。而中国象棋，规则相对复杂，比如兵过河前不能横走，炮需要隔子才能吃，蹩马腿，象眼等等。走法产生是博弈程序中一个相当复杂而且耗费运算时间的一个环节。不过通过良好的数据结构可以有效地提高生成的速度。本文的第四章将探讨棋盘表示的方法及其细节。11.41.4 搜索技术搜索技术对于计算机来说，直接通过棋盘信息判别走法的好坏并不精确。除了输赢这样的局面可以通过规则来判别外，其他的判断只能做一个大致的估计。判别两种走法孰优孰劣的一个好方法就是观察棋局走下去的结果。也就是向下搜索若干步，然后比较发展下去的结果。为了避免差错，我们假定对手的思考也和我们一样，也就是我们想到的内容，对手也想到了。这就是极大极小搜索算法的基本原则。极大极小搜索算法的时间复杂度是 O(bn).这里 b 是分之因子（branching factor），指棋局在各种情况下的合法走法数的平均值；n 是搜索的最大深度。显然对于象棋这种分之因子很大的棋类游戏，时间开销会随着 n 的曾大会积聚的增长，不出基层就会超出计算机的处理能力，厦门大学本科毕业论文4这将导致在有限时间内得不到令人满意的结果。Alpha-Beta 剪枝、迭代深化、历史启发等搜索算法的改进将效率提高了几个数量级。本文的第五章将介绍博弈树搜索的基本原理和方法。11.51.5 估值（估值（EvaluationEvaluation）然而，现有的计算机的运算能力仍然十分有限。不可能一直搜索到分出胜负的那一步，在有限搜索深度的末端，我们用什么方法来评价局面的优劣呢？我们用一些我们对中国象棋的一些经验和规则来做出不是很准确的量化的评价。写出一个好的估值函数并不是一件轻松的事，它需要你对所评估的棋类相当了解，最好事一个经验丰富的高手。然后还要进行无数次的试验后，才能得到一个令人满意的估值函数。本文将在第六章介绍估值函数。厦门大学本科毕业论文5··第二章第二章 棋盘表示棋盘表示2.12.1 基本表示方法基本表示方法计算机下棋的前提是要让计算机读懂象棋。所谓读懂，即计算机应该能够清楚地了解到棋盘上的局面（棋盘上棋子的分布情况）以及下棋方所走的每一种
