《毕业设计：基于UML的五子棋人机对弈设计》由会员分享，可在线阅读，更多相关《毕业设计：基于UML的五子棋人机对弈设计（90页珍藏版）》请在金锄头文库上搜索。
1、本科毕业设计（论文）基于UML的五子棋人机对弈专 业：计算机科学与技术学生 姓名：简越 学 号：060104010084 指导 教师：王璿 答辩 日期：2010-6-9 IIIIII燕山大学本科毕业设计（论文）摘 要人工智能是近年来很活跃的研究领域之一。机器学习和博弈是人工智能研究的重要分支。国内外对博弈的研究已经较为广泛，特别是 IBM 的国际象棋程序“深蓝”，已经达到了人类的世界冠军水平。但是这些程序或者需要经过大量训练，或者采用死记硬背的学习方法，或者是采用大规模搜索算法实现，难以避免“组合爆炸”的危机，因此，一个真正“智能”的，有学习能力的高效率的博弈策略还有待进一步研究。五子棋是一种
2、深受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。然而当我们与电脑对战时，您知道电脑是怎样像人脑一样进行思考的吗？本文设计和实现了一个人机对战的五子棋游戏，对整个程序进行UML建模，以减少程序开发周期。搜索引擎在基本的极大极小的搜索方法上，进行改进的NegeScout的方法，同时加入历史启发与置换表，这样减少搜索次数、时间，增加搜索效率。并介绍五子棋程序的数据结构、估值函数、胜负判断方法和整个搜索算法过程。关键词： 人工智能；五子棋；UML，极大极小搜索；NegeScout；燕山大学本科生毕业设计（论文）AbstractArtificial Intelligence is
3、a very active research in recent years, one of the areas.Artificial intelligence, machine learning and game is Important branch of research.Game at home and abroad have been widely investigated, especially IBMs International Chess program Deep Blue, has reached the level of the human world champion.
4、But these procedures or need to go through a lot of training, or learning by rote, or by large-scale search operator method to achieve, it is difficult to avoid the combinatorial explosion of the crisis, therefore, a truly smart, there are school learning ability of high-efficiency game strategy rem
5、ains to be studied further. Gobang Game is a popular game loved the general public, the rules are simple, varied and very full of fun and recreational.However, when we and the computer on the war, you know how the computer is like a human brain like to think of it?This machine is designed and implem
6、ented a battle of the backgammon game, the whole process UML modeling, to reduce process development cycle.Search engine in the basic mini-max search methods, ways to improve the NegeScout, while adding historical inspiration and replacement table, so to reduce the number of searches, time, and incr
7、ease the search efficiency.And introduced the Go-Moku program data structures, the valuation function, determine the outcome of the process methods and the search algorithm.KeywordsArtificial Intelligence; Gobang Game; UML ;Mini-max; NegeScoutII目 录摘要IAbstractII第1章 绪论11.1 课题背景11.2 课题来源与研究意义21.2.1 课题来
8、源21.2.2 课题研究意义31.3 论文结构4第2章 开发工具的介绍和系统配置52.1 系统环境配置52.2 开发环境C+技术52.2.1概述52.2.2 C+的优势52.3 开发工具Visual C+6.082.3.1 Visual C+ 6.0概述82.3.2 Visual C+ 6.0优势82.4 本章小结9第3章 系统分析113.1 系统需求113.2 系统的可行性研究113.2.1 技术可行性112.2.2 经济可行性122.2.3运行可行性122.2.4法律可行性123.3 功能分析123.3.1 系统的功能需求123.3.2 系统的业务流程图133.4 本章小结13第4章 系统
9、UML建模154.1 数据结构154.2下棋过程164.2.1人下棋时序图164.2.2电脑下棋时序图174.3人机博弈活动图184.4本章总结19第5章 总体设计205.1 棋盘表示205.2 走法产生器215.3 搜索引擎215.3.1 NegeScout算法215.3.2 置换表275.3.3 历史启发285.4 估值核心295.4.1棋型分值表305.4.2对棋盘位置估值：305.4.3 估值函数：315.5 胜负判断315.5 系统界面设计325.6 本章小结34第6章 系统实现356.1 系统测试356.2 系统运行356.3本章小结38结论39参考文献40致谢42附录1I附录2V
10、I附录3：XI附录4：XV附录5：XXVIII9第1章 绪论第1章 绪论1.1 课题背景在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。在人工智能领域内，博弈是很重要的一个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算机智能更加靠近人类智能。电脑博弈是人工智能研究的一个方向，到了近50年前，随着电子计算机的诞生，科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战，香农(1950)与图灵(1953)提出了对棋类博弈程序的描述，随着电脑硬件和软件的高速发展，从1980开始，电脑博弈便开始逐渐大规模地向人的智能发起了挑战，到了1997年，IBM超级电脑Deeper Blue击
11、败了当时国际象棋世界冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要旅程碑。五子棋相传起源于四千多年前的尧帝时期，比围棋的历史还要悠久，可能早在“尧造围棋”之前，民间就已有五子棋游戏。有关早期五子棋的文史资料与围棋有相似之处，因为古代五子棋的棋具与围棋是完全相同的。在上古的神话传说中有“女娲造人，伏羲做棋”一说，增山海经中记载：“休舆之山有石焉，名曰帝台之棋，五色而文状鹑卵。”李善注引三国魏邯郸淳艺经中曰：“棋局，纵横各十七道，合二百八十九道，白黑棋子，各一百五十枚”。这段虽没明讲是何种棋类，但至少知道远古就以漂亮的石头为棋子。因而规则简单的五子棋也可能出自当时，并是用石子作棋子。亦有
12、传说，五子棋最初流行于少数民族地区，以后渐渐演变成围棋并在炎黄子孙后代中遍及开来。在古代，五子棋棋具虽然与围棋相类同，但是下法却是完全不同的。正如辞海中所言，五子棋是“棋类游戏，棋具与围棋相同，两人对局，轮流下子，先将五子连成一行者为胜。”传统五子棋的棋具与围棋相同，棋子分为黑白两色，棋盘为19X19，棋子放置于棋盘线交叉点上。两人对局，各执一色，轮流下一子，先将横、竖或斜线的5个或5个以上同色棋子连成不间断的一排者为胜。因为传统五子棋在落子后不能移动或拿掉，所以也可以用纸和笔来进行游戏。五子棋游戏在国际上也十分流行。例如，韩国人把五子棋称为“情侣棋”，暗示情人之间下五子棋有利于增加情感的交流
13、；欧洲人称其为“绅士棋”，代表下五子棋的君子风度胜似绅士；日本人则称其为“中老年棋”，说明五子棋适合中老年人的生理特点和思维方式；美国人喜欢将五子棋称为“商业棋”，也就是说，商人谈生意时可边下棋边谈生意，棋下完了生意也谈成了。1.2 课题来源与研究意义1.2.1 课题来源“人工智能”(Artificial Intelligence，简称AI)一词最初是在1956 年Dartmouth学会上提出的。从那以后,研究者们发展了众多理论和原理,人工智能的概念也随之扩展。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或者人自
14、身的智能程度有没有高到可以创造人工智能的地步，等等。但总的来说，“人工系统”就是通常意义下的人工系统。关于什么是“智能”，就问题多多了。这涉及到其它诸如意识（consciousness）、自我（self）、思维（mind）（包括无意识的思维（unconscious_mind）等等问题。人唯一了解的智能是人本身的智能，这是普遍认同的观点。但是我们对我们自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”了。因此人工智能的研究往往涉及对人的智能本身的研究。其它关于动物或其它人造系统的智能也普遍被认为是人工智能相关的研究课题。人工智能目前在计算机领
15、域内，得到了愈加广泛的重视。并在机器人，经济政治决策，控制系统，仿真系统中得到应用。著名的美国斯坦福大学人工智能研究中心尼尔逊教授对人工智能下了这样一个定义：“人工智能是关于知识的学科怎样表示知识以及怎样获得知识并使用知识的科学。”而另一个美国麻省理工学院的温斯顿教授认为：“人工智能就是研究如何使计算机去做过去只有人才能做的智能工作。”这些说法反映了人工智能学科的基本思想和基本内容。即人工智能是研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人的智力才能胜任的工作，也就是研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论、方法和技术。人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪（基因
