基于CEasyX剪枝算法的能人机对弈的五子棋游戏设计与实现毕业论文程序源码大家好今天给大家介绍基于CEasyX剪枝算法的能人机对弈的五子棋游戏设计与实现文章末尾附有本毕业设计的论文和源码下载地址哦。需要下载开题报告PPT模板及论文答辩PPT模板等的小伙伴可以进入我的博客主页查看左侧最下面栏目中的自助下载方法哦文章目录基于CEasyX剪枝算法的能人机对弈的五子棋游戏设计与实现毕业论文程序源码1、项目简介2、资源详情3、关键词4、毕设简介5、资源下载6、更多C#毕业设计项目1、项目简介目前为止市面上已经有了很多的五子棋游戏但多为残局和PVP少数的PVE模式棋局也大多存在着运算时间长、对计算机要求高、不够智能等缺点无法实现在一个简单的个人计算机上做到高速有效反应。该系统基于C/C实现在个人计算机上可以人机对弈的五子棋游戏。通过设立五元组、定价估值、深度搜索等方法。并以是否进行深度搜索为区别设立了可供对比的两个模式。就整体来说该程序体积小环境要求低在快速反映的基础上还有不低的智能。2、资源详情项目难度中等难度适用场景相关题目的毕业设计配套论文字数7306个字21页包含内容全套源码配整论文3、关键词人机对弈、快速反应、深度搜索、剪枝4、毕设简介提示以下为毕业论文的简略介绍项目完整源码及完整毕业论文下载地址见文末。引言目前为止虽然市面上已经有了很多的五子棋游戏但是大多依旧是依靠残局和PVP来充数虽然有可以实现人机对弈的但是大多存在着运算时间长、对计算机要求高或者不够智能等缺点无法实现在一个简单的个人计算机上做到高速有效反应。该系统通过设立五元组从而对每个位置进行价值评估。在有多个位置可选的时候进行深度搜索来提升其智能性。以是否进行深度搜索为区别设立了两个模式可供对比。整体来说该程序体积小环境要求低在快速反映的基础上还有不低的智能完全满足一般的游戏需求。1 前言五子棋游戏历史悠久规则简单老少皆宜对环境要求又简单这使得其受众不断增加成为了如今最普遍的棋类游戏之一。对人机对弈五子棋的研究过程中人们不断地对其搜索算法进行优化升级已经发展出了极大极小值搜索、贪心算法、遗传算法、置换表技术、运用 MCTS 和卷积神经网络训练、使用α-β剪枝来减小搜索范围等各种方法以此来优化搜索方法、提高程序的智能性并拥有了许多的成果。然而在日益现代化的今天五子棋游戏虽然早已在互联网上出现但是大多却只是依靠残局和PVP来充数实现人机对弈的虽然也有但是却依旧存在着运算时间长、对计算机要求高、不够智能等缺点无法实现在个人计算机上做到高速有效反应。2 相关技术介绍2.1 五子棋规则简单介绍双方一方执黑棋一方执白棋交替落子黑子先手。棋盘大小为15×15。该系统不考虑禁手等情况。当任意一方落子后如果形成五子连珠则会立刻获得胜利另一方落败。2.2 使用的技术的简单介绍。C/CC语言作为一种通用的高级语言其最显著的特点就是运行速度快几乎和汇编等同。而C则是可以面向对象编程并且可以运行所有的C代码。EasyX EasyX Graphics Library 是针对 Visual C 的免费绘图库支持 VC6.0 ~ VC2022简单易用学习成本极低应用领域广泛。α-β剪枝技术Alpha-beta剪枝是一种搜索算法用以减少极小化极大算法Minimax算法搜索树的节点数。在系统进行深度搜索模拟棋手与系统交替落子的过程中便多次使用。其原理为通过剪掉博弈树的冗余枝杈从而减少系统开销节约时间。如图1所示便是通过剪掉B及其子节点来缩减了冗余计算的数量。具体算法思路详见2.5.4 剪枝算法。该算法一种对抗性搜索算法主要应用于机器游玩的二人游戏如井字棋、象棋、围棋。图 1 剪枝算法示意图2.3 系统思路的简单介绍五子棋游戏作为经典的零和博弈模型博弈的每一方都假设对方的所有策略的根本目的是使自己最大程度地失利并据此最优化自己的对策那么系统通过一定的线性运算可使得每一次博弈过程都能够找到一个“最优解”最终达到胜利。由于C语言的代码运行速度几乎与汇编代码等同所以为了运行速度便使用C来编写程序。由于C可以运行任意一行C代码以及绘图时使用了EasyX Graphics Library所以系统最终为“.cpp”格式。EasyX Graphics Library是针对 Visual C 的免费绘图库。程序使用EasyX 来创建窗口绘制棋子使用五元组来作为最基本的估值单位使用估值函数计算单个点位和当下棋局的价值使用搜索算法来确定系统落子位置。在游戏过程中系统使用全局变量num来记录步数以此来判断轮到哪一方落子。用自己创建的coordinate类型来记录每一个位置的信息。使用五元组作为基础最基础的价值计算元素。使用value_one函数来评估单个点位的五元组价值之和。使用value_whole函数评价当下整个棋局的优劣。在不进行深度搜索时系统通过比较每个空余位置的点位估价寻找其最大值当下最优解来确定落子位置。在进行深度搜索时则会依次遍历估价最大五个位置模拟交替落子并计算最后的棋局价值选择最优解将棋局导向对系统方最有利的局面。每次真正落子后都要根据不同情况去判断是否胜利具体见2.5.5 胜利判定。structcoordinate{//coordinate类记录了某一点位的落子情况及其估价。intx;inty;//x,y为该点位在数组中的坐标。intrt;//rt表示棋子颜色。intscore;//score表示该点的估价。}2.4 系统结构的简单介绍系统的简单组成开始界面 选择模式界面(以是否进行深度搜索为区别) 游戏界面 是否结束界面 结束界面。系统运行结构简单介绍系统运行大致流程如图1 系统运行流程图其中num表示步数value值为该点在当前棋局中的估价表示在下一步中该点的重要程度计算方法详见2.5.2 估值评分深度搜索是考虑到有时候对当下而言的最优解并非是对整局游戏而言的最优解系统需要考虑如果在此处落子后下一步对方如何落子以及该如何应对算法思路与详情见2.5.3 搜索算法。图 2 系统运行流程图2.5 关键点介绍2.5.1 五元组在游戏中对于连续的五个点位可以称其为一个五元组。五元组共有四种方向即左右方向上下方向左下-右上方向左上-右下方向。棋局中的每一个点位最多属于20个五元组边界位置的点位所属的五元组少于20这些五元组可以按方向分为4组。如果系统想要取得胜利则必须有一个五元组中含有且只能含有五颗己方颜色的棋子。对于任意一方而言当一个五元组出现了对方的棋子那么自己将无法在该五元组中取得胜利。此时这种五元组可以称其为无效五元组。同理如果一个五元组中只含有一方的棋子那么这种五元组可以称为有效五元组。五元组作为最基础的评分估值单位系统对于每一个有效五元组都将根据其中包含的棋子的数量及敌我双方的身份来给其估价估价方法详见2.5.2 估值评分。五元组也是胜利判定的单位。如果系统判定某一方获得胜利则必定是该方拥有了一个含有五颗己方棋子的五元组。2.5.2 估值评分。这个系统中共有两个估值函数一个是评价一个点的价值的点位估价函数value_one一个是评价整个棋局的棋局估价函数value_whole。在点位估价函数中系统把需要评分估价的点的五元组按照方向分为四组每组单独求和存放在数组value[]中。所以有value_one_end value[0] vlaue[1] value[2] value[3];在任意一个方向中其对应的value值等于这个点位在该方向上的所有有估价的五元组的估值之和。对于每一个有效五元组系统都应该按照敌方或己方棋子数量给其一个估价。而对于无效五元组己方虽然不能在该五元组上取得胜利但是却可以通过落子去阻止对方在该五元组中取得胜利因此它对己们而言也是有具有价值的。所以对任一有效五元组而言系统都要对该五元组进行估价。对于无效五元组因其对敌我双方都毫无价值所以不予估价。而且在合理范围内设计者可以通过调节估价来使系统变得偏向进攻或这偏向防御但就一般而言估价依据则是系统组成五连的价值阻止敌方组成五连的价值系统组成四连阻止敌方组成四连系统组成三连阻止敌方组成三连。该系统使用的函数的估价表如表1 点位估价函数估价表所示表 1 点位估价函数估价表棋子数 0 1 2 3 4己方 1 10 100 1000 100000敌方 0 5 50 500 5000而在棋局估价函数中函数得到的value值表明了棋局对己方而言的优劣。使用该函数并进行深度搜索的目的是为了避免系统通过点位估价函数寻找到的当下最优解为敌方的陷阱。在该函数中系统通过将每一个有效五元组估值之和减去每一个无效五元组估值之和所得的结果作为评价当下整个棋局对系统方的优劣。很明显如果棋局中有更多的四连或者三连则更容易胜利。在value函数中系统将整个棋局的价值进行评估。这里函数用己方存在的有效五元组价值之和减去敌方的有效五元组价值之和得到的结果作为标准来评价棋局。即扫描棋局寻找其中的有效的三连四连指有效五元组内的三连或者四连。因为是评价当下整个棋局的对己方而言的优劣所以这里的估价标准变为了五连价值所有四连的价值一个四连的价值多个三连价值。该系统中使用的估价表如表2 棋局估价函数估价表所示表 2 棋局估价函数的估价表棋子数 3 4 5 其他己方 1 100 100000 0敌方 1 100 100000 02.5.3 搜索算法在不进行深度搜索的情况下算法思路很简单只需要将没有落子的位置遍历一次分别计算该位置的价值。然后寻找其中的value值最大值点位并在此落子就可以了。在进行深度搜索的情况下算法则会变得比较复杂、耗时。为了做到节省时间、快速响应在这里系统只进行3层搜索。算法运行的流程图如图2所示。图 3 深度搜索算法运行流程图算法会优先进行深度搜索。第一层搜索的作用是模拟系统落子如果可以取得胜利则直接收起模拟的落子然后在该位置落子取得胜利。如果不能取得胜利则进行第二层模拟。第二层搜索的作用是模拟棋手落子如果棋手可以取得胜利那么减掉这一枝。如果不能取得胜利则进行第三层模拟。第三层搜索的作用是模拟系统落子然后寻找最优势的棋局。由于多层的搜索生成的博弈树有着大量的子节点所以在其中嵌入了剪枝算法来减少运算节约时间。剪枝算法详见2.5.4 剪枝。这棵由深度搜索生成的博弈树其父节点的值为符合要求的子节点的极值。算法会在第三层中根据棋局评估函数计算得到一个value。那么第二层的节点值为在第三层中各自的子节点中的最大值。第一层的节点值为第二层他们各自的子节点中的极小值。假如博弈树如图3所示则BMIN(D,E);DMAX(H,I);图 4 博弈树示例2.5.4 剪枝算法算法生成的博弈树有着众多的子节点如果一项一项计算完全则会耗费大量时间并且这些子节点中只有一个是系统真正需要的。为了加快计算速度就需要减少冗余计算。由于这些节点中第一层、第三层取的是最大值第二层取最小值所以这里使用α-β剪枝来缩减搜索范围。Alpha-beta剪枝是一种搜索算法用以减少极小化极大算法Minimax算法搜索树的节点数。其原理为通过剪掉博弈树的冗余枝杈从而减少系统开销节约时间。在搜索算法中使用了深度优先的搜索方法。如图3D节点会比J、K等更早获得赋值B也会比F、G等节点更早获得赋值。那么假设通过计算得到D1J5。那么由于EMAX(J,K);即EJ。所以有DE。又因为BMIN(D,E)。所以BE。也就是说E和他的子节点为冗余数据这样就可以直接将其减掉不计算。同理如果B5,F1。所以CMIN(F,G)AMAX(b,c)。由于BF,所以BC。所以C及他的子节点也将会是冗余数据可以直接剪掉。剪枝算法的代码大概描述如下for(xinvalue_1){//遍历第一层vlauemaxvalue_1。for(yinvlaue_2){//遍历第二层,valuemin(value_2)。for(zinvlaue_3){//遍历第三层,valuemax(value_3)。if(zy)break;//即上文中DJ的情况。}if(yx)break;//即上文中BF的情况。}if(valuex)valuex;//valuemax(x)。}2.5.5 胜利判定系统中共在四种种情况下使用了胜利判定。前两种都未发生在深度搜索中。第一种是棋手一方落完子后判断是否棋手胜利。这里使用的胜利判定函数会以运行棋手落子函数时使用的坐标(a,b)。以这一点为中心想五元组的四个方向逐个判断是否胜利。这里以判断在左右方向上是否胜利为例。函数会先寻找连子的左右边界然后计算两边界之差这个差值再加一就是这串连子的长度。如果这个长度超过5那么就说明棋手在这个方向上取得了胜利。示例代码如下以判断左右方向为例其他方向同理。intjudge_lr(intx,inty,intcolor){//仅判断在左右方向上是否胜利。x0x;y0y;//记录原本点位x1,y1search_left_uncolor(x,y);//寻找左边界边界为地方棋子或空xx0;yy0;//复位x2,y2search_right_uncolor(x,y);//寻找右边界边界为地方棋子或空xx0;yy0;//复位if((x2-x11)5)returnwin;//判断是否胜利}第二种是系统落完子后的胜利判定。但是系统在落子则是依据点位估价函数来判断的在这个函数中系统会搜索每个点位所属的五元组如果发现他的某个五元组里已经有四个己方棋子那么程序就可以直接在这里落子并停止继续搜索然后直接取得胜利。这样不仅可以直接省掉一次单独的胜利判定还省掉了一些冗余的搜索。进一步加快了程序的运行速度。以判断在上下方向上是否胜利为例。x0x;y0y;//记录原本点位while(color(x,y)uncolory-10)y--;//寻找上方边界边界为敌方棋子x1x;y1y;xx0;yy0;//记录、复位while(color(x,y)uncolory114)y;//寻找下方边界边界为敌方棋子x2x;y2y;xx0;yy0;//记录、复位for(yy1;yy2-4;y){//遍历两边界内的每一个五元组num0;//用以记录五元组内己方棋子的数量。for(l0;l5;l){//遍历无元组内部if(color(x,y)color)num;//记录数量}if(num4){//某个五元组中已经有了四个落子down(x0,y0,color);//落子win_color;//取得胜利break;}valuevalue_num(num);//在无法取得胜利时记算该点的价值。}其中点位估价计算的方法详见2.5.2 估价评分中的点位估价函数介绍。第三种和第四种发生在深度搜索中。第三中则是在深度搜索的过程中如果发现棋手一方将会获胜。那么这种落子方法必然不是程序最终要找的方法。所以直接需要跳出循环将其父节点减去。这里以判断在左上-右下方向上是否胜利为例。x0x;y0y;//保存原本点位x1,y1search_lu_uncolor(x,y);//寻找左上方边界xx0;yy0;//复位x2,y2search_rd_uncolor(x,y);//寻找右下方边界xx0;yy0;//复位if((x2-x11)5){//如果胜利seat_1_max[seat_1_i];-100000000;/*给其父节点赋一个特别小的值表示 非常不推荐系统在其父节点代表的位置落子。*/break;//跳出循环防止父节点被再次覆盖}第四种则是在模拟中发现系统可以取得胜利那么就记录下这个路径然后跳出循环在此落子。循环遍历前win_flag0;初始化 win_flag 第一层中 xseat_1_max[seat_1_i].x;yseat_1_max[seat_1_i].y;if(flag_win1){down_color(x,y,color);black;}//如果收到下层传来的消息则落子并跳出循环。第二层中if(flag_win1){loadseat_1_i;black;}//如果收到下层传来的消息则记录路径跳出循环。第三层中intjudgejudge_lu_rd(intx,inty,intcolor);//判断是否能取得胜利其判断思路与第一种情况类似if(judgewin){win_flag1;black;}//如果胜利则给win_flag赋值。并跳出循环。else{valuevalue_whole(intcolor);}//未取得胜利则计算棋局价值3 系统测试系统编写完成之后还需要进行测试以此来判断系统是否达到既定目标是否出现错误等。3.1基本功能测试3.1.1 测试界面运行目标测试开始、选择模式、游戏、是否结束、结束等界面是否可以正常运行。时间结果可以正常运行字体变色、页面跳转、落子位置、页面变淡效果、结束游戏等功能可以正常运行。部分截图3.2系统不同模式智能性测试3.2.1 选择黑棋黑棋先手机器方不进行深度搜索。一般业余玩家已经很难取得胜利但是落子方法较为僵硬偶尔还会出现可以让人一眼看出想要在那个五元组中取得胜利的落子。但是即便如此通过凭借对各个点的估价比较选出最优解。系统落子依旧算得上迅速、高效一般人依旧很难招架属于以力压人。图 8 选择黑棋的游戏截图3.2 选择白棋白棋后手机器方进行深度搜索。对广大业余的业余选手来讲单就胜率来讲虽有提高但是一百局里赢三次还是两次带来的体验差别并不大。但是可以明显感受到的是系统的落子更加“拟人化”。每一次落子都好像有极多后手会让人在不知不觉中尽失先机。缺点是有的时候会为了更长远的布局而没有选择对当下而言更好的选择。图 9 选择白棋的游戏过程截图3.3 测试结论在玩家棋力不是很高的情况下是否进行深度搜索对于玩家来讲并不是很重要。只要评分表做的较为合理在大部分情况下大众就很难下赢机器。但是如果多玩几局就会发现这种算法的落子习惯。系统落子的表现会逐渐显得套路化虽然依旧很难下赢但是会很快失去乐趣。而使用深度搜索算法进行的机器方套路化表现并不明显落子布局更加长远但是偶尔却会陷入“想的太多”的误区使得落子布局虽然更加长远了却失去了对当下而言最有利的选择从而出现一种舍近求远的现象。如果想要再进一步或许需要研究更加科学的棋局价值评估算法。4 总结1、该程序的目的是实现在个人计算机上的能快速反应的可以人机对弈的五子棋游戏。2、为了节约时间系统使用C/C语言书写。3、该程序以是否进行深度搜索为区分共设有两个模式以便对比。4、系统使用五元组作为最基本的计算单位。5、系统的两个模式都可以实现目的在面对广大的业余玩家时都可以拥有不错的胜率。在运行速度上两个模式相差不大不进行深度搜索的话速度略高。6、在不进行深度搜索的模式中如果多玩几局就很容易看出一些系统的落子规律容易腻而且如果设下陷阱系统也不会规避。在进行深度搜索的情况下。7、在进行深度搜索的模式中深度搜索会使得程序表现得更加“人性化”会出现一些不落在最优解上的“错误”但是相较于上个模式可以多规避一些“陷阱”。参考文献[1]陈树彬; 和昱旻; 原菊梅 五子棋落子算法的研究[J] 电脑与信息技术 2021-09-30[2]Stanley B. Lippman . C Primer第五版[M]. 电子工业出版社 2015.[3]周洋; 邓莉 一种五子棋博弈算法的分析 [J] 谢煜 现代计算机(专业版) 2017-04-05[4]欧俊臣; 沙玲; 杨淞文 基于 MCTS 和卷积神经网络的五子棋策略研究[J] 软件 2020-04-15[5]刘瑞 五子棋人工智能算法设计与实现[DB] 华南理工大学 2012-05-01[6]牛恺泽, 邓鑫. 五子棋人工智能研究与实践[J]. 数字通信世界, 2019(01): 32-33.[7]孙世文.五子棋人工智能算法实现研究[J].中国新通信,2018,20(23):143.[8]宋万洋.基于α-β剪枝树算法的安卓五子棋程序设计与实现[J].现代信息科技,2019,3(11):92-9397.[9]许南山,丛磊,孙风平.并行实现有自学习能力的五子棋AI[J].计算机工程与应用,2006(30):45-47.[10]王长飞,蔡强,李海生.智能五子棋算法的设计实现[J].系统仿真学报,2009,21(04):1051-1054。[11]董慧颖,王杨.多种搜索算法的五子棋博弈算法研究[J].沈阳理工大学学报,2017,36(02):39-4383。[12]Silver D,Huang A,Maddison C J,et al.Mastering the game of Go with deep neural networks and tree search[J].Nature,2016,529(7587):484-489.[13]Silver D,Schrittwieser J,Simonyan K,et al. Mastering the game of Go without human knowledge[J].Nature,2017,550(7676):354-359[14]Silver D,Hubert T,Schrittwieser J,et al.Mastering chess and shogi by self-play with a general reinforcement learning algorithm[EB/OL].arXiv preprint arXiv:1712.01815,2017.致谢省略5、资源下载本项目源码及完整论文如下有需要的朋友可以点击进行下载。如果链接失效可点击下方卡片扫码自助下载。序号毕业设计全套资源点击下载本项目源码基于CEasyX剪枝算法的能人机对弈的五子棋游戏设计与实现源码文档_C__能人机对弈的五子棋游戏.zip提示如果下载链接失效可点击下方卡片扫码自助下载。6、更多C#毕业设计项目精选C#毕业设计83套——源码论文完整资源