毕业论文-基于VC的智能中国象棋系统的设计与实现08853.doc
《毕业论文-基于VC的智能中国象棋系统的设计与实现08853.doc》由会员分享,可在线阅读,更多相关《毕业论文-基于VC的智能中国象棋系统的设计与实现08853.doc(49页珍藏版)》请在三一文库上搜索。
1、武汉理工大学 毕业设计(论文) 基于基于 VCVC 的智能中国象棋系统的设计与实现的智能中国象棋系统的设计与实现 学院(系): 专业班级: 学生姓名: 指导教师: 智能中国象棋系统的设计与实现智能中国象棋系统的设计与实现 摘摘 要要 人工智能(AI)中国象棋系统是将计算机知识和中国象棋知识结合起来的一种新型的 游戏方式。智能中国象棋系统在此基础上实现人与机器的对弈,突破了以往传统象棋 游戏只能人与人对战的限制,使中国象棋这一古老的游戏形式焕发出蓬勃朝气。 本文结合在中国象棋机器博弈方面的实践经验,在分析了中国象棋游戏需求基础 上,设计并实现了智能中国象棋系统。该系统包括人人对战、人机对战、制作
2、棋谱、 播放棋谱以及挑战英雄榜等功能模块。人人对战规则明确,包含了中国象棋所有的着 法;人机对战中电脑棋力分为简单、中等、困难三个等级,方便了不同水平人群的选 择;制作和播放棋谱模块容易操作,方便学习;挑战英雄榜则为象棋游戏增加了乐趣。 本系统的实现满足了人们对中国象棋的基本需求,解决了传统象棋游戏学习性差、 棋谱不易保存、不易演示等问题。 关键词:计算机博弈,中国象棋,人机对战,制作棋谱,搜索算法 Intelligent Chinese Chess System Design and Implementation Abstract Artificial Intelligence (AI) C
3、hinese Chess System is a new games way which combines with computer knowledge and Chinese Chess knowledge. Intelligent Chinese Chess System on the basis of it which completes the game between human and computer , breaking the traditional chess games restriction that only can play against people. So
4、that the ancient game of Chinese chess become prosperity . With the practical experience in Chinese chess computer game, a detailed analysis and research has been done .Based on those, I designed and implemented the Intelligent Chinese Chess System .This system includes the game against human ,the g
5、me between computer and human ,make chess manual ,play chess manual and hero list functions .The game against human function has all the Chinese Chess rules and they are very clear.In the game between computer and human function ,computer thinking depth is divided into simple,medium and difficulty.I
6、t facilitate the choice of different levels. Making and playing chess manual fuctions are easy to operating and learning. Hero list fuction adds much fun to chess game. This system satisfied the basic demand of people to Chinese chess and solved the studying hard and the theoretical is not easy to m
7、aking and playing of the traditional chess game. Key Words: Computer Game, Chinese Chess, Game between Human and Computer, Make Chess Manual, Search Tecniques 目目 录录 1 绪论.1 1.1 选题的背景和意义1 1.2 发展动态及研究现状1 1.3 系统概述2 1.4 本文的主要工作4 1.5 论文结构4 2 系统的分析和设计.5 2.1 数据结构(DATA STRUCTURE).5 2.1.1 棋盘的基本表示法(Board Repre
8、sentions)5 2.2 着法生成(MOVE GENERATION).7 2.2.1 模板匹配法.7 2.2.2 预置表法.8 2.3 局面评估 .8 2.3.1 估值函数(Evaluation Function) 9 2.3.2 估值的速度与博弈性能.10 2.3.3 估值函数的优化.10 2.4 博弈树搜索技术 .12 2.4.1 基本搜索算法.13 2.4.2 高级搜索算法.15 2.5 开局库设计 .16 2.5.1 开局库的作用.16 2.5.2 实现开局库的主要方法.16 3 系统的实现.19 3.1 系统的整体规划 .19 3.2 象棋界面的实现19 3.3 对弈功能的实现2
9、4 3.4 制作和演示棋谱的实现28 3.5 象棋英雄榜的实现31 3.6 开局库的实现 .32 3.7 程序说明 .32 3.8 实验结果及分析 .32 结论.34 致 谢.36 参考文献.37 附 录.38 附录 A:A INTRODUCTION ABOUT CHINESE CHESSA38 附录 B:关于中国象棋的一些简要介绍 41 1 绪论 1.1 选题的背景和意义 在人类文明发展的初期,人们便开始进行棋类博弈的游戏了。近几十年来,随着 计算机硬件和软件技术的不断发展,人们开始对计算机能否战胜人脑这个话题产生了 浓厚的兴趣。从 1980 开始,电脑博弈便开始逐渐大规模地向人类智能发起了
10、挑战,到 了 1997 年,IBM 超级电脑 Deeper Blue 击败了当时的国际象棋冠军卡斯帕罗夫,成为 了人工智能挑战人类智能发展的一个重要里程碑。 许多学者认为,对于人工智能研究而言,象棋的重要作用不亚于遗传学研究中的 果蝇。人类对机器博弈的研究衍生了大量的研究成果,这些成果对更广泛的领域产生 了重要影响。人工智能的先驱们曾认真的表明:如果能掌握下棋的本质,也许就掌握 了人类智能行为的核心;那些能够存在于下棋活动中的重大原则,或许就存在于其它 任何需要人类智能的活动中。因此对于中国象棋人机博弈问题的研究意义重大。 而当今对中国象棋的研究也正如专家们所期望的那样在蓬勃地发展着。中国象棋
11、 不仅是中国传统智慧的体现,同时也具有着比国际象棋更高的复杂度,如何让机器具 有智能,与人进行对弈成了本课题研究的一个重要问题。通过本课题的研究,掌握智能知 识的表示与计算、搜索,不仅是对所学知识的锻炼,更是在人工智能领域的有意义的 探索 1.2 发展动态及研究现状 和国际象棋博弈系统相比,中国象棋博弈系统的研究起步比较晚,是八十年代开始 的。在这个时候计算机国际象棋取得重大突破,1983 年美国贝尔公司的电脑参加美国 人类比赛,取得了不错的成绩,被授予大师称号。于是有专家学者想如何将国际象棋 电脑技术移植到中国象棋上来,以带动中国象棋电脑较快的发展;同时中国象棋从技 术研究进入理论研究,有关
12、开局、中局、残局理论以及象棋对策相继建立起来,为中 国象棋计算机博弈提供了理论基础。 1981 年张耀腾发表的人造智慧在电脑象棋上的应用 ,他提出审局函数为静态子 力值,棋子位置值,棋子灵活度值,威胁与保护等四项之和。但该文主要以残局做实 验,缺乏完整对局的考虑。1982 年廖嘉成发表的利用计算机象棋的实验就进了一 步,包括开局、中局、残局。1983 年黄少龙、周玉龙合作制成象棋排局系列软盘 专家系统与人对弈。 到了 90 年代,中国象棋计算机博弈的应用开始发展起来,人们研究出了各种博弈 软件。比较著名的软件有台湾的吴身润的中国象棋 、光谱公司出品的将族 、 晟业编制的象棋水浒战 、 象棋武林
13、帖 。而且涉足这个领域比较早的是台湾的一些 专家学者。近几年,在内地也涌现出一批对中国象棋人机博弈问题感兴趣的高校、单 位及个人,而且进入 21 世纪以后,中国象棋计算机博弈的研究受到越来越多的学者的 关注,比较著名的博弈软件如表 1 所示。 表表 1-1 著名中国象棋计算机博弈程序著名中国象棋计算机博弈程序 程程序序 作作者者 地地区区 纵纵马马奔奔流流 涂涂志志坚坚 广广州州中中山山大大学学 谢谢谢谢象象棋棋大大师师 法法国国电电脑脑公公司司 法法国国 ELP 郑郑武武尧尧、陈陈志志吕吕 台台湾湾 SHIGA(象象棋棋世世家家) 郑郑明明政政、颜颜士士净净 台台湾湾 SHCC(神神乎乎棋棋
14、技技) SAI team 美美国国 Cyclone(象象棋棋旋旋风风) 陈陈朝朝阳阳 北北京京 CONTEMPLATION 千千虑虑 陈陈志志昌昌、许许舜舜钦钦 台台湾湾 棋棋天天大大圣圣 王王骄骄 东东北北大大学学 象象棋棋奇奇兵兵 赵明阳赵明阳 中国中国 每年也会有中国象棋计算机博弈的国际奥林匹克大赛,这其中有 2003 年的世界 冠军“纵马奔流” ,2004 年的世界冠军“谢谢象棋大师” ,2005 年的世界冠军“象棋奇 兵” ,2006、2007 年的世界冠军“棋天大圣” , 2008 年的世界冠军“倚天” 。 这些都 体现了中国象棋的人机博弈的研究的受关注程度;虽然如此,但中国象棋的
15、人机博弈的 研究比国际象棋还是晚了几十年,并且在搜索算法等方面的研究还与国际象棋相距甚 远。 1.3 系统概述 1、棋盘表示(Board Representations) 棋盘表示就是使用一种数据结构来描述棋盘及棋盘上的棋子,以方便计算机处理。 中国象棋的棋盘表示还没有形成统一的或者公认的哪种为最佳的数据格式。最直观也 是最典型的方式是使用 10x9 的二维棋盘数组表示,也有使用棋子数组,扩展棋盘棋 子数组等,棋盘的数据表示直接影响到程序的时间及空间复杂度。 2、着法生成(Move Generation) 着法生成就是找到某个局面所有合法的走法。它与棋盘表示的数据结构密切相关, 一般需要大量繁
16、琐的判断,伴随着搜索进行,并且调用频繁,是相当复杂而且耗费运 算时间。在一定程度上形成了程序的性能瓶颈。当前为了提高着法生成的效率通常采 用以空间换时间的方法:与先求出棋子的在某位置的所有走法。 3、评估函数(Evaluation Function) 评估函数就是对博弈过程中实际局面的好坏做出判断或打分,它影响着博弈局发 展的趋势。目前象棋程序的静态评价函数主要有子力价值,子力灵活性,子力对棋盘 的控制,和一些对棋局影响比较大的重要特征计算几部分组成。它与着法生成一样十 分耗费运算时间,如何加速评估函数的速度十分关键。 4、搜索技术(Search Techniques) 搜索技术与算法是象棋博
17、弈系统程序的核心,是决定搜索效率的关键所在。再好 的硬件也无法实现“象棋不败算法” 。如何在成指数递增的状态空间中寻求最优解,是 象棋博弈系统的一个重要的方向。 “蛮力搜索”肯定是不可取的。如何有选择地搜索, 既瞄准最有希望的方向局部加深,又不遗漏其它存在最优解的可能。目前主要是使用 - 剪枝算法加上迭代深化、置换表、历史启发等策略的综合应用。 5、开局库(Opening Book) 把开局几步的走法建成数据库供程序直接取用。实践表明无论搜索引擎如何出色, 在开局搜索过若干层后,得到的可能只是一些很笨拙的开局。直接从开局库中取就可 以大大加快开局时的运行速度和提高开局的质量。开局库一般是采用
18、zobrist 哈希技术 加以实现。 6、机器自学习(Machine Learning) 机器自学习之一是针对评估函数。对弈过程机器自动调整评估函数参数的权值进行 优化,发现一些棋子之间潜在的联系:之二是采用模式识别,学习的过程是通过对博弈 过程的识别统计,自行丰富模式库中的内容,以提高程序的博弈性能。 1.4 本文的主要工作 本文的主要工作是将博弈策略应用到中国象棋程序的设计与实现上,建立一个完 整的中国象棋计算机博弈系统,研究工作主要集中在以下几个方面: 1、棋盘表示与走法生成 从操作速度(性能)以及使用方便与否考虑,本象棋博弈系统从带位行位列信息的扩 展棋盘棋子联系数组着手进行研究。然后
19、根据棋盘表示获得所有棋子的走法预生 成数组。在产生走法时直接从中取出数据,进行少量判断以得到该棋子的合法走步。 2、估值函数 如何快速有效的对一个局面进行评估需要从速度和知识的两个角度进行考虑:一般 知识越多估值越准确,但速度也慢下来。本系统采用通用的静态估值方式,同时在估 值时结合走法预生成数组,使估值的速度有很大提升。 3、搜索技术 博弈树搜索技术它很大程度上独立于具体的计算机博弈程序。本文讨论了 - 剪 枝搜索算法及其各种增强手段:包括窗口原则、置换表(内存增强);历史启发表(节点 顺序调整);迭代深化(时间控制)等。如何把各种增强手段有机组合起来达到最优,文 章对基于迭代加深、置换表、
20、历史启发的 Negascout 算法进行改进。 1.5 论文结构 第一章阐述了选题背景,课题的国内外研究现状及课题的主要工作和文章的章节 安排。 第二章第一部分首先介绍中国象棋程序的一些基本数据结构,着重研究了扩展的 棋盘棋子联系数组棋盘;在此基础上实现所有棋子的走法预生成数组,以提高搜 索过程中走法产生的效率。第二部分研究本系统的着法生成,包括预置表法和模板匹 配法,进一步提高了搜索效率。第三部分描述本系统的评价函数架构,着重描述了静 态估值方法,分析了其不足,并提出了解决之道。包括子力分数、子力灵活度评价、 棋盘控制等并与走法预生成数组结合以提高估值速度。第四部分实现了博弈树的 - 剪枝算
21、法并简要介绍各种搜索策略。第五部分阐述了开局库的设计原理。 第三章给出实验环境和程序实现。 第四章是全文的总结及展望。 2 系统的分析和设计 2.1 数据结构(Data structure) 数据结构是一个程序的骨架,选择一种好的数据结构可以使程序的运行效率大大 提高。 2.1.1 棋盘的基本表示法(Board Representions) 棋盘表示就是使用一种数据结构来描述棋盘上的信息,以便程序知道博弈的状态。 棋盘的数据表示直接影响到程序的时间及空间复杂度。为了追求更高效率,研究人员 针对中国象棋提出了多种不同的表示方法。 中国象棋的棋盘表示中最典型的是用一个 109 的二维字节(byte
22、)数组,数组中每 个元素代表棋盘上的一个交点,其值表明这个交点上放置的是一个什么棋子或是没有 棋子 从棋子的角度考虑,如果把棋盘看成是一个平面坐标系,可以知道每一个棋子的位 置信息:小于 10 的横坐标和小于 11 的纵坐标;又在棋盘上最多 32 个棋子,故可以用一 个 32 个字节的一维数组表示所有 32 个棋子的位置,其中每个字节的高 4 位表示该棋 子的横坐标,低 4 位表示棋子的纵坐标。而己被吃掉的棋子用坐标范围以外的数表示。 这样棋盘信息就被装入这 32 个字节中。当然也可以把棋盘看作一维的,每个元素保存 直接的位置信息。 两种棋盘表示方法:一是做一个棋盘数组;二是做一个棋子数组。棋
23、盘数组中由 棋子的位置获得棋子的类型可以在常数时间内完成,但由棋子的类型获得棋子的位置 需要遍历;在棋子数组中由棋子的类型获得棋子的位置可以在常数时间内完成,但由 棋子的位置获得棋子的类型操作繁琐。如果一个程序同时使用这两个数组,那么获得 棋子的类型和棋子的位置都可以在常数时间内完成。这就是“棋盘棋子联系数组” , 它的技术要点是: (l) 同时用棋盘数组和棋子数组表示一个局面,棋盘数组和棋子数组之间可以互相 转换。 (2) 随时保持这两个数组之间的联系,棋子移动时必须同时更新这两个数组。在 棋盘上删除一个棋子,需要做两个操作(分别修改棋盘数组和棋子数组)。同样,添加一 个棋子时也需要两个操作
24、。 “棋盘棋子联系数组“最大的优势是:对于着法产生过程,可以逐一查找棋子数 组,如果该子没有被吃掉,就产生该子的所有合理着法,由于需要查找的棋子数组的 数量(每方只有 16 个棋子能走)比棋盘格子的数量(90 个格子)少得多,因此联系数组的 速度要比单纯的棋盘数组快很多。同时“棋盘棋子联系数组”是很多改进的棋盘 的基础。 2.1.2 改进型棋盘结构 在计算机上面,位运算比一般的加减乘除及取余运算快得多。如果能在寻找棋子 和定位棋子上使用位运算代替加减乘除和取余,这将很大程度上提高运算速度。所以, 人们把“棋盘棋子联系数组“进行扩展:把棋盘做成 1616 的大小,这样得到 行号可以用 16 除,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业论文 基于 VC 智能 中国象棋 系统 设计 实现 08853
链接地址:https://www.31doc.com/p-3945443.html