中国象棋游戏的设计c++资料

《中国象棋游戏的设计c++资料》由会员分享，可在线阅读，更多相关《中国象棋游戏的设计c++资料（21页珍藏版）》请在金锄头文库上搜索。

1、中国象棋游戏的设计与实现中国象棋游戏的设计与实现 摘摘 要要 本文首先研究了中国象棋在计算机中的表示问题，接着讨论如何产生着法 一系列相关内容。其次研究了博弈树的极小极大搜索技术及在此基础上发展起 来的 Alpha-Beta 剪枝算法，使用 MFC 文档视图体系结构和 Visual C+开发工具， 实现了一个具有一定棋力的中国象棋人机对弈程序。 象棋程序的实现可以被分为人工智能和界面程序辅助两大部分。人工智能 部分主要体现计算机的下棋思路，既计算机如何进行思考并以最佳走法完成下 一步，先由相应的搜索算法进行搜索，并对各种可能的走法进行估值，从中选 择胜利面最大的一步；而界面及程序辅助部分主要便

2、于用户通过以前的下棋步 骤，更好地调整下棋思路，着法显示使用户能够清楚地知道下棋过程，更准确 地把握整个局面。 关键词：关键词：中国象棋；人工智能；博弈树；Alpha-Beta 搜索 The Design and Implementation of Chinese Chess Abstract The implementation of a chess program can be decomposed into two major parts: the artificial intelligence and the user interface and program assist. The

3、 part of artificial intelligence shows the way of computer thinking, and which step is the best step would be decided by it. Firstly, the computer uses search algorithms to search, and then evaluates every impossible step, finally choses the best one, the other part is used for the player to adjust

4、his thought to the currently phases. The display of step list makes player know the process of chess distinctly, and let player make a better choice. This paper firstly studies how to represent a chess board in computer, then discusses how to generate legal moves. Secondly, this paper studies the mi

5、ni-max searching procedure of Game Tree, and the Alpha-Beta pruning algorithm. A Chess- playing system is designed and developed, which is built on the integrated computer MFC SDI document view architecture by using Visual C+. Key words: Chinese chess; Artificial Intelligence; Game tree; Alpha-Beta

6、searching 目目 录录 论文总页数：22 页 1引言.1 1.1象棋设计背景和研究意义 1 1.2象棋设计研究方法 1 2人工智能算法设计.2 2.1棋局表示 3 2.2着法生成 4 2.3搜索算法 5 2.4历史启发及着法排序 9 2.5局面评估 9 2.6程序组装 11 3界面及程序辅助设计.12 3.1界面基本框架 12 3.2多线程 13 3.3着法名称显示 14 3.4悔棋和还原 15 4系统实现.16 结 论.19 参考文献.20 致 谢.21 声 明.22 1引言引言 1.1 象棋设计背景和研究意义象棋设计背景和研究意义 电脑游戏行业经过二十年的发展，已经成为与影视、音乐

7、等并驾齐驱的全 球最重要的娱乐产业之一，其年销售额超过好莱坞的全年收入。游戏，作为一 种娱乐活动。早期的人类社会由于生产力及科技的制约，只能进行一些户外的 游戏。随着生产力的发展和科技进步，一种新的游戏方式电子游戏也随之 诞生。 当计算机发明以后，电子游戏又多了一个新的载体。电子游戏在整个计算 机产业的带动下不断地创新、发展着。自从计算机发明，向各个领域发展，到 成为我们现在每天工作和生活必不可少的一部分的这个过程中，电子游戏也逐 步渗入我们每个人的娱乐活动中。而计算机已经普及的今天，对于可以用计算 机进行程序编辑的人来说，开发属于自己的游戏，已经不再是梦想。事实上， 个人计算机软件市场的大约

8、 80%销售份额是来自游戏软件。棋牌游戏属于休闲 类游戏，相对于角色扮演类游戏和即时战略类游戏等其它游戏，具有上手快、 游戏时间短的特点，更利于用户进行放松休闲，为人们所喜爱，特别是棋类游 戏，方便、快捷、操作简单，在休闲娱乐中占主要位置。作为中华民族悠久文 化的代表之一，中国象棋不仅源远流长，而且基础广泛，作为一项智力运动， 中国象棋开始走向世界。 随着计算机处理速度的飞速提高，人们很早就提出了疑问：计算机是否会 超越人类？世界国际象棋大师已被计算机打败，计算机已经超过了人类？而人 工智能是综合性很强的一门边缘学科，它的中心任务是研究如何使计算机去做 那些过去只能靠人的智力才能做的工作。因此

9、，对游戏开发过程中的人工智能 技术的研究自然也就成了业界的一个热门研究方向。 1.2 象棋设计研究方法象棋设计研究方法 对于象棋来说，核心设计主要包括人工智能算法的以及整个游戏中界面及 程序辅助部分的实现，主要用 Visual C+ 进行开发，里面的 MFC 类库，使游 戏开发更加方便，并利用人工智能相关搜索算法实现人工智能的着法生成，从 而完善整个游戏的功能。 本文的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈 程序。 该程序功能包括： *人机对弈； *搜索深度设定； （电脑棋力选择） *悔棋、还原； *着法名称显示； 整个程序的实现可分为两大部分： 一、人工智能算法设计（计算

10、机下棋引擎） 该部分实现了如何让计算机下中国象棋，其中涉及人机对弈的基本理论及 思想，是该程序的核心部分，同时也是本项目研究的重点所在。 二、界面及程序辅助设计 光有下棋引擎尚不能满足人机交互的基本要求，因此还需要一个框架（界 面）来作为引擎的载体，同时提供一些诸如悔棋，还原之类的附属功能（程序 辅助） 。 下面分别介绍各部分实现。由于界面及程序辅助部分涉及内容宽泛而又繁 琐，因而本文只介绍其中重点部分。 2人工智能算法设计人工智能算法设计 程序的基本框架： 从程序的结构上讲，大体上可以将引擎部分划分为四大块： 棋局表示； 着法生成； 搜索算法； 局面评估。 程序的大概的思想是： 首先使用一个

11、数据结构来描述棋局信息，对某一特定的棋局信息由着法生 成器生成当前下棋方所有合法的着法并依次存入着法队列。然后通过搜索算法 来逐一读取着法并调用局面评估函数对该着法所产生的后继局面进行评估打分， 从中选出一个最有可能导致走棋方取胜的着法。在搜索的过程中还可以采用一 些辅助手段来提高搜索的效率。其过程如下所示（图 1）： 当前棋局 着法生成器 m1m2m3 mn 搜索算法 搜索辅助 局面评估 着法队列 图 1 程序结构图 下面将分别介绍程序各个部分： 2.1 棋局表示棋局表示 计算机下棋的前提是要让计算机读懂象棋。所谓读懂，即计算机应该能够 清楚地了解到棋盘上的局面（棋盘上棋子的分布情况）以及下

12、棋方所走的每一 种着法。因而首先需要设计一套数据结构来表示棋盘上的局面以及着法。 对于棋盘局面的表示可采用传统而简单的“棋盘数组” 。即用一个 9*10 的 数组来存储棋盘上的信息，数组的每个元素存储棋盘上是否有棋子。这种表示 方法简单易行（缺点是效率不是很高） 。按此方法棋盘的初始情形如下所示： BYTE CChessBoard910 = R, 0, 0, P, 0, 0, p, 0, 0, r, H, 0, C, 0, 0, 0, 0, c, 0, h, E, 0, 0, P, 0, 0, p, 0, 0, e, A, 0, 0, 0, 0, 0, 0, 0, 0, a, K, 0, 0,

13、 P, 0, 0, p, 0, 0, k, A, 0, 0, 0, 0, 0, 0, 0, 0, a, E, 0, 0, P, 0, 0, p, 0, 0, e, H, 0, C, 0, 0, 0, 0, c, 0, h, R, 0, 0, P, 0, 0, p, 0, 0, r ; 给所有棋子定义一个值： #define R_BEGIN R_KING #define R_END R_PAWN #define B_BEGIN B_KING #define B_END B_PAWN #define NOCHESS 0 /没有棋子 黑方：#define B_KING 1 /黑帅 #define B

14、_CAR 2 /黑车 #define B_HORSE 3 /黑马 #define B_CANON 4 /黑炮 #define B_BISHOP 5 /黑士 #define B_ELEPHANT 6 /黑象 #define B_PAWN 7 /黑卒 红方：#define R_KING 8 /红将 #define R_CAR 9 /红车 #define R_HORSE 10/红马 #define R_CANON 11/红炮 #define R_BISHOP 12/红士 #define R_ELEPHANT 13/红相 #define R_PAWN 14/红兵 判断颜色： #define IsBla

15、ck(x) (x=B_BEGIN if (val alpha)/保留最大值 alpha = val; return alpha; 2.4 历史启发及着法排序历史启发及着法排序 既然 Alpha-Beta 搜索算法是在“最小-最大”的基础上引入“树的裁剪” 的思想以期提高效率，那么它的效率将在很大程度上取决于树的结构如果 搜索了没多久就发现可以进行“裁剪”了，那么需要分析的工作量将大大减少， 效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪” 操作，那此时“裁剪”也已经失去了它原有的价值（因为你已经分析了所有情 况，这时的 Alpha-Beta 搜索已和“最小-最大”搜索别无

16、二致了） 。因而，要想 保证 Alpha-Beta 搜索算法的效率就需要调整树的结构，即调整待搜索的结点的 顺序，使得“裁剪”可以尽可能早地发生。 可以根据部分已经搜索过的结果来调整将要搜索的结点的顺序。因为，通 常当一个局面经过搜索被认为较好时，其子结点中往往有一些与它相似的局面 （如个别无关紧要的棋子位置有所不同）也是较好的。由 J.Schaeffer 所提出 的“历史启发” （History Heuristic）就是建立在这样一种观点之上的。在搜 索的过程中，每当发现一个好的走法，就给该走法累加一个增量以记录其“历 史得分” ，一个多次被搜索并认为是好的走法的“历史得分”就会较高。对于即 将搜索的结点，按照“历史得分”的高低对它们进行排序，保证较好的走法 （“历史得分”高的走法）排在前面，这样 Alpha-Beta 搜索就可以尽可能早地 进行“裁剪” ，从而保证了搜索的效率。 对于着法的排序可以使用各种排序算法，在程序中采用了归并排序。归并 排序的空间复杂