中国象棋人机对弈的研究与实现-毕业论文

厦门大学本科毕业论文中国象棋人机对弈的研究与实现摘要 机器博弈被认为是人工智能领域最具挑战性的研究方向之一。国际象棋的计算机博弈已经有了很长的历史,并且经历了一场波澜壮阔的搏杀，深蓝计算机的胜利也给人类留下了难以忘怀的记忆。凭借设计优良的算法和计算机的快速运算能力，计算机可以在人机对弈中表现出相当高的“智能”。 中国象棋是一个标准的博弈问题，中国象棋计算机博弈的难度绝不亚于国际象棋，在国际象棋成熟技术的基础上,结合在中国象棋机器博弈方面的多年实践,总结出一套过程建模、状态表示、走法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点。关键词 中国象棋 人工智能 博弈树 Alpha-Beta搜索 历史启发 Windows。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 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 chessis 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目录引言1第一章 概述21.1、人机博弈的要点21.2棋盘表示31.3走法产生器31.4搜索技术3第二章 棋盘表示52.1基本表示方法5第三章 走法产生83.1 走法生成器83.2判断走法是否符合规则103.3 判断将军113.4全部生成OR部分生成11第四章 搜索技术134.1博弈树134.1.1博弈树的评价134.2负值最大搜索144.2.1广度优先和深度优先搜索144.2.2负值最大的分析：分枝因子和深度154.2.3负值最大算法的实现164.3 AlphaBeta搜索164.3.1浅的裁剪164.3.2深的裁剪174.3.3 分析184.3.4 Alpha-Beta算法的实现194.4 负值最大搜索与Alpha-Beta搜索算法的比较204.5迭代加深20第五章 估值函数225.1估值函数都包含些什么22第六章 程序辅助部分236.1、界面基本框架236.1.1画图部分236.1.2界面交互部分236.1.3电脑响应部分246.2悔棋、还原256.3设置难度，设置搜索引擎266.3.1设置难度266.3.2设置搜索引擎28第七章 总结30第八章 程序运行截图31致谢36参考文献37附录38ContentPreview1Chapter 1 Overview21.1.Key Points of Man-machine Game21.2 Board Representations31.3 Move Generation31.4 Search Techniques3Chapter 2 Board Representations52.1 Basic Representations5Chapter 3 Move Generation83.1 Move Generator83.2 Legal Move103.3 Threat King113.4 Which Approach to Generate11Chapter 4 Search Techniques134.1 Game Tree134.1.1 Game Tree Evaluation134.2 Max-Negative Search144.2.1 Breadth First Search and Depth First Search144.2.2 Analsis of Max-Negative Search：Branching Factor and Depth154.2.3 Implementation of Max-Negative Search164.3 AlphaBeta Search164.3.1 Fleet Cutting164.3.2 Deep Cutting174.3.3 Analysis184.3.4 Implementation of Alpha-Beta Search194.4 Comparison of Max-Negative Search and Alpha-Beta Search204.5 Iterated Deepening20Chapter 5 Evaluation Function225.1 What does Evaluation Fuction Contain22Chapter 6 Auxiliary Part236.1 Basic Framework of Graphic User Interface236.1.1 Paint236.1.2 Interactive236.1.3 Computer Responsing246.2 Back Move and Undo Back Move256.3 Settings266.3.1 Set Difficulty266.3.2 Set Search Engine28Chapter 7 Conclusion30Chapter 8 Running Screenshot31Acknowledgement36References37Appendix38 52引言1997年,IBM公司的超级计算机“深蓝”与当时的国际象棋世界冠军卡斯帕洛夫进行了一场大肆渲染的比赛。这次被卡斯帕洛夫称作“终于来临的一天”的比赛以深蓝的胜利而告终。IBM公司将“深蓝”的获胜称作是人工智能领域的一个里程碑。中国象棋是一种完全知识博弈（Game of Perfect Information），意思是指参与双方在任何时候都完全清楚每一个棋子是否存在，处于何处。只要看看棋盘，就一清二楚。跳棋、围棋、黑白棋等都是完全知识博弈。而扑克、麻将等则不是完全知识博弈，因为你不清楚对方的牌。我现在的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈程序。该程序功能包括：人机对战；设置难度；悔棋操作；整个程序的实现可分为两大部分：一、计算机引擎部分 该部分实现了如何让计算机下中国象棋，其中涉及人机博弈的基本理论及思想，是该程序的核心部分，同时也是本项目研究的重点所在。二、界面及程序辅助部分只有有下棋引擎尚不能满足人机交互的基本要求，因此我们还需要一个可视化的界面来作为实现程序的载体，同时提供一些诸如悔棋，计时之类的附属功能（程序辅助）使程序更友好。第一章 概述1.1、人机博弈的要点人机对弈的程序至少要包括下列组件： . 棋盘的表示方法，即局面在存储器中的存储方法，程序是根据它来分析局面的； . 掌握规则，即什么样的走法是合理的，如果程序连不合理的走法都不能检测出来，那么对手就可以利用这种走法来欺骗程序； . 找出所有合理走法的算法，这样程序就可以从这些走法中找到最好的，而不是随便找一种走法； . 比较方法，包括比较走法的方法和比较局面的方法，这样程序就可以选择最佳的走法； 用户界面，有了它，程序才能用。 整个程序的基本框架如下：图1-1 程序流程框架1.2棋盘表示棋盘表示就是适用一种数据结构来描述棋盘以及棋盘上的棋子，不同的棋盘表示会直接影响到程序的时间以及空间复杂度。中国象棋通常是使用一个二维数组。我这里使用一个有182个元素的一维数组来表示。其中90个元素来表示棋盘上的格子。本文的第三章将探讨棋盘表示的方法及其细节。1.3走法产生器博弈的规则决定了那些走法是合法的。对于某些游戏来说，这很简单，比如五子棋，任何棋盘上没有被棋子的格子上落子都是合法的。而中国象棋，规则相对复杂，比如兵过河前不能横走，炮需要隔子才能吃，蹩马腿，象眼等等。走法产生是博弈程序中一个相当复杂而且耗费运算时间的一个环节。不过通过良好的数据结构可以有效地提高生成的速度。本文的第四章将探讨棋盘表示的方法及其细节。11.4搜索技术对于计算机来说，直接通过棋盘信息判别走法的好坏并不精确。除了输赢这样的局面可以通过规则来判别外，其他的判断只能做一个大致的估计。判别两种走法孰优孰劣的一个好方法就是观察棋局走下去的结果。也就是向下搜索若干步，然后比较发展下去的结果。为了避免差错，我们假定对手的思考也和我们一样，也就是我们想到的内容，对手也想到了。这就是极大极小搜索算法的基本原则。极大极小搜索算法的时间复杂度是O(bn).这里b是分之因子（branching factor），指棋局在各种情况下的合法走法数的平均值；n是搜索的最大深度。显然对于象棋这种分之因子很大的棋类游戏，时间开销会随着n的曾大会积聚的增长，不出基层就会超出计算机的处理能力，这将导致在有限时间内得不到令人满意的结果。Alpha-Beta剪枝、迭代深化、历史启发等搜索算法的改进将效率提高了几个数量级。本文的第五章将介绍博弈树搜索的基本原理和方法。11.5 估值（Evaluation）然而，现有的计算机的运算能力仍然十分有限。不可能一直搜索到分出胜负的那一步，在有限搜索深度的末端，我们用什么方法来评价局面的优劣呢？我们用一些我们对中国象棋的一些经验和规则来做出不是很准确的量化的评价。写出一个好的估值函数并不是一件轻松的事，它需要你对所评估的棋类相当了解，最好事一个经验丰富的高手。然后还要进行无数次的试验后，才能得到一个令人满意的估值函数。本文将在第六章介绍估值函数。第二章 棋盘表示2.1基本表示方法计算机下棋的前提是要让计算机读懂象棋。所谓读懂，即计算机应该能够清楚地了解到棋盘上的局面（棋盘上棋子的分布情况）以及下棋方所走的每一种走法。因而首先我们需要有一套数据结构来表示棋盘上的局面以及走法。4图2-1 初始棋盘一般说来，棋盘表示与具体的棋类知识密切相关。我这里用的是一个有182元素的一维数组/ 棋盘初始设置static const BYTE startPosition182 = /14*13 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 19, 18, 17, 16, 17, 18, 19, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 22, 0, 22, 0, 22, 0, 22, 0, 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0, 14, 0, 14, 0, 14, 0, 14, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 11, 10, 9, 8, 9, 10, 11, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;其中间的90个元素表示棋盘上的格子，其中0表示格子上没有棋子，数字表示棋子。具体的表示方法是在一个基数上加上代表每种棋子的数字。具体的数字如下帅/将 用CHESS_KING表示 具体数字为0仕/士 用CHESS_BISHOP表示 具体数字为1相/象 用CHESS_ELEPHANT表示 具体数字为2車 用CHESS_CAR表示具体数字为3馬 用CHESS_HORSE表示具体数字为4炮 用CHESS_CANNON表示 具体数字为5兵/卒 用CHESS_PAWN表示 具体数字为6为了区分红子跟黑子，我在各种棋子上加上一个基数来区别，红色的基数为8，黑色为16，之所以选择8跟16，是因为238，2416，而棋子的种类只有7种，占一个整数的最后3位，加上基数之后，最后3位的数值并未改变，这样，我们可以方便的运用一些位运算。我们用一个常数数组来判断棋子是否在棋盘之中static const char InBoard182 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;判断一个格子是不是在棋盘内可以用if(InBoardsq=1)来判断同时我们可以这样获得格子sq的横坐标和纵坐标#define GET_X(sq)(sq)%13)/ 获得格子的横坐标#define GET_Y(sq)(sq)/13)/ 获得格子的纵坐标对于走法，我们可以用一个16位的int型整数来表示，前8位表示走法的终点，后8位表示走法的起点。这样我们可以这么表示定义两个宏，取得move（int型整数）的起点和终点#define DST(mv) (mv)255) /获得终点#define SRC(mv) (mv)&255) /获得起点第三章 走法产生3.1 走法生成器走法生成器是象棋程序中的一个重要组成部分，它是指把一个局面的所有可能的走法罗列出来的那一部分程序，它可以解决几乎所有象棋规则的问题。那么我们如何编写走法生成器呢？举个例子，我们来讨论一下如何产生马的走法。一维数组的好就是上下左右关系非常简明上面一格是 sq - 13，下面一格是 sq + 13，左面一格是 sq - 1，右面一格是 sq + 1。马可以跳的点只有8个，终点相对起点的偏移值是固定的：static const char HorseDelta42 = -27, -25, -15, 11, -11, 15, 25, 27;而对应的马腿的偏移值是： static const char KingDelta4 = -13, -1, 1, 13;这个数组之所以命名为KingDelta，是因为它也是帅(将)的偏移值。 这样，找到一个马的所有走法就容易很多了。首先判断某个方向上的马腿是否有子，然后判断该方向上的两个走法是否能走：for (i = 0; i 4; i +)sqDst = sqSrc + KingDeltai;if (CurrentPositionsqDst != 0) continue;for (j = 0; j best) best = val; return best; 4.3 AlphaBeta搜索4.3.1浅的裁剪 假设你用最小-最大搜索(前面讲到的)来搜索图4-2的树： 图4-2 博弈树浅的裁剪你搜索到F，发现子结点的评价分别是11、12、7和9，在这层是棋手甲走，我们希望他选择最好的值，即12。所以，F的最小-最大值是12。 现在你开始搜索G，并且第一个子结点就返回15。一旦如此，你就知道G的值至少是15，可能更高(如果另一个子结点比G更好)。这就意味着我们不指望棋手乙走G这步了，因为就棋手乙看来，F的评价12要比G的15(或更高)好，因此我们知道G不在主要变例上。我们可以裁剪(Prune)结点G下面的其他子结点，而不要对它们作出评价，并且立即从G返回，因为对G作更好的评价只是浪费时间。 一般来说，像G一样只要有一个子结点返回比G的兄弟结点更好的值(对于结点G要走棋的一方而言)，就可以进行裁剪。 4.3.2深的裁剪我们来讨论更复杂的可能裁剪的情况。例如在图4-3的搜索树中，我们评价的G、H和I都比12好，因此12就是结点B的评价。现在我们来搜索结点C，在下面两层我们找到了评价为10的结点N： 图4-3 博弈树深的裁剪我们能用更为复杂的路线来作裁剪。我们知道N会返回10或更小(轮到棋手乙走棋，需要挑最小的)。我们不知道J能否返回10或更小，也不知道J的哪个子结点会更好。如果从J返回到C的是10或者更小的值，那么我们可以在结点C上作裁剪，因为它有更好的兄弟结点B。因此在这种情况下，继续找N的子结点就毫无意义。考虑其他情况，J的其他子结点返回比10更好的值，此时搜索N也是毫无意义的。所以我们只要看到10，就可以放心地从N返回。 一般来说，如果返回值比偶数层的兄弟结点好，我们就可以立即返回。如果我们在搜索过程中，把这些兄弟结点的最小值Beta作为参数来传递，我们就可以进行非常有效的裁剪。我们还用另一个参数Alpha来保存奇数层的结点。用这两个参数来进行裁剪是非常有效的，代码就写在下边。像上次一样，我们用负值最大(Negamax)的形式，即搜索树的层数改变时取负值。 4.3.3 分析 让我们对Alpha-Beta搜索作一下分析，来知道它为什么是个很有用的算法。跟普通的算法不同，我们采用“Beta情况的分析”，即假设任何可能的情况下都会发生Alpha-Beta裁剪。下一次我们会知道如何让Alpha-Beta搜索接近我们的所分析的情况。在这里我只考虑浅的裁剪，因为它会让分析变得更加简单。 在最好的情况下，除了主要变例上的结点不会裁剪外(如果这个结点也被裁剪了，那么整个算法会高出边界或低出边界，这当然不是最好的情况)，在裁剪前，深D -1层的每个结点只会搜索一个深D层的子结点。 但是在深D -2层时，谁也没有被裁剪，因为所有的子结点都返回大于或等于Beta的值，而D -2层是要取负数，因此它们都小于或等于Alpha。 继续朝树根走，D -3层的每个结点(除了主要变例外)都被裁剪，而D -4层谁也没被裁剪，等等。 因此，如果搜索树的分枝因子是B，那么在搜索树一半的深度上，结点以因子B作增长，而在另一半的深度上则保持不变(我们忽略了主要变例)。所以这个搜索树所有要搜索的结点数，粗略地写成BD/2=sqrt(B)D。因此Alpha-Beta搜索最终可以将分枝因子减少为原来的平方根那么多，因此它可以让我们搜索原来两倍的深度。正因为这个原因，它是所有基于最小-最大策略的棋类对弈程序的最重要的算法。6 10 4.3.4 Alpha-Beta算法的实现Alpha-Beta搜索算法的伪代码如下，具体实现参见附录int AlphaBeta(int depth, int alpha, int beta) if (depth = 0) 返回估值(); 生成所有走法(); while (遍历走法队列) 执行下一步走法(); val = -AlphaBeta(depth - 1, -beta, -alpha); 撤销该走法(); if (val = beta) return beta; if (val alpha) alpha = val; return alpha; 4.4 负值最大搜索与Alpha-Beta搜索算法的比较我们的程序里添加了负值最大搜索与Alpha-Beta搜索两种算法，通过对两种引擎的的比较，可以看出两个搜索算法的优劣。下面是实验的数据我们选择入门级别的难度，各搜索算法下十步棋的反应时间（这十步棋的走法一致，电脑的走法也一致：这十步走法为1.炮二平五 马2进3 2.马二进三 炮8平5 3.车一平二 马8进74.车二进六 卒7进1 5.车二平三 车9进2 6.兵七进一 车9平87.马八进七 车1进1 8.马七进六 炮5平4 9.马六进四 马7退810.车三进三 象3进5） 表4-1 Alpha-Beta搜索算法与负值最大搜索算法的比较第一次反应时间第二次反应时间第三次反应时间平均反应时间Alpha-Beta搜索00:00:09.4900:00:08. 1200:00:08. 3900:00:08.67负值最大搜索00:01:02.2600:01:02.0600:01:01.7500:01:02.02我们可以很清楚得看到Alpha-Beta搜索和负值最大搜索算法的优劣，同样的走法，后者明显比前者更花费时间4.5迭代加深负值极大的代码还留给我们一个问题：我们如何来给定搜索深度？简单的棋类程序只把它设成一个固定值，这就可能使得程序走的每步棋时花的时间长短变化非常大。因此你最好根据搜索所需的时间，来决定搜索的深度。幸运的是指数特征的搜索有这样一个好处：通过“迭代加深”(Iterated Deepening)这个手段，可以很容易地对搜索进行控制，刚开始搜索时浅一些，然后增加深度重复搜索直到时间用完为止。下面是迭代加深的伪代码：for (depth = 1; ; depth +) value = AlphaBeta(-INFINITY, INFINITY, depth); if (没有足够的时间来执行下一层的搜索) break; 执行最佳走法; 这看上去似乎在浪费时间，因为除了最后一次搜索外，前面的搜索都白费了。但是根据前面分析过的结果，白费的时间是很少的：不同层数所花的时间加起来是 1 + b + b2 + .，我们已经知道它接近于最后一项bd了。所以，迭代加深所花的代价并不多，而它给我们提供了很好的时间控制的手段。它还有一个很大的作用：在做较深的搜索时，可以用浅一层搜索得到的走法顺序，在Alpha-Beta搜索中，走法顺序是影响搜索的速度的决定性因素。第五章 估值函数5.1估值函数都包含些什么 估值函数大致包含如下几个要素1、子力平衡子力是指某一棋子本身所具有的价值。通俗地讲就是一个棋子它值个什么价。例如，车值500的话，那可能马值300，卒值80等等。所以在评估局面时，我们首先要考虑双方的子力总和的对比。比如红方拥有士象全加车马炮，而黑方只有残士象加双马，则红方明显占优。2、棋子位置棋子位置，或称控制区域，是指某一方的棋子在棋盘上所占据（控制）的位置。例如，沉底炮、过河卒、以及车占士角等都是较好的棋子位置状态，而窝心马、将离开底线等则属较差的棋子位置状态。3、棋子的机动性棋子的机动性指棋子的灵活度（可移动性）。例如，起始位置的车机动性较差，所以我们下棋讲究早出车。同样四面被憋马腿的死马机动性也较差（对于一步也不能走的棋子，可以认为其机动性为零）。4、棋子的相互关系（包括攻击关系和保护关系）这一点的分析较为复杂，因为一个棋子与其它子之间往往存在多重关系。如：一个马可能在对方的炮的攻击之下同时它又攻击着对方的车.我们的程序中只分析了子力平衡跟棋子位置，二者结合起来就是一个各棋子在各个位置的价值表。然后扫描棋盘统计局面总价值。第六章 程序辅助部分6.1、界面基本框架我们的界面通过直接调用Windows API 来实现。主要分为三个部分6.1.1画图部分我们定义一个与图形界面有关的全局结构体static struct HINSTANCE hInst; / 应用程序句柄实例 HWND hWnd; / 主窗口句柄 HDC hdc, hdcTmp; / 设备句 HBITMAP bmpBoard, bmpSelected, bmpPieces24; / 资源图片句柄 int sqSelected, lastMove; / 选中的格子，上一步棋 BOOL isFlip; / 是否翻转棋盘 ChessGUI;由于我们的棋盘、棋子等都是以位图的形式给出的。所以里我们做的工作主要都是在贴位图。我们在这里定义两个函数static void DrawBoard(HDC) 负责绘制棋盘和static void DrawSquare(int, BOOL)负责和绘制格子的功能。2 36.1.2界面交互部分为WM_LBUTTONDOWN消息添加消息响应事件，我们通过static void ClickSquare(int )函数来实现我们与计算机的交互，处理点击格子事件。在ClickSquare函数里我们处理如下两种操作：、点击一个格子，如果点击自己的棋子，那么直接选中该棋子，下一步将移动该子进行走棋，否则的话，就不作处理、如果点击的不是自己的子（点击空格子或者对方的子），但有子选中了(一定是自己的子)，并且这个走法符合规则，那么走这个子。其他情况程序不予理会。6.1.3电脑响应部分我们通过一个static void ComputerMove(void)函数来实现电脑响应部分. 2 3 7static void ComputerMove(void) int pcCaptured;/ 电脑走一步棋SetCursor(HCURSOR) LoadImage(NULL, IDC_WAIT, IMAGE_CURSOR, 0, 0, LR_DEFAULTSIZE | LR_SHARED);IterativeSearch();/搜索SetCursor(HCURSOR) LoadImage(NULL, IDC_ARROW, IMAGE_CURSOR, 0, 0, LR_DEFAULTSIZE | LR_SHARED);opera.MakeMove(Search.mvResult, pcCaptured);/按最佳走法走一步棋/ 清除上一步棋的选择标记DrawSquare(SRC(ChessGUI.lastMove);DrawSquare(DST(ChessGUI.lastMove);/ 把电脑走的棋标记出来ChessGUI.lastMove = Search.mvResult;DrawSquare(SRC(ChessGUI.lastMove), DRAW_SELECTED);DrawSquare(DST(ChessGUI.lastMove), DRAW_SELECTED);if (opera.IsKilled() / 如果分出胜负，那么播放胜负的声音，并且弹出不带声音的提示框PlayMySound(IDR_LOSS);MessageBoxMute(YOU LOSE!); else / 如果没有分出胜负，那么播放将军、吃子或一般走子的声音PlayMySound(opera.Checked() ? IDR_CHECK2 : pcCaptured != 0 ? IDR_CAPTURE2 : IDR_M