中国象棋对弈系统计算机专业本科学位论文.doc

《中国象棋对弈系统计算机专业本科学位论文.doc》由会员分享，可在线阅读，更多相关《中国象棋对弈系统计算机专业本科学位论文.doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河北大学2009届本科生毕业论文（设计）中国象棋对弈系统摘 要人机博弈是人工智能研究的经典课题之一。凭借设计优良的算法和计算机的快速运算能力，计算机可以在人机对弈中表现出相当高的“智能”。中国象棋是我们中华民族文化传统的一部分，有着悠久的历史，并拥有着广泛的群众基础。象棋程序主要由人工智能和界面设计组成。人工智能体现计算机的下棋思路，既计算机如何进行思考并以最佳走法完成下一步，先由相应的搜索算法进行搜索，并对各种可能的走法进行估值，从中选择胜利面最大的一步。界面部分主要便于用户通过以前的下棋步骤，更好地调整下棋思路，着法显示使用户能够清楚地知道下棋过程，更准确地把握整个局面。本文在概述计算机博

2、弈，特别是中国象棋软件概况的基础上，分析了现有中国象棋博弈软件实现方法中存在的问题，设计了棋盘、棋子和评价函数的表示方法，在博弈理论的基础上采用递归方法实现了-剪枝搜索，应用VC和MFC设计并实现了博弈界面。实现了一个具有一定棋力的中国象棋人机对弈程序。关键词：人机博弈 中国象棋 博弈树 VC ABSTRACTMan-machine Game is a classic topic in Artificial Intelligence. Relying on fine-designed algorithms and the fast operation ability, computers ca

3、n display high intelligence in playing chess. The Chinese chess is our Chinese nation culture tradition part, which has the glorious history and is having the widespread mass base. The Chinese chess procedure is mainly composed of the artificial intelligence and the contact surface design.The artifi

4、cial intelligence mainly manifests the mentality of the computer which plays chess.In other words, the computer how to carry on the ponder and completes the next step by the best move. First it carries on the corresponding searching algorithm, and selects the best move to win. Surface is used to adj

5、ust well the mentality of playing chess.Demonstrating can make users know clearly the process of playing chess, in order to grasp the entire aspect accurately.In this thesis, we first present a survey of the state of the art in Computer Game, especially Computer XiangQi software. Then aiming at addr

6、essing the existing problems in XiangQi software, we design a concise framework for XiangQi chessboard representation, static evaluation function and human-computer interface. Futher, we implement the interface and the XiangQi game program MyChess in VC+ and MFC. It is fair for beginner and we imple

7、ment the man-maching playing chess with cerain chess strengh.Key words：Man-machine gambling XiangQi game tree VC一 引言从1956年正式提出人工智能学科算起，50多年来，获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果。人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。人工智能目前在计算机领域内，得到了愈加广泛的重视。人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。当计算机出现后，随着社会的进步和科技的发展，现

8、在计算机似乎已经变得十分聪明了。1997年5月，IBM公司研制的深蓝（Deep Blue）计算机战胜了国际象棋大师卡斯帕罗夫（Kasparov）。在一些原来只属于人类的工作地方计算机以它的高速和准确性为人类发挥着它的作用。人工智能始终是计算机科学的前沿学科，计算机编程语言和其它计算机软件都因为有了人工智能的进展而得以存在。基于人工智能的博弈程序将人工智能和娱乐有机结合在一起。人工智能结合最强的博弈程序是国际象棋程序。国际象棋程序可以不断学习，因此可以不断的提高。计算机程序不会像人那样下棋，它只通过搜索所有可走的步来确定要走的下一步，而且计算机走的每一步都来自上一步的学习得到。博弈过程可以构建一

9、棵博弈树，将所有的走法罗列出来。博弈树的结点对应一个棋局，分支表示一步着法。根结点表示初始局面，叶节点表示终局。终局可以是赢、输、和三者之一。在深度优先的极大极小树过程中，博弈树的某些部分并不会产生有意义的值，因而无需扩展这一部分。-剪枝过程就是利用这一点，将生成后继与倒推估计值相结合，及时剪掉一些无用分支，从而提高了搜索效率。本设计项目拟将人工智能技术与中国象棋博弈相结合，应用博弈树的剪枝技术和最大最小值原理进行搜索，找出博弈的最佳着法，实现基本的人机对弈过程，在实践中更好地学习并掌握人工智能博弈技术。二 需求分析2.1 系统概述2.1.1 中国象棋的一般描述中国象棋是历史上最为悠久的棋类，

10、早在两千多年前的战国时代就有了中国象棋的记载，它至今仍是华人最喜欢的棋类之一。下棋双方根据对棋局形势的理解和对棋艺规律的掌握，调动车马，组织兵力，协调作战在棋盘这块特定的战场上，进行着象征性的军事战斗。棋盘和棋子： 棋盘由九道直线和十道横线交叉组成。棋盘上共有九十个交叉点，棋子就摆在和活动在这些交叉点上。棋盘中间没有划通直线的地方，叫做“河界” ；划有斜交叉线的地方，叫做“九宫” 。棋子共有三十二个，分为红黑两组，每组共十六个。红棋子：帅一个，车、马、炮、相、仕各两个，兵五个。 黑棋子：将一个，车、马、炮、象、士各两个，卒五个。其中帅与将、仕与士、相与象、兵与卒的作用完全相同，仅仅是为了区分红

11、棋和黑棋。将或帅移动范围：只能在九宫内移动。移动规则：每一步只能沿水平或垂直方向移动一点。士或仕移动范围：只能在九宫内移动。移动规则：每一步只可以沿对角线方向移动一点。象或相移动范围：河界的一侧。移动规则：每一步只可以沿对角线方向移动两点，在移动的过程中不能够穿越障碍。马移动范围：任何位置移动规则：每一步只可以水平或垂直移动一点，再按对角线方面向左或者右移动，移动的过程中不能够穿越障碍。车移动范围：任何位置移动规则：可以水平或垂直方向移动任意个无阻碍的点。炮移动范围：任何位置移动规则：移动起来和车很相似，但它必须跳过一个棋子来吃掉对方的一个棋子。兵移动范围：任何位置移动规则：过河前，每步只能向

12、前移动一点。过河后，它便增加了向左右移动的能力，兵不允许向后移动。2.1.2 国内外象棋发展情况象棋是中华民族精神文明的瑰宝，目前象棋博弈即人机对弈已经成为对计算机的算法以及人工智能研究的经典课题。人机博弈问题是近年来比较热点的问题，机器博弈被专家们描述为人工智能的果蝇，就是说人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。国外的研究人员经过五十多年的对国际象棋博弈系统的探索，终于IBM公司在1997年开发出了超级计算机“深蓝” ，并且战胜了世界国际象棋大师卡斯帕罗夫。这正表明国外计算机人工智能水平确实已经很高。在我国，人工智能也正在飞速发展中。有几个比较有名的

13、中国象棋软件：象棋大师、棋海无涯、象棋奇兵。在中国象棋软件中，核心是搜索技术，比较常见的有：-搜索、极大-极小搜索、迭代深化、置换表法等。2.2 系统运行环境2.2.1 硬件环境CPU：P I I I 内存：512M2.2.2软件环境操作系统：Windows XP2.3 系统功能需求通过对现有游戏工具的研究，游戏本身结构的分析和数据流程实现方式的探讨，本软件在设计上分为人工智能和界面两大部分。人工智能部分实现了如何让计算机下中国象棋，其中涉及人机博弈的基本理论及思想，是该程序的核心部分，同时也是本项目研究的重点所在。光有下棋引擎尚不能满足人机交互的基本要求，因此我们还需要一个界面来作为引擎的载

14、体，使系统更具人性化。 2.4 系统性能需求经济性：作为中国象棋这样的小游戏，其经济成分比重相对较少，主要是支出的费用：其中包括设备购置费、软件开发费用、管理和维护费等。技术性：技术上的可行性分析主要分析现有技术条件能否顺利完成开发工作，硬件、软件配置能否满足开发者的需要，各类技术人员的数量，水平，来源等。中国象棋对弈系统的工作主要是：凭借设计优良的算法和计算机的快速运算能力来搜索出最好的着法，计算机可以在人机对弈中表现出相当高的“智能”。计算机硬件和软件技术的飞速发展，为系统的建设提供了技术条件。市场性：在当前计算机技术飞速发展的大环境下，人工智能和软件技术的更新使中国象棋完全有可能也有能力

15、采用这样先进技术。风险性：包括项目的经济风险、技术风险和市场风险。此项目投入小，技术要求不高，市场潜力比较大。三 概要设计3.1 系统设计目标程序的大概的思想是：首先使用一个数据结构来描述棋局信息，对某一特定的棋局信息由着法生成器生成当前下棋方所有合法的着法并依次存入着法队列。然后通过搜索算法来逐一读取着法并调用局面评估函数对该着法所产生的后继局面进行评估打分，从中选出最有可能导致走棋方取胜的着法。在搜索的过程中还可以采用一些辅助手段来提高搜索的效率。本系统设计了棋盘、棋子和评价函数的表示方法，应用VC和MFC设计并实现了博弈界面，在博弈树理论的基础上采用递归方法实现了-剪枝搜索。该程序用户界

16、面良好，实现了一个具有一定棋力的中国象棋人机对弈程序。程序功能包括：1） 人机对弈；2）棋子、棋盘样式和颜色选择；3）搜索深度设定； 4）新局、结束。3.2 程序设计总体框架整个程序的实现可分为两大部分：1）人工智能部分该部分实现了如何让计算机下中国象棋，其中涉及人机博弈的基本理论及思想，是该程序的核心部分，同时也是本项目研究的重点所在。2）界面及程序辅助部分光有下棋引擎尚不能满足人机交互的基本要求，因此我们还需要一个界面来作为引擎的载体，使系统更具人性化。 四 详细设计4.1 常用搜索算法4.1.1 概述从理论上说，让机器下中国象棋是一个简单的游戏，只要每一步都考虑各种可能的着法，以及每种着

17、法的后继变化，如此下去直至出现一方将死或双方和棋。但是实践操作中，这种策略是不可行的，因为需要考虑的每种着法加起来会是天文数字。不管是人类还是计算机去下棋，都有一整套下棋的理论，人类好几百年前就开始下棋，在近两百年里有很多理论知识，而机器下棋只有五十多年的历史。4.1.2 深度优先搜索图的深度优先遍历的递归定义：假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为

18、从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。深度优先搜索极大极小树的过程，可以表示为一个递归的形式。如图4-1所示的一棵树，共有三层。根结点为A，其子节点有B、C、D三个，而B、C、D也各有若干子节点。以深度优先算法搜索此树时，先进入根结点A，生成其第一个子节点B；然后遍历B，生成B的

19、第一个子节点E；E将其估值返回给父节点B，删掉E，B生成第二个子节点F；F将其估值返回给父节点B，删掉F，B生成第三个子节点G；G将其估值返回给父节点B，删掉G，B在三个叶节点的返回值中取极小值并将此值返回给A，A生成第二个子节点C，同样遍历C及其子节点，得到C的返回值再生成D并向下遍历之；最后A在B、C、D的返回值中取极大值，拥有该极大值的子节点就是下一步要走的方向。ABCEDFGHIJK图4-1 极大极小树从上述过程可以看出，深度优先搜索极大极小树的过程中，任何时候只要保存与其层数相同个数的结点。图4-1所示的树任何时候仅需保存3个结点。仅生成将要搜索的结点，搜索完成的结点可以立即删去以节

20、省空间。4.1.3博弈策略如今的象棋程序把棋局看成博弈树，每个局面表示成棋局树中的一个节点，每个着法代表它的一个分支。这样，树就由双方不同层面上的所有着法组成。令红棋胜的局面值为1，黑棋胜的局面值为-1，和局的值为0。当轮红棋走时，红棋定会选择子节点值为1或0（如果没有值为1的子节点的话）的走法；而轮到黑棋时，黑棋则会选择子节点值为-1或0（如果没有值为-1的子节点的话）的走法。对于中间结点的值有如下计算方法：如果该结点所对应的局面轮到红棋走，则该结点的值是其最佳（对红棋而言）的一个值；如果该结点所对应的局面轮到黑旗走，则该结点的值是其最差（对红旗而言）的一个值。这样，从这棵树的叶子节点倒推向

21、根部，就可以得出所有节点的值。双方就可以从其所面临的棋局中选择一步好棋。然后一步步走向胜利。表示轮到红方走棋表示轮到黑方走棋图4-2 象棋博弈示意图由博弈树的构造可知：在博弈树中，由于叶节点的值可以由估计函数给出，因此中间节点的值可以通过从其孩子节点中或取最大值或取最小值求得，从而最终确定根结点的值。极大极小搜索算法是通过递归的形式完成的。极大极小搜索算法运行时要检查整个博弈树，然后尽可能检查最好的线路。极大极小搜索算法容易理解，但是效率非常低。每次搜索最深一层时，树的大小就呈指数增长。在极大极小搜索的过程中，存在着一定程度的数据冗余。Alpha-Beta搜索能够让我们忽略许多结点的搜索。对于

22、每一个被忽略的非叶子节点来说，这都意味着不仅节点本身，而且节点下面的子树也被忽略掉了，这就导致了Alpha-Beta搜索需要遍历的节点远远于少于极大极小算法所遍历的节点。这也同时意味着对搜索同一棵树来说，Alpha-Beta搜索所花费的时间远远少于极大极小搜索算法所花费的时间。ABCDEF1615表示取极大值的节点表示取极小值的节点图4-3 Alpha剪枝示意如图4-3所示，有一棵极大极小树的片段，节点B的值为16，结点D的值为15，由此我们可以判断结点C的值将小于等于15（取极小值）；而结点A的值为结点Max（B,C）,为16，也就是说不再需要估结点C的其他结点如E、F的值就可以得出父节点A

23、的值了。这样将结点D的后继兄弟结点减去称为Alpha剪枝。BACCD16EF1216表示取极大值的节点表示取极小值的节点图4-4 Beta剪枝示意如图4-4所示，结点B的估值为12，结点D的估值为16，由此我们可以判断结点C的值将大于等于16（取极大值）；而结点A的值为结点Min(B,C)，为12.也就是说不再需要求结点C的其他结点如E、F的值就可以得出父节点A的值了。这样将结点D的后继兄弟结点减去称为Beta剪枝。通过对上述两个博弈树片段的观察我们会发现：Alpha剪枝发生在MAX节点上，即剪裁掉冗余的MAX节点；Beta剪枝发生在MIN节点上，即剪裁掉冗余的MIN节点。将Alpha剪枝和B

24、eta剪枝的思想融入到极大极小搜索算法中，就得到了Alpha-Beta搜索算法。将这个算法用类C的伪代码描述如下：int AlphaBeta(nply,nAlpha,nBeta)if(game over)return Eveluation;/胜负已分，返回估值if(nPly = 0)return Eveluation;/叶子节点返回估值if(Is Min Node)/此句用于判断当前节点是何种节点/是取极小值的节点for(each possible move m)/对每一可能的走法mmake move m;/生产新节点score = alphabeta(nPly 1,nAlpha,nBeta)

25、;/递归搜索子节点unmake move m;/撤销搜索过的节点if(score = nBeta)return nAlpha;/alpha剪枝，抛弃后继节点return nBeta;/返回最小值Else/取极大值的节点for(each possible move m)/对每一可能的走法mmake move m;/生产新节点score = alphabeta(nPly 1,nAlpha,nBeta);/递归搜索子节点unmake move m;/撤销搜索过的节点if(score nAlpha) nAlpha = score;/取极大值if(nAlpha = nBeta)return nBeta;

26、/beta剪枝，抛弃后继节点return nAlpha;/返回最大值同极大极小搜索算法一样，Alpha-Beta搜索算法也有点繁琐，我们不仅要在基数层进行Alpha剪枝，而且还要在偶数层进行Beta剪枝。不过只要用负极大值的形式，这样在任何一层都只进行Beta剪枝，它就会同负极大值算法一样简洁。今天的博弈程序大多采用的都是基于负极大值形式的搜索算法，本次论文也不例外。使用负极大值方法，博弈双方都取极大值。负极大值算法比极大极小算法短小并且简单。负极大值算法的核心在于：父节点的值是各子节点的值的负数的极大值。对于象棋还要注意一点,估值函数必须对谁走棋敏感，也就是说对于一个该红方走棋的局面返回正的

27、估值的话，则对于一个该黑方走棋的局面返回负的估值。在算法原理上，普通的极大极小算法和负极大值算法完全等效，负极大值仅仅是一种更好的表达形式。使用伪代码描述如下：/alpha-beta search with Negamax frameint alphabteta(int nPly,int alpha,int beta)if(Game over)return eval();/胜负已分，返回估值if(nPly=alpha)alpha = score;/保存最大值if(alpha=beta)break;/beta剪枝return alpha;/返回极大值4.2 棋局表示和走法规则的实现4.2.1棋盘

28、和棋子的表示计算机下棋的前提是要让计算机读懂象棋，即计算机应该能够清楚地了解到棋盘上棋子的分布情况以及下棋方所走的所有着法。因而首先我们需要有一套数据结构来表示棋盘上的局面以及着法。棋盘表示主要探讨的是使用什么数据结构来表示棋盘上的信息。通常，用来描述棋盘及其上棋子信息的是一个二维数组。可以用一个910个字节的二维数组来表示中国象棋的棋盘，数组中每一个字节代表棋盘上的一个交点，其值表明这个交点上放置的是一个黑棋还是红棋或是没有棋子，。这种表示方法简单易行。按此方法棋盘的初始情形如图4-5所示。BYTE ChessBoard109=2 ,3 ,6 ,5 ,1 ,5 ,6 ,3 ,2,0 ,0 ,

29、0 ,0 ,0 ,0 ,0 ,0 ,0,0 ,4 ,0 ,0 ,0 ,0 ,0 ,4 ,0,7 ,0 ,7 ,0 ,7 ,0 ,7 ,0 ,7,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 ,11,0 ,0 ,0 ,0 ,0 ,11 ,0,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,9,10,13，12,8,12,13,10, 9图4-5 棋盘初始情形其中棋子分别用数字代表；其中0表示无棋子；黑棋分别用1，2，3，5，6，7代表； 1 表示帅2 表示车3 表示马5表示仕

30、6表示象7表示兵红棋分别用8，9，10，12，13，14代表；8表示将9表示车10表示马12表示仕13表示相14表示卒黑棋的初始位置在棋盘上方，也就是数组的前5行；红棋的初始位置在棋盘的下方，也就是数组的后5行；没有棋子的格子用0表示。图4-6 棋盘界面示意图定义一个棋子位置的结构typedef struct-chessmanpositionBYTEx;BYTEy;CHESSMANPOS;一个走法的结构typedef struct-chessmoveShortChessID;/标明是什么棋子CHESSMANPOSForm；/起始位置CHESSMANPOSTo； /走到的位置IntScore;

31、/值CHESSMOVE；有了对棋盘局面和着法的表示之后，程序才能够完成以下操作：1）生成所有的合法着法；2）执行着法、撤销着法；3）针对某一局面进行评估。因而，棋局表示好比是整个程序（计算机下棋引擎部分）的地基，之后所有的操作都将建立在其基础上。4.2.2 走法规则的实现走法产生就是用来告诉其他部分下一步可以往哪里走的模块。我们的程序需要让计算机在轮到它走子的时候能够执行一步它认为对它最有利的着法，那前提就是它要有若干可供选择的着法，提供所有候选着法的“清单”就是我们的着法生成器所要完成的。之后用搜索函数来搜索“清单”，并用局面评估函数来逐一打分，最后就可以选择出最佳着法并执行了。在中国象棋中

32、，每一种棋子的移动规则各有不同，这样的情形导致可较为复杂的判断。但是我们可以将每种棋子在某一位置上的最大可走步建成一个数据库。在产生走法时直接从数据库中取出数据，进行少量判断就可以算出该棋子的合法步骤。本系统中走法产生采用的基本思想是遍历整个棋盘，当发现有当前下棋方的棋子时先判断它是何种类型的棋子，然后根据其棋子类型而相应地找出其所有合法走法并存入走法队列。在进行走法产生的时候，往往伴随着搜索进行。对于一个局面的所有直接后继，有两种选择：一次产生一种走法然后搜索之；或者一次产生其所有走法然后搜索之。在实际使用中，绝大部分程序都是一次产生一个局面的全部走法，然后调整其搜索顺序。下面给出车的走法程

33、序；/红车或黑车if(nFromY!=nToY&nFromX!=nToX)returnFALSE; /车走直线if（nFromY=nToY） /水平走if(nFromXnToX) /水平向左走for(i=NfromX+1;inToX;i+)if(positionnFromYi!=NOCHESS) /中间有障碍returnFALSE;else/for(i=nToX+1;inFromX;i+)if(positionnFromYi!=NOCHESS)returnFALSE;Else /垂直走if(nFormYnToY)for(j=nFromY+1;jnToY;j+)if(positionjnFrom

34、X!=NOCHESS) /中间有障碍returnFALSE;elsefor(j=nToY+1;jnFromY;j+)if(positionjnFromX!=NOCHESS)returnFALSE;4.3 局面评估及搜索算法4.3.1 棋子的价值评估在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行评价。因而搜索与局面评估是整个下棋引擎的核心。估值是一个通过既有的棋类知识来评估一个局面优劣的过程。棋子的价值评估，简单地说就是评估双方都有哪些棋子在棋盘上。一方的棋子总值就是棋盘上存活的该方棋子乘以棋子价值的和。用一个式子表达如下：Si

35、deValue=Sum（PieceNumberPieceValue）其中PieceNumber是某种棋子的数量，PieceValue是该种棋子的价值，Sum是对各种棋子的总价值求和。如果红色的棋子价值总和大于黑色的价值总和，意味着红方的局势优于黑方。而红黑双方的SideValue之差越大，红方的优势也就越大。但实际上真正的博弈程序几乎不会仅仅利用上面提到的式子来评估棋子价值。在中国象棋中需要考虑以下几个因素：1） 子力总和子力是指某一棋子本身所具有的价值。根据经验，可以让一个车价值500，一个马价值为300，一个兵价值为100等。将的价值为无限大（通常用一个远大于其他棋子的数）。2） 棋子位置

36、棋子位置是指某一方的棋子在棋盘上所占据的位置。在象棋中，如果一位置落在某方棋子的合法走步上，就可以认为呗该方控制。如果某一位置同时落在双方的合法走步上，可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣。能控制更多位置的一方在这项评分上占优势。3） 棋子灵活性棋子的灵活性是指棋子的活动范围，通常是越大越好。评估棋子的灵活性是将一个棋子的所有合法走法罗列出来，乘上该种棋子每一步的价值。Mobility=Sum（MoveNumberMoveValue）其中，MoveNumber是某种棋子的合法走法数量，MoveVulue是该种棋子每一走法的价值，Sum是对所有棋子的灵活性价值求和。Mobil

37、ity就是所有棋子的灵活性分数。4） 棋子关系棋子间的关系也是估值的重要内容之一，将某个棋子把对方棋子威胁看成是一个不利的因素。棋子关系的评估应考虑到该谁走棋的问题。如果某个黑车落在红马的合法走步之内，但此时轮到黑方走棋，则认为黑马遇到的威胁较轻。而如果此时轮到红方走棋，则认为黑马受到的威胁很大，应减去一个相对较大的值了。棋子间关系的评估可以在很大程度上提高估值的精度，通常是博弈估值的必备内容。分析关系时，首先，对将帅的攻击保护应分离出来单独考虑，因为对将帅的保护没有任何意义，一旦其被吃掉整个游戏就结束了。其次，对一个普通子，当它既受到攻击又受到保护的时候要注意如下几个问题：1）攻击者子力小于

38、被攻击者子力,攻击方将愿意换子。2）多攻击或单保护的情况，并且攻击者最小子力小于被攻击者子力与保护者子力之和,则攻击方可能以一子换两子。3）三攻击或两保护的情况，并且攻击者子力较小的二者之和小于被攻击者子力与保护者子力之和,则攻击方可能以两子换三子。当然，上述三条只是覆盖了最常见的几种情况，但是并不全面。而且，在本程序中并没有直接地重新考虑双方兑子之后的控制区域及机动性变化情况。4.3.2搜索算法在搜索过程中，搜索程序通常会评估一个所有经过的节点是否已分出胜负，如果是就直接返回估值而不再对该节点搜索下去。这一估值过程与其他的部分分开置于两个模块中，已分出胜负的局面不需要再向下搜索，而其他的估值

39、过程则要在搜索树的末端才执行。4.4 操作界面对于界面，我们使用Visual C+建立一个基于对话框的MFC应用程序。主要工作都在对话框类的两个文件CChessUIDlg.h和CChessUIDlg.cpp下展开。（一）初始化部分BOOL CCChessUIDlg:OnInitDialog()OnInitDialog()负责的是对话框的初始化。我们把有关中国象棋的棋局初始化情况也放在了这里。初始化的内容包括：1）对引擎部分所用到的变量的初始化；2）对棋盘、棋子的贴图位置的初始化；（二）绘图部分 void CCChessUIDlg:OnPaint() OnPaint()函数负责的是程序界面的绘图

40、。因此，在这里我们要完成棋盘、棋子的显示。 （三）走棋部分（用户动作响应部分）为WM_LBUTTONDOWN消息添加消息响应事件，可得到如下函数：void CCChessUIDlg:OnLButtonDown(UINT nFlags, CPoint point)当用户在窗口客户区按下鼠标左键时,程序就会调用OnLButtonDown(UINT nFlags, CPoint point)函数来进行响应。其中第二个参数CPoint point是我们在本程序中所要用到的，它给出了当鼠标左键被按下时，鼠标指针的位置坐标。OnLButtonDown函数处理如下两种操作：1)如果用户点击鼠标的位置落在己方

41、的棋子上，表示用户选中了该棋子，下一步将移动该子进行走棋。2)如果之前用户已经选过了棋子，那么这一次的点击表达了用户的一次走棋过程。在收到用户传达的走棋信息后，先判断该着法是否合法，如果合法，则执行之。紧接着我们调用引擎的搜索函数计算出计算机对用户着法的应着，然后执行该应着。如此，OnLButtonDown函数里实现了人与机器的对弈（当然每走一步棋，也还需要绘图函数来显示棋盘局面的更新）。五结论在知道老师的热心帮助下，经过三个月的设计工作，终于完成了毕业设计任务：中国象棋对弈系统对弈界面的设计与实现内容涉及人工智能的基本理论以及开发MFC应用程序的一些基础知识。通过这次比较这个正规的软件开发，

42、使我们积累了运用理论知识解决实际问题的经验。通过毕业设计，我真正认识到了在系统开发中需求分析的重要性，好的需求分析可以避免造成资源的浪费。在此次过程中，也出现过许多错误，通过找出问题所在并解决问题的过程更增加了实践的经验。在中国象棋对弈系统的编写过程中，使我们对人工智能也有了一个初步的了解。由于毕业设计时间有限，系统难免还存在很多的不足，需要进一步的改善。总之，在这次设计中，我学到了大量的知识，开阔了视野，也为日后从事软件开发工作奠定了坚实的基础。谢辞首先我要感谢王硕老师。在论文选题、材料的搜集整理及修改过程中他给予了我悉心的指导和关怀,对我的毕业设计十分地负责。不仅如此，王老师时时关心我的毕

43、业设计的进度，经常与我联系，进行交流与讨论。王老师学识渊博，治学严谨，平易近人，在整个毕业设计中给予我很多好的建议。当我遇到难题无法解决时，他总能耐心的给我讲解，使我能够如期完成中国象棋对弈系统的设计与实现。我由衷地感谢王硕老师对本次毕业设计所倾注的大量心血！同时，我要感谢数学与计算机学院的所有老师们，由于他们的传道、授业、解惑，让我学到了扎实的计算机理论知识，使我在本次毕业设计中可以灵活应用，以及为以后的工作和学习奠定了坚实的基础。参考文献1 王小春.PC游戏编程（人机博弈）:重庆大学出版社,2002年 2 陈建春.Visual C+ 高级编程技术开发实例剖析:电子工业出版社,1999年3

44、张海藩软件工程导论第四版.北京：清华大学出版社，2003年4 陆汝.人工智能：北京科学出版社，1995年5 马宪民.人工智能的原理与方法：西北工业大学出版社，2006年6 蔡自兴.人工智能基础：高等教育出版社，2005年7 奥尔费耶夫，伍铁平.人的思维和“人工智能”：中国社会科学出版社，1986年8 姚领田.精通MFC程序设计专著：人民邮电出版社，2006年 9 Franois Dominic Larame.国际象棋程序设计(一)：引言：10 Franois Dominic Larame.国际象棋程序设计(三)：着法的产生:11 Franois Dominic Larame.国际象棋程序设计(四)：基本