五子棋毕业论文--人工智能课题.docx

《五子棋毕业论文--人工智能课题.docx》由会员分享，可在线阅读，更多相关《五子棋毕业论文--人工智能课题.docx（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、五子棋毕业论文-人工智能课题本科毕业论文(设计)题目五子棋AI算法和网络通信的研究学生姓名学号系别计算机科学系年级2004专业计算机科学与技术指导老师职称讲师完成日期2020-4-01五子棋AI算法和网络通信的研究摘要：本系统将利用五子棋游戏作为研究对象，通过设计出一个能够实现两种不同对战形式的五子棋游戏。并对所涉及到的相关技术进行初步的讨论，将重点放在人机对奕中AI算法研究方面。游戏中提供两种选择形式：人机对战和人人对战。在人机对战中玩家通过选择不同的AI等级和电脑一决高下。在人人对战中双方能够进行下棋，悔棋但要通过对方的同意。同时还能够实如今线聊天。AI的不同等级是以不同的搜索深度确定的。

2、本系统以深度为2，3，4分别为初级，中级，高级。网络对战中则使用Socket实现点对点通信。关键字：五子棋、博奕AI算法、网络通信ResearchtheAIofRenjuandtheCommunicationSummary:ThissystemwilluseRenjuasresearchobjects,passingtodesignaRenjugamethatcanprovidetwokindsofdissimilaritiestotheplaymode.toinvolvetooftherelatedtechniquecarryonthestudyofthefirststep,playmore

3、attentionintheAIcalculatewayresearchaspect.Itprovidetwokindsofchoicemodesinthegame:Personsmachinetothewarandtheeveryonetowar.TheplayerpassestochoosethedifferentAIgradeandcomputerinpersonsmachinetherightnessthewaradefinitelysuperiority.Bothpartiescancarryonplaychessintheeveryonetherightnessthewar,the

4、regretschessbutwanttopasstheapprovaloftheotherparty.Canalsocarryouton-linechatinthemeantime.AIdifferentgradewithsearchthedepthassurancedifferently.Thissystemtakesdepthas2,3,4isanentry-levelrespectively,mediumclass,highclass.ThenetworkorderscorrespondencetowardsthenusingtheSocketrealizationtoorderint

5、hewarto.Keyword:Renju,AI,networks目录第一章引言(4)1.1问题背景(4)1.2五子棋简介(5)第二章具体设计经过(5)2.1概要介绍(5)2.1.1本程序介绍(5)2.1.2本程序优点(5)2.2用软件工程方法学指导开发经过(5)2.2.1问题定义(6)2.2.2可行性研究(7)2.2.3需求分析(8)2.2.4总体设计(9)2.2.5具体设计(10)2.2.6编码和单元测试(10)2.3用户界面(10)2.4系统解析(11)2.4.1界面部分(11)2.4.1.1CFiveChessView的属性(11)2.4.1.2CFiveChessView的函数(12

6、)2.4.2通信部分(14)2.4.3其他部分(15)2.4.3.1CMatch-棋盘类(16)2.4.3.2CMessg消息类(17)2.4.3.3CComputer电脑类(18)2.5人机对战中的AI算法(18)2.5.1极大极小树(19)2.5.2深度优先搜索DFS(19)2.5.3剪枝方法(20)2.5.4静态估值函数(21)2.5.5AI算法的分析和改良(21)2.5.5.1算法分析(22)2.5.5.2算法改良(24)第三章运行测试(25)3.1网络部分(25)3.2人机部分(25)第四章总结部分(27)4.1系统总结(29)4.2缺乏讲明(29)4.3致谢(28)参考文献(29)

7、第一章引言1.1问题背景计算机运算速度一直遵循着摩尔定律在飞速的发展，随着这些技术的快速发展，使得大规模的运算得以在很短的时间内实现。正是基于这些技术，近年来各式各样的棋类游戏软件也纷纷出如今了电脑荧屏上，使得那些喜欢下棋，又经常苦于没有对手的棋迷们能随时过足棋瘾。所以假如能设计一款兼有人工智能和网络联机的五子棋软件则对五子棋棋迷们来讲无疑是个“福音。在人机智能方面其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝便是最具讲服力的代表；其它像围棋的“手淡、象棋的“将族等也以其优秀的人工智能深受棋迷喜欢；本系统将重点放在人工智能方面，采用不同的策略将人工中的智能分为不同的等级。选择五子棋游戏作为本设

8、计的课题，是由于该游戏的规则简单，所涉及的方向比拟少。这样才能将问题的重点放在人工智能解决上，而非规则的解决，有更多的精神放在高效算法和通信经过的优化。希望能通过本次系统的设计，整合所学的知识，实现从理论到实践上的升华。1.2五子棋简介下面就五子棋的背景和规则做一些简单的介绍。五子棋是起源于中国古代的传统黑白棋种之一。当代五子棋日文称之为“连珠，英译为“Renju，英文称之为“Gobang或“FIR(FiveinaRow的缩写)，亦有“连五子、“五子连、“串珠、“五目、“五目碰、“五格等多种称谓。五子棋不仅能加强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有当代休闲的明显特征“短

9、、平、快，又有古典哲学的高深学问“阴阳易理；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场的概念，亦有“点的连接。它是中西文化的沟通点，是古今哲理的结晶。五子棋的规则如下：棋盘：采用同围棋盘一样的15路或19道路的棋盘，为了减小问题的规模，本系统将采用15道路的棋盘。下法：两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的穿插点落子。无子的穿插点又被称为空点。输赢判定：黑、白双方有一方的5个棋子在横、竖或斜方向上连接成一线即为该方赢。第二章具体设计经过2.1概要介绍2.1.1本程序介绍游戏中提供两种选择形

10、式：人机对战和人人对战。在人机对战中玩家通过选择不同的等级和电脑一决高下，能够向懊悔棋。在人人对战中双方通过选择一方作为服务器，通过弹出对话框设置本地应用程序监听端口，而另外一方则作为客户端，通过连接服务器选项，在弹出的对话框中设置要连接的服务器的IP地址和端口号。当双方都提示连接成功后，两方才能够进行下棋。如要悔棋则需要通过对方的同意。同时还能够实如今线聊天。AI的不同等级是以不同的搜索深度确定的。本系统以深度为2，3，4分别为初级，中级，高级。网络对战中则使用Socket实现点对点通信。2.1.2本程序特点五子棋游戏程序由于规则简单操作简便等特点，自然就成为程序员对人工智能研究的首选对象。

11、所以网络上关于这类的程序很多，但是由于主要都是采用搜索穷举技术作为解决方案，这将使得问题的规模变的很庞大如当搜索深度为3时，每走一步电脑在将最坏的情况下需要搜索的点将到达225*225*225=11390625个。即便采用的剪枝技术，其某些点的响应的时间也是让人无法忍耐的，如开局时，由于这个时候每个点都是空的，没有能够剪枝的点，必须遍历真个盘面，所以很耗时间，大约需要30多秒的时间，这个显然是不可接受的。为了程序设计和玩家的忍耐时间的需要。不得不减小深度，所以绝大部分都采用深度为2的检索，很明显深度越低系统的智力也相对的降低，需要代价的。本程序的一个主要特点是，采用了高效的优化方法，使得在一样

12、的搜索规模中所花费的计算时间大幅度的减小。响应时间明显得到提高。即便搜索深度到达4的时候，其响应时间在绝大部分的情况下还是能够接受的。2.2用软件工程方法学指导开发经过在小规模的程序开发中，很多人都不太注意用软件工程的方法学设计系统，包括我本人，在开发一些小功能程序时总是随心所欲的添加需求：有时为了类与类之间的通信需要，往类中添加不相关的变量，直接修改变量的属性或者声明一大堆的全局变量。固然最后系统都能够笨重的运行起来，但这是明显违犯程序设计方法学。可维护行，易修改性严重降低。后期假如需要添加某些功能的时候将变得特别的繁琐。能够想象在多个团队一起开发的大型系统中这种粗陋的开发方法根本是行不通的

13、。所以要养成用正确的方法指导开发经过的习惯，固然有时候看起来有点大题小做，但我觉的这是作为一名合格的软件开发工程师所必须把握的技能。通过长期不断的积累才能增加我们介入大型项目开发的能力。下面对软件工程作下简单的介绍：软件工程一直以来都缺乏一个统一的定义，很多学者、组织机构都分别给出了本人的定义：Boehm：运用当代科学技术知识来设计并构造计算机程序及为开发、运行和维护这些程序所必需的相关文件资料。IEEE：软件工程是开发、运行、维护和修复软件的系统方法。FritzBauer：建立并使用完善的工程化原则，以较经济的手段获得能在实际机器上有效运行的可靠软件的一系列方法。目前比拟认可的一种定义以为：

14、软件工程是研究和应用怎样以系统性的、规范化的、可定量的经过化方法去开发和维护软件，以及怎样把经过时间考验而证实正确的管理技术和当前能够得到的最好的技术方法结合起来。我个人对软件工程理解是，它一种工程上的方法学，用一种有步骤，有计划的正确有效方法指导开发经过。软件工程的精华能够用著名的软件工程专家B.Boehm的七条基本原理来概括。1用分阶段的生存周期计划进行严格的管理。2坚持进行阶段评审。3实行严格的产品控制。4采用当代程序设计技术。5软件工程结果应能清楚地审查。6开发小组的人员应该少而精。7成认不断改良软件工程实践的必要性。目前绝大部分的软件方法都能够从这七条基本推倒出来。B.Boehm指出

15、，遵循前六条基本原理，能够实现软件的工程化生产；根据第七条原理，不仅要积极主动地采纳新的软件技术，而且要注意不断总结经历。下面扼要介绍软件生存周期在本次每个阶段的基本任务2.2.1问题定义问题定义的一个的关键问题是“要解决的问题是什么，这个是这个阶段必需要明确要回答的问题。在没将问题定义好，试图准备下个阶段的任务。这明显是不成熟，甚至不可能的事。本次系统设计中首先明确了需要解决的问题是五子棋AI算法和网络通信的研究，基本的要求是设计一款能够实现网络和单机对战的五子棋游戏，提供一些基本的操作如退出系统，向懊悔棋等操作，重点是放在AI算法和网络通信的研究。而并不是美工设计，也不是为了提供各种操作丰

16、富的接口。主要是通过这种可视化的界面讨论AI，当然增加可玩性和美工会给系统润色不少。上面只是很粗略的明确大概的方向，严格根据软件工程的方法这个阶段需要生产一份书面报告。需要通过对系统的实际用户访问调查，扼要地写出他对问题的理解，并在用户和使用部门负责人的会议上认真讨论这份书面报告，澄清含糊不精的地方，改正理解不正确的地方，最后得出一份双方都满意的文档。本系统的需求很少也很明显了。2.2.2可行性研究这个阶段要回答的关键问题：“对于上一个阶段所确定的问题能否可行？为了回答这个问题，我们需要进行一次大大压缩和简化了的系统分析和设计的经过，也就是在较抽象的高层次上进行的分析和设计的经过。可行性研究应

17、该比拟简短，这个阶段的任务不是详细解决问题，而是研究问题的范围，探索这个问题能否值得去解，能否有可行的解决办法。可行性研究应该比拟简短，这个阶段的任务不是详细解决问题，而是研究问题的范围，探索这个问题能否值得去解，能否有可行的解决办法。可行性研究以后的那些阶段将需要投入要多的人力物力。及时中止不值得投资的工程项目，能够避免更大的浪费。根据这些基本的概念，我在技术上主要是通过相关文档资料的查找后确定可行性，凭着大学期间打下厚实的专业科基础，十分是数据构造和算法，能够在这段时间内理解通透并应该有所改良，后来证实是对的。利用剩下时间也应该来讲也比拟充裕的。经济上暂不考虑。下面主要从技术上进行分析：工

18、具：VC+是一款经久不衰的开发工具，它代表了基于Windows的C+语言产品，完美地集成了传统的编程工具，也集成了Windows中特殊的工具箱，如MFCMicrosoftFoundationClasses和Windows资源编辑器AppStudio。另外还参加了几种新工具，如轮廓应用程序生成器AppWizard、C+类管理器ClassWizard和类阅读器ClassBrowser，以及各种各样为开发MicrosoftWindows下的C/C+程序而设计的工具，MFC类库为我们提供了丰富的类资源。所以VC+是最好的选择。本程序将采用VC的单文档的视图框架，这样能够简化程序的开发。网络通信方面将从

19、MFC封装socket的类CSocket实现点对点通信。算法：在这图论搜索技术这方面，前人已有很成熟的算法。如粗糙的有深度优先算法(DFS)和广度优先算法(BFS)这两个基本的算法，关键需要解决的是能够设计出一种高效的剪枝函数，减小搜索问题的规模。目前博弈类游戏中的人工智能基本都采用极大极小值方法这对我来讲是个挑战，而剪枝的则采用Alpha-Beta，通过丰富的文档资料初步了解到这些技术已经很成熟了。我有自信心能解决好这个问题。Socket：联机对战中的数据传输量很少，利用Socket编程是在好不过了，而且在这方面的把握程度不存在有问题。所以通过对以上关键问题的分析，能够很明确了该系统的可行性

20、。这个阶段的任务告一段落了。能够着手下一个阶段的任务了。软件工程很强调文档驱动开发经过，只要完成了上个阶段的工作后，才能开场下一步骤，这是传统的瀑布开发方法。当然不同的开发模型，经过也会有所区别，大体上都遵循软件工程的这个步骤。这个阶段应该要产生一份（可行性分析报告）。2.2.3需求分析这个阶段的任务仍然不是详细地解决问题，而是准确地确定“为了解决这个问题，目的系统需要做什么，主要是确定目的系统必须具备哪些功能。用户了解他们所面对的问题，知道必须做什么，但是通常不能完好准确地表达出他们的要求，更不知道如何利用计算机解决他们的问题；软件开发人员知道如何使用软件实现人们的要求，但是对特定用户的详细

21、要求并不完全清楚。因而在需求分析阶段必须和用户密切配合，充分沟通信息，以得出经过用户确认的系统逻辑模型。通常用数据流图、数据字典和扼要的算法描绘表示系统的逻辑模型。在设计本系统时考虑到用户需要的是一个操作简便界面简单的游戏软件。同时要提供人机和人人这样的功能。十分是人机部分，要考虑到不同级别的用户。电脑智能不能太低需要有一定的智能下棋功能。本系统用提供平常下棋的一些步骤操作。网络联机：提供向服务器一方发出连接请求的操作，并从弹出的对话框中设置IP和端口号；服务器提供监听的操作同样在弹出的对话框中设置端口号。任何一方需要悔棋请求，则必须通过对方确实定后方可。连接成功后双方能够开场游戏，决定在界面

22、中提供在线聊天功能。用户能够通过主界面的上的菜单操作执行响应的功能和请求，如向对方发处向懊悔棋一步，重新开场，认输等，另一方在接到请求后决定接受或拒绝。人机对战：选择和电脑对弈的等级操作，同样可以以执行网络联机的悔棋等功能，只是由于是人机所以无需通过确认。2.2.4总体设计这个阶段必须回答的关键问题是：“概括地讲，应该怎样解决这个问题？首先，应该考虑几种可能的解决方案。如，目的系统的一些主要功能是用计算机自动完成还是用人工完成；假如使用计算机，那么是使用批处理方式还是人机交互方式；信息存储使用传统的文件系统还是数据库。通常至少应该考虑下述几类可能的方案：低成本的解决方案。系统只能完成最必要的工

23、作，不能多做一点额处的工作。本系统的最基本要求就是能够实现必要的操作，其他额外的一些工作在后面完成中等成本的解决方案。这样的系统不仅能够很好地完成预定的任务，使用起来很方便，而且可能还具有用户没有详细指定的某些功能和特点。固然用户没有提出这些详细要求，但是系统分析员根据本人的知识和经历断定，这些附加的能力在实践中将证实是很有价值的。这个成本方案在完成上面的低成本方案后添加的。如增加保存棋局，美化界面，实现观看电脑与电脑之间的对战等功能。高成本的“十全十美的系统。这样的系统具有用户可能希望有的所有功能和特点。构造设计的一条基本原理就是程序应该模块化，也就是一个大程序应该由很多规模适中的模块按合理

24、的层次构造组织而成。总体设计阶段的第二项主要任务就是设计软件的构造，也就是确定程序由哪些模块组成以及模块间的关系。通常用层次图或构造图描绘软件的构造。2.2构造图2.2.5具体设计这个阶段的详细内容我把放到模块分析的章节去分析。下面仅作个扼要的概述。总体设计阶段以比拟抽象概括的方式提出了解决问题的办法。具体设计阶段的任务就是把解法详细化，也就是回答下面这个关键问题：“应该如何详细地实现这个系统呢？这个阶段的任务还不是编写程序，而是设计出程序的具体规格讲明。这种规格讲明的作用很类似于其他工程领域中工程师经常使用的工程蓝图，它们应该包含必要的细节，程序员能够根据它们写出实际的程序代码。2.2.6编

25、码和单元测试这个阶段的关键任务是根据以上阶段分析的软件模型，编写各个功能模块。要注意的是程序的扩张性和可读性。以便以后软件的升级修改。同时要仔细的测试每个功能编写好的功能模块。这个内容也放到下面编译运行章节去。2.3用户界面用户界面在整个系统的使用中起着很大的作用，它将直接影响到用户对软件的评价。界面是人机交互的平台，所以在设计时尽量往用户方考虑。提供操作简便和友好界面。下面是系统使用的界面，感觉还有很多地方需要改良和完善。但是总体来讲已经能够基本知足系统的需要。拥有较为良好的交互功能。图2.3用户界面2.4系统解析下面结合操作对各个功能模块设计进行相应的解析。2.4.1界面部分这部分我采用的

26、是vc+提供的单文档视图框架，该框架为我们生成了Window应用程序最基本的界面无需本人动手编写复杂的菜单模块等代码，只要在基于这个框架的基础上对相应的功能进行补充和扩展。2.4.1.1CFiveChessView的属性CView类是该框架中一个很重要的类，它提供了大部分的交互功能，如菜单，鼠标左键等消息的的响应。下面对本系统中的CFiveChessView类的几个重点内容做个介绍。m_ListenSocket和m_ClientSocket变量，这两个类成员均是派生自CSocket类，前者定义为一个服务端的套接字Socket变量，它用于服务端负责监听，当它收到某个主机发来的连接请求时，将m_C

27、lientSocket和远程主机端的套接字关联。这样双方能够进行通信了。CMatchm_match这是一个棋盘类的一个变量。关于这个类将在后面做具体的讲解，将棋盘单独抽象为一个类，并向外部提供棋盘的一些操作。这比拟符合面向对象编程。CComputerm_computer这也是一个很重要的成员，它将人机对战中的电脑方抽象成一个类，该类提供不同的等级的下棋功能。根据当前棋盘的局势给出最佳的下棋点。该类也将在后面给出具体的介绍。m_mode这是用于标记当前系统的是属于哪种形式人机或者联机，当它是人机的状态时值为P_PK_C枚举类型的值，同样当它是联机状态就为P_PK_P。若当前没有选择的状态值就为NOCHOOSE，表示当前还为进行选择。m_who用于标记使用棋子的类型，1代表黑色，2代表白色。m_turn这是联机中用于标识当前是轮到哪方下棋了。m_bWin标识本机方赢的状态。m_bOver标识游戏能否已经结束。2.4.1.2CFiveChessView的函数下面的五个变量均为CBitmap类对象，m_lastwhitechess加载的是位图。m_whitechess加载的是位图，m_lastblackchess加载m_blackchess加载位图，m_black加载位图。m_board加载的是棋盘位图。