基于Minimax和Alpha |
您所在的位置：网站首页 › 五子棋算法代码 › 基于Minimax和Alpha |
基于Minimax和Alpha
|
😎五子棋工程
需求→设计→编码→测试→发布 前言五子棋AI是上大学第一学期做的第一个工程，其中断断续续做了近一个月时间，其中的思路和估值参考了许多这位大神的作品lihongxun，但其中有些算法功能还未能完全掌握运用，不过目前棋力很多时候已不输于其AI。由于没有掌握C++，而项目开始时过于自信，虽然程序中用了类，但实则为一个实实在在的C语言项目，可以直接忽略其中类的部分。就以后学习数据结构和算法前，此版为最终版，但此版中还存在着很多问题，其中最严重的就是由于拓展时建立了很多节点，当搜索广度为10，深度为时时，未经剪枝，则会创建约10^10个节点而每个节点都存有棋盘和下一步的点位棋盘，因此怀疑是内存消耗过多而导致程序意外退出，即使加入剪枝和内存清理也同样存在着闪退问题，暂未查明详细原因，待学习数据结构以后再深入探究重构。 github项目地址:yrd1240189774/GoBang (github.com) 我学到了什么首先来说这是我独立完成的第一个包含GUI的完整的项目，学到了一种模块化的编程思想，先知道自己这个项目有什么需求，列清梳理好后再对函数进行设计，将各个功能区分开，最后再编码测试组装。其次是测试的重要性，这次项目中最头疼的无非就是找bug，当写好一串代码以后，不能运行或是不能安需求运行的概率很大，其中问题很可能就在一个数值的区别上，因此对更少的代码组织测试而不是等功能写好后在进行测试任意的多，具体的测试方法就不展开讨论，可以了解各种测试框架和最简单的利用print测试的方式。然后是代码的阅读能力有所提高，因为在学习是经常需要读懂别人的程序，尤其像java，js，python，对这些语言的语法和特点有了初步的认识。在一个是对算法尤其是博弈算法有了初步的了解，对Alphago有了更深的认识，就我目前的认知水平看来，机器眼里的世界是一个用代码表示的数学表示的世界，同样认识了许多崇拜的大佬。最后，Talk is cheap, show me your code. 这个AI的棋力如何如果你对五子棋有一些研究，你是不那么容易被战胜的尤其是在你先手的时候。而若一个人并不是一个五子棋高玩就像我一样，通过和我还有身边以及网络上一些小伙伴的对战结果来看，这个AI已经能战胜绝大部分业余玩家。专业一点来说，根据棋力测试，目前我确定的AI的搜索深度是 8 层，广度为6，如果没有特殊的优化技巧，这个深度已经达到了一个比较高的水平但广度较低，这也是我程序本身的一大问题。 迭代 第一代 实现棋盘实现双人对战 第二代 评估每一个落子位置的分数，不参杂思维挖掘 第三代蒙特卡洛搜索（单例模式） 评估函数搜索全局，选择3个落点 选择 拓展 模拟 回溯 第四代更新蒙特卡洛搜索为全局模式 新增Alpha-Beta剪枝 第五代 重写启发式评估函数，提高运行速度 实现
从计算机问世后，博弈算法从来就没有停止过改进的步伐。最早打败人类顶级棋手的AI就是深蓝。以下内容摘自百度百科： 深蓝是美国IBM公司生产的一台超级国际象棋电脑，重1270公斤，有32个大脑（微处理器），每秒钟可以计算2亿步。"深蓝”输入了一百多年来优秀棋手的对局两百多万局。 1997年 6月，深蓝在世界超级电脑中排名第259位，计算能力为每秒113.8亿次浮点运算。 1997年的深蓝可搜寻及估计随后的12步棋，而一名人类象棋好手大约可估计随后的10步棋。每增加1步棋的搜寻能力约等于增加下棋强度约80 ELO分。 博弈AI我的想法，博弈AI利用了现代计算机更加强大的算力，使得计算机能实现在某一功能上，对未来的评估能力和速度及细节上超过人类。目前，很多游戏都是"博弈"的，比如五子棋是双方博弈，斗地主也是。有些是双方竞争，有些会包含合作。在《人工智能-一种现代方法》一书中的第五章 《对抗搜索》中，介绍了博弈论专家们对博弈的一种定义： 有完备信息的，确定性的，轮流行动的，两个游戏者的零和游戏 这也是我们这套算法适用的场景，注意其中任何一个条件不满足，那么将无法直接使用这套算法进行设计。比如这些游戏就不行： 斗地主和德州等大部分牌类游戏，因为不是完备信息，看不到对方玩家的牌，而且还有随机性（摸牌不确定）四国军棋，不是完备信息，不是双人游戏DOTA，不是完备信息，不是双人游戏，而且不是轮流行动而五子棋，围棋，黑白棋，象棋等都是满足这些条件的，因此都可以用这套算法来实现。 AI这里说一下自己对该AI比较狭义的看法。就我从头到尾编写的看法感觉他并不能称作一个AI，而只是一个按照规则执行的既定的程序，并没有学习的能力，即使这一次失败了，也不会在进行总结修改提升，而一切的修改提升都是编程人员测试完成的，进行的一切的模拟和判断都是靠对现实情景的数字化符号化完成的，和Alphago类AI有着很大的差别。 极小化极大值搜索Minimax算法是一种递归算法，是一种消极的算法，他会假定对手的每一步都会走在对自己最有利的位置，也是一种深度优先的算法，他会先探索一个分支直至最底层，这也为Alpha-Beta剪枝提供了条件。 五子棋看起来有各种各样的走法，而实际上把每一步的走法展开，就是一颗巨大的博弈树。在这个树中，从根节点为0开始，奇数层表示电脑可能的走法，偶数层表示玩家可能的走法。在全局搜索的情况下，算法将对棋面中的每一个点位进行延申，他将对未来规定深度和运行时间下的每一种可能进行模拟，拓展，对每一个最终节点进行评估，也就是后面的局势评估函数，我们规定对电脑越有利，分数越大，对玩家越有利，分数越小，分数的起点是0。最后进行回溯，由于对落点的选取根据的是末节点的局势，因此Minimax的性能很大取决于局势评估函数的准确性。 在拓展的层中，区别为Min层和Max层。 电脑走棋的层我们称为 MAX层，这一层电脑要保证自己利益最大化，那么就需要选分最高的节点。玩家走棋的层我们称为MIN层，这一层玩家要保证自己的利益最大化，那么就会选分最低的节点。下面是wiki上Minimax算法的一张图 回溯时，节点将对本节点和上一级节点的值进行比较，若本节点为上一级的第一节点，则将上一节点的分数与本节点同步，否则将比较两者分数的大小，在Max节点，则将取两者中的最大值，同理，Min选取最小值。若本节点是上一节点选择的最后一个，则在比较后对上一级节点回溯。 最后是wiki上的Minimax算法的伪代码，我的Minimax函数基本上是基于对该伪代码的实现 function minimax( node, depth, maximizingPlayer ) is if depth = 0 or node is a terminal node then return the heuristic value of node if maximizingPlayer then value := −∞ for each child of node do value := max( value, minimax( child, depth − 1, FALSE ) ) return value else (* minimizing player *) value := +∞ for each child of node do value := min( value, minimax( child, depth − 1, TRUE ) ) return value 在我的代码中 节点对应结构 struct Node_Tree{ int flag,cnt,depth,result=0,number=0,Alpha=-100000000,Beta=+100000000; int VmBoard[16][16]; struct Node_Tree* son[216]; COORD site[216]; Node_Tree *Last; };fiag储存棋子，cnt储存下一层节点的探索的索引，depth储存深度，resulte储存节点棋盘是否已有胜负，number储存下一层总节点数量，Alpha和Beta储存当前节点的最大最小值用以剪枝，VmBoard[16][16]储存模拟棋盘，struct Node_Tree* son[216]储存下一节点的指针，COORD site[216]储存下一层节点的落子点，Node_Tree *Last指向上一节点。 创建根节点 Node_Tree* createroot();创建树的根节点，通过启发式评估函数选择下一层的点位，储存回溯得到的最大值和位置 创建叶节点 Node_Tree* createleaf();和创建根节点类似 节点的延申 Node_Tree* createlist();当当前的depth=5,必须满足这个条件才能使连五成为可能 其次对不同的empty，block，count进行分类讨论，具体实现可见代码ScoreGet()函数 由于不在进行复杂的匹配运算，只通过几个数值便可判断分数，虽然可能相比没有那么准确，但启发式评估函数毕竟需要计算的是全部节点，而Allscore()函数才是最终打分的关键，所以在尽量精确的情况下提高启发式搜索函数的速度才是首要的，经过重构，在广度为6，深度为8的情况下，运行时间依旧能保持小于5s 单元测试本AI经过很多次测试，对局。主要对手为前文提及的github里的作者和手机app五子棋大师，而后为解决广度不够的问题，我们使第一层的搜索广度为棋盘上分数非零的位点，后续的7层广度为4，以尽可能解决深度过低或广度不够的问题。测试中，若设置广度为定值则容易出现走很多活三，眠四等问题，而广度过大则会出现深度不够或计算时间过久，因此分层计算不同的广度暂时为一个折中解决办法,充当一种类似于算杀的模块，但依旧受制于程序本身的问题 |
【本文地址】