酝酿了近一年之久的GobangForward五子棋算法终于发布啦!这是一个与市场上五子棋算法有着不同思路的原创加强版算法,采用JavaScript语言描述。下面为大家简述一下其基本思想。
各位可以
点击这里打开程序演示页面,
点击这里下载GobangForward v1.0算法,其中混缩后的min版js文件可用于部署。
关于GobangForward类中的几个接口的使用方法,请各位自行参阅算法里的注释加以学习。本文重在讲解此算法的思路,故不再赘述。
对于五子棋的AI算法,其核心思路就是比较各点的优先等级。GobangForward算法将棋局分为了六个等级。
第一等级:无论何种情况,如果我方已形成了4连珠,且有一边未被堵截,那么下一步子一定会落在另一边形成5连珠取胜。
第二等级:如果敌方形成了上述的4连珠棋形,我方下一步只能落子在另一边进行堵截。
第三等级:如果我方已经形成了3连珠,并且不是两边都被堵截,则落子在其中的一边,形成4连珠。
第四等级:如果敌方形成了上述的3连珠棋形,我方择其一边进行堵截。
第五等级:此等级根据用户选择的游戏难度进行调节。在简单难度中,我们不进行防守;在中等难度中,我们对将要形成特殊棋形的点防守;在困难难度中,我们只对能够形成双重特殊棋形的点防守。
第六等级:当上述棋形均不成立时,我们使用“半径法循环”来遍历棋盘,找出一个利于进攻的点。关于“半径法循环”的细节,请诸位参阅上一篇文章。
当客户调用getStep方法,请求返回一个AI算法得出的点坐标时,程序会根据步数,如果在3步以内,则进行布局,为了更好的走出对自己有利的局势;否则,依次进行上述等级的判断。如果在当前等级下找到了满足条件的点,则将此点返回给客户,否则就将任务移交到下一等级,以此类推。这就是算法的基本思想。
但是,有很多的情况是,在当前等级下,许多点都满足条件,那么如何选择一个最适合的呢?这个问题的基本思路如下。
依次遍历符合条件的点,看看哪个点可以直接形成死棋(如:两边无子拦截的四连珠)。如果没有,则判断能否形成利于攻击的双重特殊棋形(如:“三三”、“四四”,因为无禁手)。再判读哪个点可以达到连攻带防的效果。然后判断有没有点能够形成第一等级或第三等级中的棋形。接着我们再根据这些点落子后,在三个方向上,能形成一条线的同色棋子总数来筛选。为什么是三个方向呢?因为去除了当前点在被发现的方向,否则会造成结果不准确。这个细节在后面的底层算法中有介绍。最后,我们再根据这些点距棋盘中心的距离来确定出一点来。一般认为,距离棋盘中心越近,越容易形成对自己进攻与防守均有利的局面。假如几个点距棋盘中心的距离是一样的,那我们只能随机选择其中一个点了。
上述即为本算法的核心思路,接下来,需要解决算法底层的问题。也就是,给出一个点,如何判断这个点在四个方向的子力情况。
这个底层算法,就是matchChess方法。它通过遍历给定点的前后四个方向,返回一个由四个元素组成的一维数组,分别代表在水平,竖直,左斜和右斜四个方向上发现的子力。除此之外,它还可以自动匹配一些特定的棋形(matchPattern方法),来生成几个临近点的棋形等级,并将特殊棋形在四个方向发现的个数压入patterns数组中。
关于“子力”的描述,是采用x.y的形式。若用“3.1”表示计算某点后的结果,且此点处是黑棋,则其意为,有3个黑棋连成在一条线上,且在线上的一边有一个白棋。那么,“3.0”就表示没有白棋。“3.2”表示两边均有白棋。
有了底层的算法后,一切棋形逻辑问题,都基于此形式的描述来判断,继而确立了文章开始的一整套逻辑思路。
由于文章所限,不能将算法字里行间之意,完整的进行描述。请各位借助注释进行阅读吧!
最后,由于水平不足,算法中或许还存有一些小的逻辑错误。本文的下载链接将提供算法最新版的下载,欢迎关注!