基于HTML的五子棋AI大战游戏

基于HTML的五子棋AI大战游戏摘要HTML5技术的发展推动了游戏行业的蓬勃发展。HTML5的五子棋游戏是一款休闲类别的棋类网页游戏,该游戏利用了Canvas技术完成了游戏主界面的开发，再利用Canvas组件进行棋盘和棋子的绘制,最后通过JavaScript脚本语言实现登录检验和电脑AI算法以及游戏内部逻辑实现。由于HTML5的跨平台性,使得该游戏能够方便快捷的在浏览器上直接运行,并且与各种浏览器都达到完美的兼容效果。关键词游戏;五子棋;HTML5;CanvasHTML-BASEDGOBANGMAN-MACHINEWARGAMEABSTRCTThenewstandardsandtechnologiesofHTML5havedriventhedevelopmentofweb-basedcasualgames.HTML5-basedGomokuisacasualchessgamethatusesHTML5'slatestCanvastechnologytocreateanddevelopgamepages.Firstly,thematerialeditingandgameUIinterfacedesigninthedrawingsoftware,andthenuseHTML5andCSS3torealizethegeneralframeandlayoutstyleofthewholepageofthegame,thenusetheCanvascomponenttodrawtheboardandthechesspiece,andfinallyrealizethecomputerAIthroughtheJavaScriptscriptlanguage.Algorithmandgameinternallogicimplementation.Thankstothecross-platformuseofHTML5,thegamecanberundirectlyandeasilyonthebrowser,andiscompatiblewithallkindsofbrowsers.KEYWOEDSgame;Gobang;HTML5;Canvas目录中文摘要 =1\*romanⅠ英文摘要 Ⅱ1绪论 1HYPERLINK\l"_Toc5341_WPSOffice_Level2"1.1课题研究背景 1HYPERLINK\l"_Toc23920_WPSOffice_Level2"1.2国内外研究现状 1HYPERLINK\l"_Toc15272_WPSOffice_Level2"1.3研究的目的和意义 1HYPERLINK\l"_Toc5341_WPSOffice_Level1"2开发相关技术简介 2HYPERLINK\l"_Toc7043_WPSOffice_Level2"2.1开发介绍 2HYPERLINK\l"_Toc5341_WPSOffice_Level3"2.1.1SublimeText3 2HYPERLINK\l"_Toc13790_WPSOffice_Level3"2.1.2ChromDevTools 2HYPERLINK\l"_Toc29797_WPSOffice_Level2"2.2主要技术 3HYPERLINK\l"_Toc23920_WPSOffice_Level3"2.2.1HTML、CSS 3HYPERLINK\l"_Toc15272_WPSOffice_Level3"2.2.2JavaScipt技术 3HYPERLINK\l"_Toc1058_WPSOffice_Level3"2.2.3Canvas简介 42.3博弈算法简介 4HYPERLINK\l"_Toc13790_WPSOffice_Level1"3需求分析 5HYPERLINK\l"_Toc30811_WPSOffice_Level2"3.1总体分析 53.2功能分析 5HYPERLINK\l"_Toc15770_WPSOffice_Level2"3.3可行性分析 5HYPERLINK\l"_Toc23920_WPSOffice_Level1"4系统功能设计 6HYPERLINK\l"_Toc2986_WPSOffice_Level2"4.1系统功能模块设计 6HYPERLINK\l"_Toc1968_WPSOffice_Level2"4.2游戏通信协议设计 7HYPERLINK\l"_Toc1968_WPSOffice_Level2"4.3游戏服务器设计 7HYPERLINK\l"_Toc1968_WPSOffice_Level2"4.4网络游戏功能设计 8HYPERLINK\l"_Toc15272_WPSOffice_Level1"5系统功能实现 9HYPERLINK\l"_Toc1968_WPSOffice_Level2"5.1前端界面功能 9HYPERLINK\l"_Toc1968_WPSOffice_Level2"5.2前端主界面功能 9HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.1初始化棋盘 10HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.2画棋盘格 10HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.3AI实现-极大极小值搜索算法 11HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.4评估函数 12HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.5Alpha-Beta剪枝算法 13HYPERLINK\l"_Toc5244_WPSOffice_Level3"5.2.6判断游戏胜负 146游戏功能测试 156.1测试概要 156.1.1测试方案 156.1.2测试安排和进度 156.2测试结果及其发现 156.2.1Bug清单 166.3分析摘要 166.3.1软件能力 166.3.2缺陷和限制 166.4测试结论 167HYPERLINK\l"_Toc1058_WPSOffice_Level1"总结与展望 17HYPERLINK\l"_Toc7043_WPSOffice_Level1"参考文献 18致谢 191.绪论1.1课题研究背景五子棋是一种大众化且比较容易上手的游戏，随着计算机网络技术的不断发展，各类玩家在线对战游戏如雨后春笋般不断冒出，其中就包括五子棋类游戏。五子棋不仅能够改善思维敏捷能力、还能开发人脑智力、手脑并用，而且蕴含哲理。游戏也逐渐从最开始的仅文字图片游戏向如今的3D游戏发展。但是休闲类游戏仍占据着游戏市场的一席之地。而且如今有人不断研究电脑算法，使得机器算法能与人脑对抗。其中IBM“深蓝”与战胜过围棋世界冠军柯洁的谷歌“AlphoGo”便是最具有说服力的代表。1.2国内外研究现状随着计算机网络通信的发展，游戏产业成为了一个香馍馍。游戏文娱产业的发展让人们得到了一种新的体验，现如今游戏产业规模已达几千亿美元，国内外制作的精良游戏不胜枚举，类似王者荣耀这种现象级手游，更是成为手游的代表作，游戏不仅丰富了人们的空余生活，还催生了一个巨大产业链。1.3研究的意义和目的本游戏重点研究实现电脑算法方面，研究将人工智能算法运用到五子棋的开发中去，与玩家进行人机博弈。而且五子棋的游戏规则单一，页面的绘制也比较容易，这样我们就可以重点研究高效率的人机算法，实现人机对抗，并且分设几个不同批次的难度。希望这次通过本次毕设，结合前端技术和数据结构与算法，完成该毕业设计，从而对软件开发的大体步骤与框架有一个全新的认识。12开发相关技术简介2.1开发介绍本次开发项目前端界面大部分采用HTML、CSS来编写，游戏内部的逻辑及人机博弈的用JavaScript来实现。且采用B/S架构，即浏览器与后台服务器交互，项目通过浏览器的解释，展现出游戏的大体界面。2.1．1SublimeText3简介SublimeText3是一个文本代码编辑器，其高效的性能成为了网页开发者必不可少的工具之一SublimeText它最开始被设计为一个具有丰富扩展功能的Vim文本编辑器。SublimeText3具有优美的用操作户界面和强大丰富的扩展功能库，例如代码缩略图，Python的插件，包管理工具，代码段等，还可自定义键绑定，菜单和工具栏。SublimeText3还支持多平台运行。SublimeText支持多种布局格式和代码的缩略图，其右侧具有文件略缩图和滑动条，可以方便地观察当前窗口所属区域。还具有按f11进入全屏免打扰模式功能。在屏幕比较大或需要同时编辑多个文件时效率特别高，一键进入全屏免打扰模式更是开发者的福音。SublimeText3支持文件夹直接浏览，可以打开文件夹，在左侧会有导航栏类似于一般IDE的文件资源管理目录，方便同时处理多个文件。SublimeText支持多位置同时编辑相同区域，只需要按住键盘ctrl键，就可以同时选择多个位置，同时操作，提高开发效率。SublimeText3具有自动恢复上次编辑区域，比如说在上次修改文件，但忘记了保存，这个时候意外退出软件，该软件不会直接询问用户是否需要保存，等到下次启动软件，文档之前的编辑状态都会恢复。2.1.2ChromeDevTools简介ChromeDevTools,是一种可以实时调试代码并且内嵌在谷歌浏览器内部的开发者工具。DevTools可以高效的跟踪CSS布局,设置JavaScript断点debug调试其脚本,以及进行javascript代码的优化。DevTools具有检查和实时更新页面的功能，可以在Elements面板中检查和实时编辑DOM容器中的任何元素。强大的Console功能，打印日志、执行测试代码、测量和统计执行和异常报错处理。方便好用的Network功能，可以记录并分析所有的网络请求、测试网络的性能和查看加载事件等等。2.2主要技术2HTML、CSS简介HTML是一种超文本标记语言。是一种网页内容载体，内容就是网页开发者写在网页页面上，想让用户浏览的信息资源，可以囊括文字、图片、超链接，视频资源等。CSS样式是网页的外观表现。就像网页的外衣一样。比如，标题字体大小的样式、颜色的变化，或为页面插入背景图片、边框等，这些称之为外观表现。称为超文本标记语言，是因为一个网页可以同时对应多个HTML文件，并且网页文件一般以.htm为扩展名或者.html。网页开发者可以使用任何能够生成文本类型资源文件的编辑器来产生超文本标记语言文件，只需要在退出文件时，修改该文件名的后缀名即可。标准超文本标记语言文件类型都具有规范的整体文本结构，而且标记一般都是成对出现（br标签除外），即超文本标记语言文件的开头与结尾标志和超文本标记语言的head与body两大部分。JavaScript简介JavaScript是一种脚本解释型语言，是一种动态的基于原型的语言，广泛应用于客户端，最早是被应用在静态页面上，用来给HTML网页增加动态式的功能。为了取得技术领先，微软推出了JScript，与JavaScript一样可以方便的在浏览器上面直接运行和调试。后来开发者统一了其标准，JavaScript兼容于ECMA标准，因此也称为ECMAScript。JavaScript被常常用于网页应用开发。其增添了动态功能，提供各式各样的网页页面。JavaScript一般是写在html文件中就可以实现开发者需要的功能。同其它语言一样，其有自身的基本数据类型，表达式和算术以及逻辑运算符及程序的基本流程逻辑和对应的数据结构。Javascript有四种基本数据类型用来处理数据和文字。其具有以下特点：原生、基于对象、便捷、动态性以及跨平台性。JS主要作为本地脚本直接在用户的浏览器上运行，所以不需要服务器的支持。而随着服务器性能的发展，虽然开发者更喜欢运行于服务器端的脚本以保证安全，但JavaScript仍然凭借其跨平台、易上手等优势领先与其他语言。而例如ajax还可以在一个静态页面上，动态得生成不同的页面。Canvas简介canvas是HTML5新标准出来之后提供的一种新标签。在新标准出来之前，网页页面只有一些比较简单的标签，比如<p>、<h2>。但有了canvas技术后,Web页面开始变得丰富多彩起来。Canvas可通过JS脚本来绘图。还能实现立体图的渲染和系统的优化。canvas主要应用的领域：游戏和动画。本次设计就是应用Canvas功能绘制游戏界面。还可用于广告页面的动态开发，发挥巨大的作用。还可以直接嵌入网站的内容：类似图表echarts、音视频、可以直接与Web融合，不需要任何的插件，直接内嵌在JS中即可达到想要的效果。博弈树搜索算法简介五子棋游戏，是黑白双方轮流下子。就产生了不同的棋盘局面，不同的应对方法。比如说黑方先下子，白方就总共有224种落子的方法，如果黑方选择了其中的一步来应对，那么白方就有223种方案和223种局面来应对下一步。这样来看，就产生乐一个又一个的树。3博弈树搜索算法可以完全不需要顾及具体是什么博弈事件，只需要在算法的层面上进行研究。电脑算法是否准确我们需要借助与估值函数，奕会影响搜索算法的准确性。在整个搜索算法过程中，该函数需要不断的，反复的被系统验证，确定合理的值。43需求分析3.1总体分析本次毕业设计是需要开发出一个带有电脑智能算法和网络对战功能的五子棋游戏，能够在网络上运行。五子棋电脑算法是本游戏的核心关键所在，应当实现市场上大部分同款游戏所具备的功能，例如悔棋、选择游戏难度、开始下棋、匹配玩家、保存棋局最后页面等。玩家对战：选择和玩家对弈操作，需要双发同时确认才能开始游戏，也可以执行悔棋功能，但是需要对方玩家的同意，而且需要说明黑先白后，玩家可以申请先手。并在游戏结束一方获胜后，可查看最后胜利或者失败的画面。3.2功能分析（1）介绍游戏的规则：对局双方各手执一色棋子，空棋盘开局。先后顺序为黑先、白后，双方交替下子，而且每次只能下一子。棋子落在棋盘的横线交叉的空白点上，棋子下定一个位置后，不得向其它点移动，奕不得从棋盘上拿掉或拿起另落他处。黑方的第一枚棋子必须下在棋盘正中央俗称“天元”位置上。每回合轮流下子是双方的权利，但奕不允许任何一方放弃落子权。（2）选择对战模式：游戏分为人机对战和玩家对战。两种游戏模式都具有悔棋与查看最后输赢画面。（3）用户注册：注册为玩家才可以登录游戏，需要填写基本注册信息，系统会自动识别验证信息填写的规范，注册完登录后就可以选择游戏对战模式以及电脑AI的难度。（4）用户登录：玩家注册完成后，回到页面填写账号密码，游戏将根据玩家的账号ID以及登记自动匹配对手。3.3可行性分析技术层面：运用windows7及以上操作系统，以谷歌浏览器为用户的主要操作平台，开发出一款界面优美、功能齐全的五子棋人机/双人对战游戏。经济层面：系统的开发成本比较低廉，已经有的PC机就可完成开发所需的条件。操作层面：操作主要是鼠标与键盘搭配使用，主要凭借鼠标来确定棋子下落的位置，操作简单明了，只需要明白游戏规则以及其他的快捷键即可。54系统详细设计4.1系统功能模块设计如今现有的网络编程模式主要分成两类：一种是基于客户端/服务器模式，另一种是浏览器/服务器模式；C/S（客户端/服务器）程序具有比较好的系统交互性，功能强大，但是必须要安装平台软件； B/S（浏览器/服务器）模式下要求客户端可以直接在浏览器下运行。但是必须具有一定的响应速度和安全限制，所以其交互性与功能有一些限制。五子棋系统的交互性要求较高，所以本系统选用了在 B/S模式进行实现。本程序中提供两种游戏模式：玩家电脑对战模式和玩家对战模式。游戏开始之前，可以选择先手确认，与电脑一决高下。在玩家对战中，可以通过先手请求来确认是黑棋先还是白棋先，同时设有悔棋功能。如果没有启动的话，玩家是无法直接进行游戏的。如果使用计算机自动完成，那么就直接用批处理方式；信息的存储使用的是传统的文件系统，因为不需要储存玩家的具体信息，只需要保留对局双方的棋局信息即可。并且增加悔棋，美化界面，实现观看电脑与电脑之间的对战等功能。4.2游戏通信设计协议因为是PC线上玩的游戏，通信模式就是浏览器发起网络请求，然后服务器方面响应并回复请求。避免了网络信号不好时，玩家掉线的情况。该游戏没有设计固定的用户，采用的方法是游戏每次都会向服务器申请一个游戏ID，使用这个游戏ID在互联网上和其他用户进行对战。于是报文协议设计了两种模式：普通请求/回复报文gamequest、游戏数据报文nextquest。关于游戏请求与游戏对局时的通信，因为采用的是请求加回复的方式，服务器不能主动通知浏览器有新的游戏开始或是对手已经下了下一步棋，因此需要客户端主动向服务器获取相应的信息。于是这部分被设计为浏览器端定时向服务器发送更新数据的请求，服务器一旦接收到了请求，就把通过该请求的TCP连接发回去。这样虽然增加了网络的流量，但为了数据的稳定性必须做出一定的牺牲。4.3游戏服务器设计这是网络游戏最重要也是最核心的一部分。一个高效、并且稳定的游戏服务器程序直接决定了该游戏的体验。在实际的游戏服务器开发中，游戏内部的逻辑与网络通信逻辑可能由不同的人员分工合作进行开发。因此，游戏逻辑与网络通信逻辑应在保证效率的情况下实现尽可能的低耦合。游戏的逻辑与网络通信需要尽可能地独立，就我们五子棋服务器而言，网络通信端使用PPC、epoll，并且都和游戏逻辑无关，只要能接收分类，并交给游戏进行逻辑处理，并将游戏逻辑处理好的数据发出即可。关于服务器的游戏逻辑，首先我们要明白服务器要做哪些事情：1、用户游戏ID的申请与管理2、对局数据的处理与管理6大致就以上这两种事情。但是因为游戏的客户端数量很多，不同的浏玩家之间进行对局，必须要清晰地处理与管理这些数据。我这里建立了一个GameIdPool，用于游戏id的储存与申请，以防发生错误，给用户分配了无效或者是重复的id。对局数据的处理与管理：在两个用户都分配到id的情况下，双方都能申请进行游戏。这时服务端做的就是匹配好这些用户，并通知这些用户已经可以开始游戏。由于篇幅的原因，我就省略了服务器的代码。大致说一下各种函数的用途。PlayerToPlayer:它的作用就是用来匹配玩家。当有用户客户端申请玩家对战进行游戏时，服务器会先调用相应的匹配函数来寻找可以进行匹配的另一个玩家，如果找到了合适的玩家，接下来就会调用SetPTP来检查这两个玩家是否有对局关系。如果没有匹配到相应的玩家，则会调用setwait函数来继续等待其他的用户进行匹配。该函数使用的数据结构为简单的hash映射。SetPlayerStatues:用于存放玩家的对局数据，使用pool方式，本地下棋的信息将会储存在这里，用以客户端得到对方的落棋信息。PlayerTPlayer的info会直接映射到pool的对应下标。不同id的浏览器查找数据会相当地迅速。4.4网络游戏功能设计现在我们回到游戏的客户端（浏览器）上，前面已经实现了单机游戏的设计。现在要做的就是加入网络功能，其实就是把单机部分的AI接到服务器上。首先是游戏id数值的获取。我们先向服务器发送一个GetId的网络请求，然后就会得到服务器分配的id数值。然后浏览器就会将这个id当成自己的游戏id，直到告知服务器玩家退出游戏，或者是服务器在长时间没有得到该id的情况下自动释放前都是有效的。当客户端分配到该id数字后，就可以向服务器发起游戏匹配请求GetNewGame。为了防止系统匹配不到玩家这种情况发生，设置发送匹配的网络请求最多会维持一分钟，在这一分钟结束后，浏览器便会向服务器发出停止匹配的请求。当同时有两个客户端在这段交叉时间进行匹配，便能够匹配在一起进行游戏。游戏匹配成功后，浏览器端将会收到服务器发过来的对局基本信息，其中囊括了了对手id、玩家1，2是否申请先手还是后手。等到游戏开始后，先手先下棋然后将数据提交到服务器，由后手来更新数据，按照这样依次循环下去直到达成游戏胜利条件，游戏就会结束。75系统界面实现5.1前端界面功能前端界面主要的功能是：游戏说明、单人模式、双人模式。（图5-1）图5-1功能演示5.2前端主界面模块界面在整个游戏界面起着很大的作用，它将直接影响到玩家对游戏界面美观的评价。界面是整个人机交互（玩家对战）的平台，所以在设计时尽量往用户友好方向考虑。提供一个操作简便和友好界面。以下是下棋对战使用的界面，还有很多地方需要改进和操作的功能需要完善。但是总体来说已经基本能够满足游戏的需要。拥有较为良好的交互功能。如图5-2所示。8图5-2下棋界面5.2.2初始化棋盘function InitializeGobangBoard(){//初始化棋盘函数代码，表示将用来处理Paint的Control事件的方法。gobangBoardGroupBox.Paint+= newPaintEventHandler (gobangBoardGroupBox_Paint);Var x,y;for (x=0;x<15;x++)for (y=0;y<15;y++){//初始化棋盘界面，每次开始时调用5.2.3画棋盘格functiongobangBoardGroup_Paint(objectsender,PaintEventArgs e){Var i;//获得画笔Graphicsgr=e.Graphics;PenmyPen= newPen(Color.Black,2);SolidBrush brush= newSolidBrush(Color.Red);for (i=0;i<15;i++){//绘制棋盘gr.DrawLine(myPen,30+i*40,30,30+i*40,590);gr.DrawLine(myPen,30,30+i*40,590,30+i*409}图5-3画棋盘格5.2.4AI实现-极大极小值搜索算法五子棋看起来有各式各样的走法，但是实际上把所有走法一步一步的展开，就是一棵巨大的博弈树结构。在这个树中，从根节点为0开始，奇数层表示电脑的所有可能的走法，偶数层则表示玩家所有可能的走法。假设电脑先手落子，那么第一层就是电脑的所有可能的走法，第二层就是玩家的所有可能走法，以此类推。我们首先假设平均每一步有50种可能的走法（首先不考虑优化），那么从根节点开始，往下面每一层的节点的数量就是上一层的50倍，假设我们只进行4层的往下思考，也就是电脑和玩家随机各走两步，那么这颗博弈树的叶子节点数为50^4=625万个。我们先不考虑这么多个节点要多久能计算出来。首先可以用递归来遍历这一棵树。而且我们需要一个评估函数对当前整个局势作出评估，返回一个得分数。我们规定对电脑越有利，这个分数就越大，对玩家越有利，这个分数就越小，分数的起点是从0开始。我们遍历这颗博弈树的时候，就很明显可以看出具体如何选择分支了：电脑走棋的层我们称之为MAX层，这一层电脑要保证自己利益最大化，那么就需要选择得分数最高的节点。玩家走棋的层我们称之为MIN层，这一层玩家要保证自己的利益最大化，那么就会选择得分数最低的节点。这也就是极大极小值搜索算法的名称由来。这是维基百科上的一张图5-4：10图5-4极大极小搜索算法此图中我们假设甲是电脑，乙是玩家，那么在甲层的时候，总是选其中值最大的节点，乙层的时候，总是选择其中最小的节点。而每一个节点的分数，都是由其孩子节点决定的，因此我们对博弈树只能进行深度优先搜索（DFS）而无法进行广度优先搜索。深度优先搜索用递归非常容易实现，然后剩下的主要工作其实是完成一个评估函数和对该搜索算法进行一定的优化，这个函数需要对当前局势给出一个比较准确的评分。五子棋是一个15×15的棋盘，因为棋盘大小是不会变动的，所以目前来看用15×15的二维静态数组来存储，效果是最好的。极小化极大值搜索算法，正常需要两个函数，一个搜索极小值，一个搜索极大值。因为其实大部分逻辑是一样的，完全可以把这两个函数合并成一个。然后把对手的分数变成负的，就是我方的分数。这种实现就是负极大值搜索。代码如下：varr=function(deep,alpha,beta,role,step,steps,spread){var_e=board.evaluate(role)varleaf={score:_e,step:step,returnleaf}varbest={score:MIN,step:step,steps:steps}//双方个下两个子之后，开启starspread模式//省略剪枝代码}115.2.5评估函数有了搜索策略，我们还需要进行局势的评估。我们简单的用一个整数表示当前局势，分数越大，则自己优势越大，分数越小，则对方优势越大，分数为0是表示双方局势相当。它接受一个角色，因为分数是相对角色而言的，返回一个整型数。比如如果对电脑是1000分，那么同样的局势对人类棋手就会返回-1000分。我们对五子棋的评分是简单的把棋盘上的各种连子的分值加起来得到的，对各种连子的基本评分规则如下：·连五，100000·活四,10000·活三1000·活二100·活一10如果一侧被封死但是另一侧没有，则评分降一个档次，也就是死四和活三是相同的分·死四,1000·死三100·死二10按照这个规则把棋盘上电脑的所有棋子打分，之和即为电脑的单方面得分scoreComputer，然后对玩家的棋子同样打分得到scoreHuma。scoreHuman即为当前局势的总分数。那么如何找出所有的连子呢，目前我的方式是遍历数组，一个个的数。因为代码量比较大，在这里我不会贴出代码，他就是对单个点进行评分的模块。5.2.6AlphaBeta剪枝算法可以做一个简单的计算，平均一步考虑50种可能性的话，思考到第四层，那么搜索的节点数就是50^4=6250000，在我的电脑上一秒钟能计算的节点不超过5W个，那么625W个节点需要的时间在100秒以上。电脑一步思考100秒肯定是不能接受的，实际上最好一步能控制在5秒以内。AlphaBeta剪枝算法是一种安全的剪枝策略，也就是不会对棋力产生任何负面影响。它的基本依据是：棋手不会做出对自己不利的选择。依据这个前提，如果一个节点明显是不利于自己的节点，那么就可以直接剪掉这个节点。前面讲到过，AI会在MAX层选择最大节点，而玩家会在MIN层选择最小节点。那么如下两种情况就是分别对双方不利的选择：1.在MAX层，假设当前层已经搜索到一个最大值X，如果发现下一个节点的下一层（也就是MIN层）会产生一个比X还小的值，那么就直接剪掉此节点。解释一下，也就是在MAX层的时候会把当前层已经搜索到的最大值X存起来，如果下一个节点的下一层会产生一个比X还小的值Y，那么之前说过玩家总是会选择最小值的。也就是说这个节点玩家的分数不会超过Y，那么这个节点显然没有必要进行计算了。通俗点来讲就是，AI发现这一步是对玩家更有利的，那么当然不会走这一步。2.在MIN层，假设当前层已经搜索到一个最小值Y，如果发现下一个节点的下一层（也就是MAX层）会产生一个比Y还大的值，那么就直接剪掉此节点。如图5-5所示。12图5-5剪枝算法示意图如上图所示，在第二层，也就是MIN层，当计算到第二层第三个节点的时候，已知前面有一个3和一个6，最大值至少是6。在计算第三个节点的时候，发现它的第一个孩子的结果是5，因为当前是MIN节点，会选择孩子中的最小值，所以此节点值不会大于5。而第二层已经有一个6了，第二层第三个节点肯定不会被选择。因此此节点的后序孩子就没有必要计算了。这是MAX节点的剪枝，MIN节点的剪枝也是同样的道理，就不再讲了。AlphaBeta剪枝的Alpha和Beta分别指的是MAX和MIN节点。代码实现如下。varr=function(deep,alpha,beta,role,step,steps,spread){//对max和min函数都增加一个alpha和beta参数。//在max函数中如果发现一个子节点的值大于alpha，则不再计算后序节点，此为Alpha剪枝。//在min函数中如果发现一个子节点的值小于beta，则不再计算后序节点，此为Beta剪枝。var_e=board.evaluate(role)varleaf={score:_e,step:step,steps:steps}returnleaf}varbest={score:MIN,step:step,steps:steps}//双方个下两个子之后，开启starspread模式按照wiki上的说法，最大优化效果应该达到1/2次方。也就是如果你本来需要计算10000个节点，那么最好的效果是，你只需要计算100个点就够了。13这是建立在所有的节点排序都是完美的假设上的。因为我们不可能完美排序，所以我们的优化效果达不到那么好。但是依然可以达到约3/4次方的优化效果。5.2.7判断游戏胜负五子棋游戏的胜负，是要判断棋盘上是否有这样一个点，从这个点为中心的横、竖、左斜和右斜四个方向是否有连续的五个同色棋子出现，则为游戏胜利。具体代码如下。functionCheckWin( int color ){var x, y;// 判断横向for ( y = 0; y < 15; y++ ){for ( x = 0; x < 11; x++ ){ if ( color == m_data[x][y] && color == m_data[x + 1][y] &&color == m_data[x + 2][y] &&color == m_data[x + 3][y] &&color == m_data[x + 4][y] ) { return TRUE;}}}}// 不满足胜利条件return FALSE;}由于这个算法所遵循的搜索顺序是从左到右、自上而下，因此在每次循环的时候，都有一些坐标无需纳入考虑范围。例如对于横向判断而言，由于右边界所限，因而所有横坐标大于等于11的点，都构不成达到五子连珠的条件，所以横坐标的循环上界也就定为11，这样也就提高了搜索的速度。146功能测试6.1测试概要6.1.1测试方案1.测试方法：黑盒测试2.测试内容：测试“新游戏”，“退出”，“选项”，“选择难度”这几个功能的实现和正确性。3.测试用例设计方法：基于具体场景设计测试用例6.1.2测试安排和进度（表6-1）表6-1测试项计划开始时间计划结束时间新游戏2019.3.302019.3.31选项（AI先手）2019.4.12019.4.2选项（玩家先手）2019.4.22019.4.3选项（玩家对战）2019.4.42019.4.5选择难度2019.4.102019.4.11退出2019.4.1220测试结果及其发现边缘落子测试结果如图所示（图6-1）图6-1测试边缘落子图6-2电脑先手落子152.1BUG清单表6-2bug清单Bug编号测试用例编号错误原因缺陷分析Bug-001006-边缘落子007-边缘落子008-边缘落子白子没对落在棋盘边缘的黑子进行封堵，当黑子先形成五子连珠是提示白子获胜产生这一缺陷的原因就是没有添加“禁手判定”算法Bug-002010-算法问题白子没对黑子进行封堵，提示黑子获胜产生这一缺陷的原因可能是算法不太恰当Bug-003015-天元落子016-天元落子黑棋应该在天元落下第一个子，但实际结果是黑棋可以不在天元落子没有增加天元落子算法6.3分析摘要6.3.1软件能力《基于html的五子棋AI大战》 游戏作为棋牌类休闲游戏基本可以满足玩家的需求，但是如果想往竞技游戏发展，则需要更多的改进和相应的完善。6.3.2缺陷和限制1.《基于html的五子棋AI大战》游戏的功能还不够完善，需要完善其功能。2.《基于html的五子棋AI大战》源代码中，没有编写“天元落子”的算法。这会导致在“AI先手”和“玩家先手”模式中进行游戏，黑棋先手可以不在天元落子，不符合游戏规则。3.《基于html的五子棋AI大战》源代码中，没有对边缘落子进行算法判定，导致一旦有边缘落子而形成五子连珠，AI就不会进行封堵，影响了游戏的难度。6.4测试结论该《基于html的五子棋AI大战》游戏存在很大的问题，但是由于针对的玩家群体不同，具体情况，还是由玩家需求来决定，毕竟该游戏只是人们工