基于UML的五子棋人机对弈Word文档下载推荐.docx
《基于UML的五子棋人机对弈Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《基于UML的五子棋人机对弈Word文档下载推荐.docx（72页珍藏版）》请在冰点文库上搜索。
题目类型
1.理工类：
工程设计（）；
工程技术实验研究型（）；
理论研究型（）；
计算机软件型（√）；
综合型（）。
2.管理类（）；
3.外语类（）；
4.艺术类（）。
题目性质
1.毕业设计（√）2.论文（）
题目来源
科研课题（）生产实际（）自选题目（√）
主
要
内
容
1.掌握UML建模。
2.通过一定的算法的来实现人机对弈。
基
本
求
1.window环境下，可选择VisualC++、VB、Delphi或Java等任一编程语言实现。
2.界面美观，交互性好。
3.熟悉UML建模语言。
4.实现较高的AL。
参
考
资
料
1.刁成嘉主编《UML系统建模与系统分析》北京:
机械工业出版社,2007等相关的UML建模资料
2.人机博弈等相关书籍
周次
1-3周
4-6周
7-12周
13-15周
16-17周
应
完
成
的
阅读UML,人机博弈相关书籍和技术资料，学习编程语言，掌握基本原理和算法。
总结UML建模步骤，建立UML模型，设计出人机博弈算法。
编程实现算法，并通过图形界面实现功能。
调试、完善阶段并撰写毕业答辩论文初稿。
撰写和修改毕
业论文,准备毕业答辩。
指导教师：
王璿
职称：
副教授
2009年2月27日
系级教学单位审批：
年月日
摘要
人工智能是近年来很活跃的研究领域之一。
机器学习和博弈是人工智能研究的重要分支。
国内外对博弈的研究已经较为广泛，特别是IBM的国际象棋程序“深蓝”，已经达到了人类的世界冠军水平。
但是这些程序或者需要经过大量训练，或者采用死记硬背的学习方法，或者是采用大规模搜索算法实现，难以避免“组合爆炸”的危机，因此，一个真正“智能”的，有学习能力的高效率的博弈策略还有待进一步研究。
五子棋是一种深受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。
然而当我们与电脑对战时，您知道电脑是怎样像人脑一样进行思考的吗？
本文设计和实现了一个人机对战的五子棋游戏，对整个程序进行UML建模，以减少程序开发周期。
搜索引擎在基本的极大极小的搜索方法上，进行改进的NegeScout的方法，同时加入历史启发与置换表，这样减少搜索次数、时间，增加搜索效率。
并介绍五子棋程序的数据结构、估值函数、胜负判断方法和整个搜索算法过程。
关键词：
人工智能；
五子棋；
UML，极大极小搜索；
NegeScout；
Abstract
ArtificialIntelligenceisaveryactiveresearchinrecentyears,oneoftheareas.
Artificialintelligence,machinelearningandgameisImportantbranchofresearch.
Gameathomeandabroadhavebeenwidelyinvestigated,especiallyIBM'
sInternationalChessprogram"
DeepBlue"
hasreachedthelevelofthehumanworldchampion.
Buttheseproceduresorneedtogothroughalotoftraining,orlearningbyrote,orbylarge-scalesearchoperatormethodtoachieve,itisdifficulttoavoidthe"
combinatorialexplosion"
ofthecrisis,therefore,atruly"
smart"
thereareschoollearningabilityofhigh-efficiencygamestrategyremainstobestudiedfurther.
GobangGameisapopulargamelovedthegeneralpublic,therulesaresimple,variedandveryfulloffunandrecreational.
However,whenweandthecomputeronthewar,youknowhowthecomputerislikeahumanbrainliketothinkofit?
Thismachineisdesignedandimplementedabattleofthebackgammongame,thewholeprocessUMLmodeling,toreduceprocessdevelopmentcycle.
Searchengineinthebasicmini-maxsearchmethods,waystoimprovetheNegeScout,whileaddinghistoricalinspirationandreplacementtable,sotoreducethenumberofsearches,time,andincreasethesearchefficiency.
AndintroducedtheGo-Mokuprogramdatastructures,thevaluationfunction,determinetheoutcomeoftheprocessmethodsandthesearchalgorithm.
Keywords ArtificialIntelligence;
GobangGame;
UML;
Mini-max;
NegeScout
第1章绪论
1.1课题背景
在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。
在人工智能领域内，博弈是很重要的一个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算机智能更加靠近人类智能。
电脑博弈是人工智能研究的一个方向，到了近50年前，随着电子计算机的诞生，科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战，香农（1950）与图灵（1953）提出了对棋类博弈程序的描述，随着电脑硬件和软件的高速发展，从1980开始，电脑博弈便开始逐渐大规模地向人的智能发起了挑战，到了1997年，IBM超级电脑DeeperBlue击败了当时国际象棋世界冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要旅程碑。
五子棋相传起源于四千多年前的尧帝时期，比围棋的历史还要悠久，可能早在“尧造围棋”之前，民间就已有五子棋游戏。
有关早期五子棋的文史资料与围棋有相似之处，因为古代五子棋的棋具与围棋是完全相同的。
在上古的神话传说中有“女娲造人，伏羲做棋”一说，《增山海经》中记载：
“休舆之山有石焉，名曰帝台之棋，五色而文状鹑卵。
”李善注引三国魏邯郸淳《艺经》中曰：
“棋局，纵横各十七道，合二百八十九道，白黑棋子，各一百五十枚”。
这段虽没明讲是何种棋类，但至少知道远古就以漂亮的石头为棋子。
因而规则简单的五子棋也可能出自当时，并是用石子作棋子。
亦有传说，五子棋最初流行于少数民族地区，以后渐渐演变成围棋并在炎黄子孙后代中遍及开来。
在古代，五子棋棋具虽然与围棋相类同，但是下法却是完全不同的。
正如《辞海》中所言，五子棋是“棋类游戏，棋具与围棋相同，两人对局，轮流下子，先将五子连成一行者为胜。
”
传统五子棋的棋具与围棋相同，棋子分为黑白两色，棋盘为19X19，棋子放置于棋盘线交叉点上。
两人对局，各执一色，轮流下一子，先将横、竖或斜线的5个或5个以上同色棋子连成不间断的一排者为胜。
因为传统五子棋在落子后不能移动或拿掉，所以也可以用纸和笔来进行游戏。
五子棋游戏在国际上也十分流行。
例如，韩国人把五子棋称为“情侣棋”，暗示情人之间下五子棋有利于增加情感的交流；
欧洲人称其为“绅士棋”，代表下五子棋的君子风度胜似绅士；
日本人则称其为“中老年棋”，说明五子棋适合中老年人的生理特点和思维方式；
美国人喜欢将五子棋称为“商业棋”，也就是说，商人谈生意时可边下棋边谈生意，棋下完了生意也谈成了。
1.2课题来源与研究意义
1.2.1课题来源
“人工智能”（ArtificialIntelligence，简称AI）一词最初是在1956年Dartmouth学会上提出的。
从那以后,研究者们发展了众多理论和原理,人工智能的概念也随之扩展。
人工智能的定义可以分为两部分，即“人工”和“智能”。
“人工”比较好理解，争议性也不大。
有时我们会要考虑什么是人力所能及制造的，或者人自身的智能程度有没有高到可以创造人工智能的地步，等等。
但总的来说，“人工系统”就是通常意义下的人工系统。
关于什么是“智能”，就问题多多了。
这涉及到其它诸如意识（consciousness）、自我（self）、思维（mind）（包括无意识的思维（unconscious_mind）等等问题。
人唯一了解的智能是人本身的智能，这是普遍认同的观点。
但是我们对我们自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”了。
因此人工智能的研究往往涉及对人的智能本身的研究。
其它关于动物或其它人造系统的智能也普遍被认为是人工智能相关的研究课题。
人工智能目前在计算机领域内，得到了愈加广泛的重视。
并在机器人，经济政治决策，控制系统，仿真系统中得到应用。
著名的美国斯坦福大学人工智能研究中心尼尔逊教授对人工智能下了这样一个定义：
“人工智能是关于知识的学科――怎样表示知识以及怎样获得知识并使用知识的科学。
”而另一个美国麻省理工学院的温斯顿教授认为：
“人工智能就是研究如何使计算机去做过去只有人才能做的智能工作。
”这些说法反映了人工智能学科的基本思想和基本内容。
即人工智能是研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人的智力才能胜任的工作，也就是研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论、方法和技术。
人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。
也被认为是二十一世纪（基因工程、纳米科学、人工智能）三大尖端技术之一。
这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。
人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。
人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。
可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。
从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。
[1]
计算机博弈是人工智能的一个研究内容，它包括跳棋、象棋、五子棋等竞争性的智能活动。
五子棋的根在中国，有着广泛的群众基础。
但与世界先进的五子棋技术相比，我们的棋艺水平还很低，所以我们要推广五子棋，宣传五子棋，争取在较短的时间内赶上和超过世界五子棋坛的先进水平。
随着中国五子棋网上比赛的开通，将世界连珠五子棋运动的最新状况及时展现在眼前，为五子棋爱好者提供了尽情参与的机会，这无疑对国内的普及、发展起到了推动的作用。
1.2.2课题研究意义
智能机器是机器系统发展的崭新阶段，具有深远的社会影响。
如果说以蒸汽机为动力的工具机的发展，使人类摆脱了繁重的体力劳动，导致了第一次产业革命，那么以计算机为先导的智能机器的发展，则会使人类摆脱繁杂的脑力劳动，开创一次新的产业革命。
这样，人类将进入信息化社会，知识和智力将成为生产和经济发展的决定性因素。
如果说电力技术终将成为消除城乡对立的最强有力的杠杆；
智力技术则终将成为消除脑力劳动与体力劳动之间差别的最强有力的杠杆。
人工智能研究博弈的目的并不是为了让计算机与人进行游戏，而是通过对博弈的研究来检验某些人工智能技术是否能达到对人类智能的模拟，因为博弈是一种智能性很强的竞争活动。
另外，通过对博弈过程的模拟可以促进人工智能技术深入一步的研究。
本次设计选择以五子棋的游戏开发为课题的根本目的是通过实现五子棋游戏，促进对人工智能知识和技术进一步的学习和研究。
1.3论文结构
本论文一共分为6章，内容包括：
绪论、开发工具的介绍、系统分析、总设计、系统详细设计与实现、系统测试等。
第一章为绪论。
介绍了课题的背景与所选课题的意义。
第二章为开发工具的介绍和系统配置。
介绍了本系统所采用的一些主流技术和语言，包括：
C++技术的概述和它的一些优势，visualc++开发工具的概述和特点，还有本系统的配置问题。
第三章为系统分析。
分别描述了本系统需求和可行性研究以及功能分析等方面的问题。
第四章为系统UML建模。
对该系统的数据结构、下棋过程、以及整体的活动进行建模
第五章为总体设计。
详细介绍棋盘的表示、以及走访产生、搜索引擎的介绍，估值核心以及胜负判断等。
第六章为系统的实现。
介绍了系统的测试以及系统运行的结果。
第2章开发工具的介绍和系统配置
2.1系统环境配置
系统环境：
windowsXPSP3
开发语言：
C++
开发工具：
VisualC++6.0
2.2开发环境C++技术
2.2.1概述
C++这个词在中国大陆的程序员圈子中通常被读做“C加加”，而西方的程序员通常读做“Cplusplus”，“CPP”。
它是一种使用非常广泛的计算机编程语言。
C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。
它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。
2.2.2C++的优势
我觉得C++最大的优势在于她的通用和全面。
我们往往听到C++和其他语言的比较：
诸如运行效率不如C啦、应用软件的开发效率上不如Java和.NET啦、GUI开发不如VB啦……以及在各个方面与各种专用语言和脚本语言的比较。
似乎C++就没有自己最突出的地方，简直一无是处。
我想说的是，先不谈比较的结果，这些比较能够成立，本身就说明了C++的优势——她是通用的，她是全面的。
在成熟的主流语言中，除了C++，还有谁能够做到这一点？
另外一些比较则罕有提及：
与C语言比开发应用软件？
与Java比做底层？
与VB比运行效率？
是的，很罕见。
因为结论显而易见以至任何的比较都是浪费时间。
当然了，她们都有各自的适用范围，做好本职就好了，何必与你比其他的。
这是一种生存之道，无可厚非。
唯有C++，选择了另一条道路——“通用语言”，不是象C那样“通用的”底层语言，也不是象Java那样其实只能在一个平台上运行的“跨平台”语言，而是真正的通用：
通用于所有层次、通用于所有平台、通用于所有领域，对所有的应用都不偏不倚、一视同仁。
要做到这一点是很困难的，C++往往被人指责野心过大。
还有各种各样的误解：
有指责VC只能在Windows上使用的（所以C++是不能跨平台的）；
有指责gcc无法快速开发GUI的（所以C++的应用是有局限的）；
有指责Java、.NET和脚本语言占据了绝大部分网站开发的（所以C++是不能适应网络时代的）……这些指责说得人多了，就成为了真理。
我不想去一一解疑，只想说明一点：
语言之间的比较很少是公正的，因为误解是广泛存在的。
无疑，C++的野心确实很大，“通用”二字貌似华丽有余，实惠不足。
常常有人说：
学习C++，然后使用其他专门语言。
是的，在一个特定领域里，通用往往比不上专用的。
但是，整体总是大于部分之和。
如果说，“博”和“精”各有所长的话，那么又博且精不是更好吗？
就象我们常常用电脑，而不是分立的上网机、办公机、游戏机、编程机
……虽然C++不能包揽所有的冠军，但是如果她在哪方面都不算太差的话，又何必执着于虚幻的完美呢？
确实，C++能够立足于世，不仅在于她是“通用”的，更在于她是“全面”的。
你常常能在某个局部找到她的一点不足。
是的，她有一个不足；
那么，能否改进呢？
回答是：
不能！
为什么？
如果改进了这一点，就会出现新的不足，可能是另一点，甚或更多。
就象一个已经挤满了人的车厢，要上去一个，就得再下来一个！
是的，C++就是这样的车厢，她无法让你享受悠闲的空间，反而给你窒息的感觉；
但是，正是这样的车厢，支撑着主干交通的正常运行（想想吧，如果一个人口密集的大城市里全部都是私家车，会是什么状况）。
车厢可能会越做越大，因为技术正在不断提高，但是C++这个车厢，永远都是满的。
一个局部的不足，如果不存在被改进的可能，恰恰暗示了已经达到了全局最佳！
C++正是以此为目标的；
并且，她做到了！
回到最初比较上。
C++的运行效率不如C吗？
是的，也许吧，以特定的标准。
但是，不如在哪些方面呢？
虚函数、虚基类、异常处理……这些都是C所不具备的。
如果在C++中不使用它们，那么效率就不会比C低（优秀的编译器确实可以做到这一点）！
C++考虑问题永远是综合的，而非单方面的，她的效率，趋近于你在享用各种特性时所能达到的最佳值，你只付出必然的代价。
C++在应用软件的开发效率上不如Java和.NET吗？
但是，原因是什么呢？
是C++语言不及Java和.NET吗？
不是的。
只是因为后两者是产品，而C++是语言。
这个比较，本身就是不合适的。
在.NET中，你同样可以使用C++，同样可以达到它的开发效率。
另外，C++并不限制其实现产品，所以每个特定应用领域都可以有其特定的编译器，它们帮助程序员达到各自最佳的开发效率。
如果单论语言，那么只有C++的语言复杂度会影响这一话题。
也许Java等更容易上手，但是对两方面的资深人员来说，C++的开发效率毫不逊色。
值得一提的是，在比较时应该同时考虑应用的复杂度。
另外，需要知道，作为产品的Java和.NET预处理了一些应用复杂度，而这些产品本身很大程度上（如果不说全部的话）是用C++开发的。
C++在GUI开发方面不如VB吗？
但是，为什么呢？
作为语言，C++没有制订标准的GUI库，因为GUI太复杂，要达到通用的最佳，很难。
因此，C++放弃了这方面的通用化。
但是，每个具体的实现可以使用各自优化的GUI库。
VC比VB如何？
如果嫌它还不算快速开发，BCB呢？
另外，还有QT等通用GUI库。
在语言方面，C++追求通用和全面，而局部的优化，交给具体的实现来完成，这是C++成功的秘诀。
综上所述，我认为C++的优势就在于她的通用和全面（也有人认为这正是她的劣势，也许吧，从另一个角度）。
她的通用，来源于其始终不变的远大理想（也可称之为“野心”）；
而她的全面，则得益于她的设计者们力争上游、精益求精的工作态度！
就象我曾经说过的，C++真正的优势在于C++社群——那些设计她的人，实现她的人，以及使用她的人。
那些表面的优势来源于此，也归结于此。
2.3开发工具VisualC++6.0
2.3.1VisualC++6.0概述
VisualC++是一个功能强大的可视化软件开发工具。
自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++已成为专业程序员进行软件开发的首选工具。
虽然微软公司推出了VisualC++.NET（VisualC++7.0），但它的应用的很大的局限性，只适用于Windows2000,WindowsXP和WindowsNT4.0。
所以实际中，更多的是以VisualC++6.0为平台。
VisualC++6.0不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrateddevelopmentenvironment,IDE）。
VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。
这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。
2.3.2VisualC++6.0优势
VisualC++不仅仅是一个编译器。
它是一个全面的应用程序开发环境，使用它你充分利用具有面向对象特性的C++来开发出专业级的
Windows
应用程序。
VisualC++作为一种程序设计语言，它同时也是一个集成开发工具，提供了软件代码自动生成和可视化的资源编辑功能。
在使用VisuaC++开发应用程序的过程中，系统为我们生成了大量的各种类型的文件。
VisualC++采用的框架是MFC。
MFC不仅仅是人们通常理解的一个类库。
你如果选择了MFC，也就选择了一种程序结构，一种编程风格。
MFC是一个很大的、扩展了的C++类层次结构，它能使开发Windows
应用程序变得更加容易。
MFC是在整个Windows家族中都是兼容的，也就是说，无论是
Windows3.x、Windows95还是WindowsNT，所使用的
MFC是兼容的。
每当新的Windows版本出现时,MFC也会得到修改以便使旧的编译器和代码能在新的系统中工作。
MFC也回得到扩展，添加新的特性、变得更加容易建立应用程序。
使用MFC的最大优点是它为你做了所有最难做的事。
MFC
中包含了上成千上万行正确、优化和功能强大的Windows代码。
你所调用的很多成员函数完成了你自己可能很难完成的工作。
从这点上将，MFC
极大地加快了你的程序开发速度。
由于MFC编程方法充分利用了面向对象技术的优点，它使得我们编程时极少需要关心对象方法的实现细节，同时类库中的各种对象的强大功能足以完成我们程序中的绝大部分所需功能，这使得应用程序中程序员所需要编写的代码大为减少，有力地保证了程序的良好的可调试性。
最后要指出的是MFC类库在提供的对象的各种属性和方法都是经过谨慎的编写和严格的测试，可靠性很高，这就保证了使用MFC类库不会影响程序的可靠性和正确性。
2.4本章小结
本章对C++有了一个总体介绍，对C++的相关优势也做了简单介绍，同时简单阐述了VisualC++的相关信息和技术优势.。
第3章系统分析
3.1系统需求
五子棋作为一款休闲益智游戏，它最大的优点在于游戏规则家喻户
升级会员 