毕业设计：基于UML的五子棋人机对弈设计.doc

本科毕业设计（论文）基于UML的五子棋人机对弈专 业：计算机科学与技术学生 姓名：简越 学 号：060104010084 指导 教师：王璿 答辩 日期：2010-6-9 IIIIII燕山大学本科毕业设计（论文）摘 要人工智能是近年来很活跃的研究领域之一。机器学习和博弈是人工智能研究的重要分支。国内外对博弈的研究已经较为广泛，特别是 IBM 的国际象棋程序“深蓝”，已经达到了人类的世界冠军水平。但是这些程序或者需要经过大量训练，或者采用死记硬背的学习方法，或者是采用大规模搜索算法实现，难以避免“组合爆炸”的危机，因此，一个真正“智能”的，有学习能力的高效率的博弈策略还有待进一步研究。五子棋是一种深受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。然而当我们与电脑对战时，您知道电脑是怎样像人脑一样进行思考的吗？本文设计和实现了一个人机对战的五子棋游戏，对整个程序进行UML建模，以减少程序开发周期。搜索引擎在基本的极大极小的搜索方法上，进行改进的NegeScout的方法，同时加入历史启发与置换表，这样减少搜索次数、时间，增加搜索效率。并介绍五子棋程序的数据结构、估值函数、胜负判断方法和整个搜索算法过程。关键词： 人工智能；五子棋；UML，极大极小搜索；NegeScout；燕山大学本科生毕业设计（论文）AbstractArtificial Intelligence is 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.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 remains 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 implemented 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 increase 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 课题来源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章 系统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附录2VI附录3：XI附录4：XV附录5：XXVIII9第1章 绪论第1章 绪论1.1 课题背景在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。在人工智能领域内，博弈是很重要的一个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算机智能更加靠近人类智能。电脑博弈是人工智能研究的一个方向，到了近50年前，随着电子计算机的诞生，科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战，香农(1950)与图灵(1953)提出了对棋类博弈程序的描述，随着电脑硬件和软件的高速发展，从1980开始，电脑博弈便开始逐渐大规模地向人的智能发起了挑战，到了1997年，IBM超级电脑Deeper Blue击败了当时国际象棋世界冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要旅程碑。五子棋相传起源于四千多年前的尧帝时期，比围棋的历史还要悠久，可能早在“尧造围棋”之前，民间就已有五子棋游戏。有关早期五子棋的文史资料与围棋有相似之处，因为古代五子棋的棋具与围棋是完全相同的。在上古的神话传说中有“女娲造人，伏羲做棋”一说，增山海经中记载：“休舆之山有石焉，名曰帝台之棋，五色而文状鹑卵。”李善注引三国魏邯郸淳艺经中曰：“棋局，纵横各十七道，合二百八十九道，白黑棋子，各一百五十枚”。这段虽没明讲是何种棋类，但至少知道远古就以漂亮的石头为棋子。因而规则简单的五子棋也可能出自当时，并是用石子作棋子。亦有传说，五子棋最初流行于少数民族地区，以后渐渐演变成围棋并在炎黄子孙后代中遍及开来。在古代，五子棋棋具虽然与围棋相类同，但是下法却是完全不同的。正如辞海中所言，五子棋是“棋类游戏，棋具与围棋相同，两人对局，轮流下子，先将五子连成一行者为胜。”传统五子棋的棋具与围棋相同，棋子分为黑白两色，棋盘为19X19，棋子放置于棋盘线交叉点上。两人对局，各执一色，轮流下一子，先将横、竖或斜线的5个或5个以上同色棋子连成不间断的一排者为胜。因为传统五子棋在落子后不能移动或拿掉，所以也可以用纸和笔来进行游戏。五子棋游戏在国际上也十分流行。例如，韩国人把五子棋称为“情侣棋”，暗示情人之间下五子棋有利于增加情感的交流；欧洲人称其为“绅士棋”，代表下五子棋的君子风度胜似绅士；日本人则称其为“中老年棋”，说明五子棋适合中老年人的生理特点和思维方式；美国人喜欢将五子棋称为“商业棋”，也就是说，商人谈生意时可边下棋边谈生意，棋下完了生意也谈成了。1.2 课题来源与研究意义1.2.1 课题来源“人工智能”(Artificial Intelligence，简称AI)一词最初是在1956 年Dartmouth学会上提出的。从那以后,研究者们发展了众多理论和原理,人工智能的概念也随之扩展。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或者人自身的智能程度有没有高到可以创造人工智能的地步，等等。但总的来说，“人工系统”就是通常意义下的人工系统。关于什么是“智能”，就问题多多了。这涉及到其它诸如意识（consciousness）、自我（self）、思维（mind）（包括无意识的思维（unconscious_mind）等等问题。人唯一了解的智能是人本身的智能，这是普遍认同的观点。但是我们对我们自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”了。因此人工智能的研究往往涉及对人的智能本身的研究。其它关于动物或其它人造系统的智能也普遍被认为是人工智能相关的研究课题。人工智能目前在计算机领域内，得到了愈加广泛的重视。并在机器人，经济政治决策，控制系统，仿真系统中得到应用。著名的美国斯坦福大学人工智能研究中心尼尔逊教授对人工智能下了这样一个定义：“人工智能是关于知识的学科怎样表示知识以及怎样获得知识并使用知识的科学。”而另一个美国麻省理工学院的温斯顿教授认为：“人工智能就是研究如何使计算机去做过去只有人才能做的智能工作。”这些说法反映了人工智能学科的基本思想和基本内容。即人工智能是研究人类智能活动的规律，构造具有一定智能的人工系统，研究如何让计算机去完成以往需要人的智力才能胜任的工作，也就是研究如何应用计算机的软硬件来模拟人类某些智能行为的基本理论、方法和技术。人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪（基因工程、纳米科学、人工智能）三大尖端技术之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。1计算机博弈是人工智能的一个研究内容，它包括跳棋、象棋、五子棋等竞争性的智能活动。五子棋的根在中国，有着广泛的群众基础。但与世界先进的五子棋技术相比，我们的棋艺水平还很低，所以我们要推广五子棋，宣传五子棋，争取在较短的时间内赶上和超过世界五子棋坛的先进水平。随着中国五子棋网上比赛的开通，将世界连珠五子棋运动的最新状况及时展现在眼前，为五子棋爱好者提供了尽情参与的机会，这无疑对国内的普及、发展起到了推动的作用。1.2.2 课题研究意义智能机器是机器系统发展的崭新阶段，具有深远的社会影响。如果说以蒸汽机为动力的工具机的发展，使人类摆脱了繁重的体力劳动，导致了第一次产业革命，那么以计算机为先导的智能机器的发展，则会使人类摆脱繁杂的脑力劳动，开创一次新的产业革命。这样，人类将进入信息化社会，知识和智力将成为生产和经济发展的决定性因素。如果说电力技术终将成为消除城乡对立的最强有力的杠杆；智力技术则终将成为消除脑力劳动与体力劳动之间差别的最强有力的杠杆。人工智能研究博弈的目的并不是为了让计算机与人进行游戏，而是通过对博弈的研究来检验某些人工智能技术是否能达到对人类智能的模拟，因为博弈是一种智能性很强的竞争活动。另外，通过对博弈过程的模拟可以促进人工智能技术深入一步的研究。本次设计选择以五子棋的游戏开发为课题的根本目的是通过实现五子棋游戏，促进对人工智能知识和技术进一步的学习和研究。1.3 论文结构本论文一共分为6章，内容包括：绪论、开发工具的介绍、系统分析、总设计、系统详细设计与实现、系统测试等。第一章为绪论。介绍了课题的背景与所选课题的意义。第二章为开发工具的介绍和系统配置。介绍了本系统所采用的一些主流技术和语言，包括：C+技术的概述和它的一些优势，visualc+开发工具的概述和特点，还有本系统的配置问题。第三章为系统分析。分别描述了本系统需求和可行性研究以及功能分析等方面的问题。第四章为系统UML建模。对该系统的数据结构、下棋过程、以及整体的活动进行建模第五章为总体设计。详细介绍棋盘的表示、以及走访产生、搜索引擎的介绍，估值核心以及胜负判断等。第六章为系统的实现。介绍了系统的测试以及系统运行的结果。第2章 开发工具的介绍和系统配置第2章 开发工具的介绍和系统配置2.1 系统环境配置系统环境：windows XP SP3开发语言：C+开发工具：Visual C+ 6.02.2 开发环境C+技术2.2.1概述C+这个词在中国大陆的程序员圈子中通常被读做“C加加”，而西方的程序员通常读做“C plus plus”，“CPP”。 它是一种使用非常广泛的计算机编程语言。C+是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。2.2.2 C+的优势我觉得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 开发工具Visual C+6.02.3.1 Visual C+ 6.0概述Visual C+是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+6.0不仅是一个C+编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrateddevelopment environment,IDE）。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。 2.3.2 Visual C+ 6.0优势Visual C+不仅仅是一个编译器。它是一个全面的应用程序开发环境，使用它你充分利用具有面向对象特性的C+来开发出专业级的Windows应用程序。VisualC+作为一种程序设计语言，它同时也是一个集成开发工具，提供了软件代码自动生成和可视化的资源编辑功能。在使用VisuaC+开发应用程序的过程中，系统为我们生成了大量的各种类型的文件。Visual C+采用的框架是MFC。MFC不仅仅是人们通常理解的一个类库。你如果选择了MFC，也就选择了一种程序结构，一种编程风格。MFC是一个很大的、扩展了的C+类层次结构，它能使开发Windows应用程序变得更加容易。MFC是在整个Windows家族中都是兼容的，也就是说，无论是Windows3.x、Windows95还是Windows NT，所使用的MFC是兼容的。每当新的Windows版本出现时,MFC也会得到修改以便使旧的编译器和代码能在新的系统中工作。MFC也回得到扩展，添加新的特性、变得更加容易建立应用程序。使用MFC的最大优点是它为你做了所有最难做的事。MFC中包含了上成千上万行正确、优化和功能强大的Windows代码。你所调用的很多成员函数完成了你自己可能很难完成的工作。从这点上将，MFC极大地加快了你的程序开发速度。由于MFC编程方法充分利用了面向对象技术的优点，它使得我们编程时极少需要关心对象方法的实现细节，同时类库中的各种对象的强大功能足以完成我们程序中的绝大部分所需功能，这使得应用程序中程序员所需要编写的代码大为减少，有力地保证了程序的良好的可调试性。最后要指出的是MFC类库在提供的对象的各种属性和方法都是经过谨慎的编写和严格的测试，可靠性很高，这就保证了使用MFC类库不会影响程序的可靠性和正确性。2.4 本章小结本章对C+有了一个总体介绍，对C+的相关优势也做了简单介绍，同时简单阐述了Visual C+的相关信息和技术优势.。第3章 系统分析第3章 系统分析3.1 系统需求五子棋作为一款休闲益智游戏，它最大的优点在于游戏规则家喻户晓，简单，上手快，趣味性强，所以受广大用户青睐，在各大提供棋牌类游戏的平台都可以看到玩五子棋游戏的人很多。休闲益智游戏中等级并不是最重要的追求目标，通过对游戏规则的熟悉，能很快上手掌握其操作方式，也更适合男女老幼全家共同娱乐，花费时间简短，速战速决，在短时间内感受到游戏的乐趣，完全享受气氛轻松活跃的游戏过程。此种娱乐方式既不耽误时间也能轻松调剂娱乐，充分适合现代人们的娱乐需求。更主要的是开发了人的智力，成为年轻一代最流行的游戏，据统计，五子棋游戏的玩家中，学生占了接近三分之一的比例，对学生的智力健康成长起一定作用，正所谓休闲娱乐两不误。3.2 系统的可行性研究可行性研究的目的，不是解决问题，而是确定问题是否值得去解决，就是要用最小的代价在尽可能短的时间内确定问题是否能够解决。这里所说的相对短和相对低是指和实现建议系统所需要时间和成本相比较而言。要在较高层次上以较抽象的方式进行的系统分析和设计的过程。一般说来，至少应该从三个方面研究每种方法的可行性：技术可行性、经济可行性、操作可行性。3.2.1 技术可行性技术可行性主要是对当前的软、硬件技术能否满足系统地实现要求进行分析。目前大多数企业的计算机多为个人计算机系统（PC机），而个人计算机又普遍采用Microsoft微软的Windows作为操作系统，Windows XP以其简单易用，灵活可靠、出色的多媒体应用赢得了用户广泛好评。利用微软公司提供的Visual C+ 6.0，其中提供很多工具与包以及MFC模型，这样对本项目的开发提供了极大的便利。2.2.2 经济可行性经济可行性主要是对开发系统进行费用支出的预估和对项目的经济效益进行评价。本系统开发费用低，其次本系统的维护费用极低。该项目的实施在经济上主要费用有： (1) 设备购置费用：包括计算机、打印机等计算机系统及外围相关设备的购置费用。 (2) 软件费：本系统的研发费用，相关操作平台软件费 系统实施所需的计算机设备可以利用燕山大学学生机房提供的计算机设备或者自带电脑，设备均采用Windows XP系统，打印设备可以利用校园内相关打印业提供，软件为本人免费研发，提供给用户免费使用。因此，从经济可行性上来分析，本系统开发时间较短，实用性强，应用广泛，可移植性强，发展前景广阔，经济性良好。2.2.3运行可行性运行可行性主要指房地产高层管理人员对开发应用项目的态度和管理方面的条件。本软件能大大丰富用户的业余生活，通过和电脑对抗，提高自身五子棋。2.2.4法律可行性法律可行性主要指该系统的开发会不会在社会上或政治上引起侵权、破坏或其他责任问题。系统由本人开发，所有权归本人所属，未使用任何非法软件进行相关开发，因此开发该系统是可行的。根据以上几点的可行性分析，本系统的开发是切实可行的！3.3 功能分析3.3.1 系统的功能需求这方面的需求指定系统必须提供的服务。通过需求分析应该划分出系统必须完成的所有功能，用结构化分析方法建立数据模型、功能模型、行为模型。本系统提供了人先手，电脑先手两方面选项，同时提供了菜鸟级，专家级以及不可战胜三个级别。为了体现每种级别的不一样，特别设立一个思考进度条。3.3.2 系统的业务流程图整个游戏基本流程图：图3-1 游戏流程图本软件使用起来非常简单，只用打开软件，先选择先后手，在选择难度，就可以进行游戏了。如果不选择的话，默认是专家级，先手下棋。3.4 本章小结本章对人机博弈的五子棋的设计和实现过程做了可行性分析和需求分析。从问题定义出发论述该系统预计实现的功能，根据其功能和实际的功能进行了简单的规划，力图简单、方便、易懂的操作方式，进一步降低使用软件的难度，使游戏更加容易上手，并为该系统的总体设计奠定了理论基础。43第4章 系统UML建模第4章 系统UML建模本软件采用现代软件的基本开发模式，即采用面向对象UML建模。4.1 数据结构五子棋人机博弈程序的类图如图4-1所示。图4-1类图类的定义以下：走法产生器：CmoveGenerator搜索引擎的基类：CsearchEngine。定义接口以及公用函数历史启发类：ChistoryHeuristic。用来给搜索算法调整节点顺序，提高搜索效率置换表类：CtranspositionTable。用来记忆评估过的点的价值，增强搜索效率搜索引擎：CnegaScout_TT_HH。使用的是NegaScout算法，并加上了历史启发与置换表。是由CserchEngine、ChistoryHeuristic和CTranspositionTable派生出来的估值核心：Ceveluation。棋盘：CWzqDlg。4.2下棋过程4.2.1人下棋时序图图4-2人下棋时序图时序图说明；1. OnLButtunDown()记录棋盘落子点2. IsValidPox()用于建立新棋子3. AnalysisLine()检查此类棋子是否能和周围类型的棋子合并4.2.2电脑下棋时序图图4-3电脑下棋时序图时序图说明：1. SetMoveGenerator()调用走法2. AddMove()用于向数组中添加走法3. CreatePossibleMove()用于给定局面的下一步所有的合法的步骤4. return（）返回走法5. SearchAGoodMove()调用算法6. Eveluate()调用估值7. return()返回估值8. MakeMove()传入走法来改变棋盘9. OnLButtonDown()棋盘落子10. IsValidPox()用于建立新棋子11. AnalysisLine()检查此类棋子是否能和周围类型的棋子合并4.3人机博弈活动图根据上面分析得出人机博弈整体活动图如图4-4所示。图4-4软件整体活动图游戏分为两种方式，一种是人走棋，另外一种是电脑走棋。如果人走棋，则在棋盘上选择下棋点，随后落子然后判断胜负，如果人获胜则结束游戏，如果没获胜调用电脑下棋。当电脑下棋的时候，先寻找潜在下棋点，如果存在则随着模拟这个下棋点，进行子节点扩展，调用算法，评价出改节点，一直到没有潜在下棋点，选择最大值的节点走出最佳步骤。4.4本章总结面向对象程序设计具有直观性、逻辑性强的特点，非常适合人机博弈程序的分析和设计。而UML建模语言是面向对象程序设计主要分析和设计语言。能使程序不仅在逻辑上结构清晰，而且具有更强的可扩展性和维护性。本章对本软件进行了详细的UML建模，描述出本软件的类图，时序图以及整体的活动图。燕山大学本科毕业设计（论文）第5章 总体设计5.1 棋盘表示本系统基于图5-1所示的数据表示棋盘：1. 盘数据由一个15*15的二维数组表示。2. 用数字“0”和“1”来表示不同的棋子。3. 没有棋子的格子用0xFF表示。上述内容仅仅是在实现各个模块时要遵循的数据表示，为了在使用的时能够避免数据表示差错，我将棋子的定义成一系列的宏定义，便以使用图5-1五子棋棋盘宏定义放在头文件（define.h）中5.2 走法产生器任何一种人机博弈棋类游戏都会涉及走法产生，顾名思义，走法产生就是决定怎么走才是合法的步骤。五子棋的走法产生比较容易，对于五子棋来说，棋盘上的所有空白的位置都是合法的落子点。走法产生类文件在（MoveGenerator.h），实现文件在MoveGenerator.cpp中。5.3 搜索引擎对于本系统，最重要的就是在此部分，搜索引擎，这是决定电脑的“智力”是否高的一个重要标准。本游戏的搜索引擎主要采用NegeScout算法与历史启发以及置换表三部分组成。5.3.1 NegeScout算法在介绍NegeScout算法之前，首先介绍博弈树以及极大极小算法 博弈树博弈树是指在博弈过程中，任何一方都希望自己取得胜利。因此，在某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在A方的立场上，则可供 A选择的若干行动方案之间是“或”关系，因为主动权操在 A方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由 A方决定，考虑到对 A方有利总是要选取最大值，所以 A方搜索极大值。但是，若B方也有若干个可供选择的行动方案，则对 A方来说这些行动方案之间是“与”的关系，因为这时主动权操在 B方手里，这些可供选择的任何一个行动方案都肯能被 B方选中，B方一定会选择对 A方最不利的方案，因此，B方总是要选择使 A方得分最小的路线走，称极小值搜索。A方就必须考虑到对自己最不利的情况的发生。若把上述博弈过程用图表示出来，得到的是一棵“与/或树”。这里特别指出，该“与/或树”是始终站在某一方（例如 A方）的立场上得出来的，决不可一会儿站在这一方的立场上，一会儿站在另一方的立场上。称描述博弈过程的与/或树为博弈树，它有如下特点：（1）博弈的初始格局是初始结点。 （2）在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流地扩展节点。（3）所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点6。 极大极小值分析法在二人博弈问题中，最常用的方法是极大极小值分析法。图5-2给出用极大极小值分析法计算博弈树倒推值的实例：图5-2 d=4的博弈树的极大极小搜索过程7在前文的博弈树中，如果令假胜的局面值为1，乙胜的局面值为-1，而和局的值为0。当轮到甲走时，甲定会选择子节点值最大的走法；而轮到乙时，乙则会选择子节点值最小走法。所以对于中间节点的值可以有如下计算方法；如果该节点所对应的局面轮到甲走棋，则该节点的值时其所有子节点中值最大的一个值，反之轮乙走棋，则该节点的值时所有子节点中值最小的一个值。我们可以这样想，如果有一种函数能够可以为每一局面的忧劣评分。例如甲胜为+；乙胜为；和局为0；其他的情形依据双方剩余棋子的数量及位置评定一个具体的分数。这样我们可以建立一棵固定深度的搜索树，其叶子节点不必是终了状态，而只是固定深度的最深一层的节点，其值由上述函数评出；对于中间节点，如同前面提到的那样，甲方取子节点的最大值，乙方取子节点的最小值。这个评分的函数称静态估值函数。用以取代超出固定深度的搜索。估值函数给出的只是一个较粗略的评分，在此基础上进行的少量搜索的可靠性，理论上是不如前述的WIN,LOST,DRAW三种状态的博弈树的，但这个方法却是可实现的。而极大极小方法往往是指基于静态估值函数的有限深度的极大极小搜索8。 剪枝算法在极大极小搜索的过程中，存在着一定程度的数据冗余而剪枝算法可以解决极大极小值分析过程中存在一定的不足，首先看下面两幅图：图5-3 alpha-beta剪枝假如，对于上图左边部分所示的数的片段，根据所示的节点的值，B为18，D为16。因此我们可以断定出C的值一定小于16，而A的值是MAX(B,C)为18，这样的话不用估值C点以后的节点了就能算出A的值。这样的节点D的后继节点减去的方法叫alpha剪枝。反之对于图4-3右半部分，这种剪枝叫做beta剪枝。将alpha与beta剪枝加入MINIMAX搜索，这就是著名alpha-beta搜索算法。这里给出alpha-beta伪代码：/伪代码，alpha-beta算法。int AlphaBeta(nPly,nAlpha,nBeta) if(game over) return Eveluation;/胜负已分，返回估值 if(nPly = 0) return Eveluation;/叶子节点返回估值 if(Is Min Node) /判断当前节点为何种节点 for (each possible move m) /对于每一种走法m Make move m;/生成新节点 Score = alphabeta(nPly 1 , nAlpha , nBeta)/递归搜索子节点 Unmake move m;/撤销搜索过的节点 if (score = nBeta) return nAlpha;/alpha剪枝，抛弃后继节点return nBeta;/返回最小值Else/取极大值的节点for (each possible move m) /对于每一种走法m Make move m;/生成新节点 Score = alphabeta(nPly 1 , nAlpha , nBeta)/递归搜索子节点 Unmake move m;/撤销搜索过的节点 if (score nAlpha) nAlpha = score;/取最大值 if(nAlpha = nBeta) return nBeta;/beta剪枝，抛弃后继节点return nAlpha;/返回最大值Alpha-beta搜索能够让我们忽略很多节点的搜索，这样可以大大提高搜索效率。这也让对于同一棵树的搜索来说，alpha-beta搜索所花的时间远远少于极大极小算法所花的时间9有前面的介绍我们可以了解，如果节点排列最理想的情形之下，使用Alpha-beta搜索建立的博弈树的节点个数为：W(d+1)/2 + Wd/2 +1其中W是博弈树的分支因子，d是最大搜索深度。这个数字大约是极大极小搜索建立节点数的平方根的2倍左右。我们也将这棵理想的博弈树叫做极小树。在最差的情况之下，alpha-beta搜索建立的博弈树的节点也和极大极小值一样。10 极小窗口搜索（NegaScout算法）极小窗口搜索时alpha-beta的变种。正常情况下，在搜索树的根结点，也就是电脑棋手需要决策的局面，我们可以调用alpha-beta算法来得到根结点的分值，同时也可以得到应该走哪一步棋的结论。这时，调用该函数时，我们应使参数alpha=-1000，beta=1000，这里1000是一个足够大的数。这是因为在根结点时，我们需要把窗口初始化成最大，在搜索过程中，随着信息的获得，这个窗口会渐渐地减小，最后收敛到根结点的最优值上。 于是，我们可以对a-b裁剪作一个改进：我们假定：假如第一步是最佳的移动，其后继则次之，知道另一个节点被证明最佳的。在其中一个中间节点，其第一个分支以完整窗口（a,b）搜索值并产生一个位于该窗口的值V，后继的分支则先用零窗口例如（v,v+1）搜索。然后a-b算法调用判断一下，这个搜索是否能够改善当前的最优值，即局面p某一个子结点的实际最优值是否比alpha大。如果比alpha小，则跳过这个子结点。进一步，当该子结点的返回值大于alpha时，从前面的分析中已经知道，它的实际最优值大于这个值，所以当返回值大于beta时，其实际最优值也超过了beta，这时就应该进行剪枝。这就是NegaScout搜索。下面给出伪代码：/伪代码 NegaScout Function negascout(node, depth, , ) if node is a terminal node or depth = 0 return the heuristic value of node b := (* initial window is (-, -) *) foreach child of node a := -negascout (child, depth - 1, -b, -) if a (* check if null-window failed high*) a := -negascout(child, depth - 1, -, -) (* full re-sear