Simple-AI-for-Gomoku

A simple demo to write a AI for Gomoku

五子棋AI

这个项目参考了网上的五子棋源码,并且做出了自己的修改与一定的优化。

基本思路:首先我们知道棋类AI的基本框架就是博弈树,使用最大最小搜索算法和alpha/beta剪枝。这是基本的框架。然后因为存在的解太多,所以我们需要考虑一个评估函数来进行选择。

[1]评估:

这里主要采用状态分析的办法来进行打分。我们首先统计所有的棋形状态(冲二,冲三,活三等等),然后根据双方的状态来打分:

具体来说,就是轮到我方下的时候我们有一个双三,对方没有四颗子，那么我方一定赢,这时候就打出很高的分数,反之就会得到很低的分数。把所有必赢或者必输的情况统计出来可以直接返回,除此之外,我们就需要给相应的状态打分了,注意也要给对方打分,最后两者的分数相减即可。

[2]搜索:

搜索部分采用博弈树进行搜索,这一部分可以进行alpha/beta剪枝，即如果在最大最小搜索过程中,下一层的某一个值大于当前的最大值alpha,那么可以终止当前的搜索,因为继续搜索的值一定会更小，不可能可以更新alpha.除此之外,我进行如下的优化:

首先如果返回的某一个分数是必赢的(大于阈值),而且是第一层搜索,那么就可以直接终止搜索。

其次如果某一层的评估结果是必输或者必赢的值,那么也应该立刻返回结果到上一层,这是因为即便搜索到更好的结果意义也不大。

[3]选择:

在搜索过程中,搜索深度和宽度是一个很难同时处理的问题,深度太浅会导致看的不够远,太深导致节点数目过大。而宽度太短会导致漏掉一些可能的状态。所以这里采取了类似A*算法的一个优化思想,可以大大增强找到较优解的效率。

首先我们可以选择预计算,即找到可能比较优秀的落子点,然后过滤掉不够好的落子点,这样就避免了开局就去尝试最角落的走法(尽管这样最后也不会选择,但是会浪费大量的时间).那么怎么评估呢?我们直接使用我们上面的评估函数即可。这样预先生成下一层的子节点,选择里面的较优解。由于我们提前计算了这些节点的值,那么我们就可以把这些节点的值当作参数传递下去,避免重复评估。

其次我们需要给这些节点排序,这样有助于提前找到优秀的解,也提高alpha/beta剪枝的效率。这是A*算法的基本思想,无需多言。

[4]预选择

现在要考虑如何进行评估?如果把所有空位置都评估一次的话,还是比较缓慢,所以我们可以考虑再进行一次预处理！首先可以预测到较好的解法有较大的概率居于棋子密集的地方。要不就进攻,要不就防守。所以我们选择评估的位置也应该尽可能的往这些点靠。其次复杂度不能高,否则就失去减小计算量的意义。而且这里是一定要把所有空的点都走一次的。防止漏掉。

综上所述,我们可以选择使用图遍历的方式来解决问题,我们对图的每一个非空位置进行dfs,找到属于它的连通分量,然后开始计算所有的与这个连通分量相邻的空节点。如果连同分量中的一个子是当前执棋的棋子,那么就增加一点,否则就是对方的棋子,就增加0.5,为什么对方d棋子也增加?这是因为还要考虑防守的状态，我们有可能需要往对方的密集处下棋。最后统计每一个空节点被遍历到的次数,乘上分数再乘上一个系数再加1,1代表相邻的次数就得到预估计的权值,主要是集中在密集的点。这里的估计很粗略,因为主要的评估还是靠后门的评估函数。一次遍历的复杂度也不过是O(n)而已。

[5]优化效率:

通过cprofile可以发现主要效率瓶颈在于评估函数,因为每生成一个节点都要评估一次。所以评估函数被调用的次数非常多。考虑我们评估的方式是传入一个棋局就评估一次。这样即使只改变一个子也要重新评估,效率很低。所以需要加快速度。

这一部分可以考虑这样做：注意到只有新的那个节点会改变一些状态,所以我们可以考虑只评估和那个节点有交集的四条直线,然后评估这四条直线的产生的棋形。将这些棋形覆盖原来的这些直线上的棋形。最后再评估一下即可。但是注意我们还需要实现撤销一个节点的状态,因为生成子节点时候的选择过程是类似于BFS的,在这里我们只需记录上一个增加的节点,然后把它置为0，评估和这个空节点有关的四条直线产生的状态即可然后覆盖原来的状态即可。经过这样的优化,效率直接提高了10倍(经过测试从1.3s变成0.82s).

[6]实现中遇到的问题:

这里有一些问题要说明一下：

首先关于博弈树的实现过程并没有采取打正负分的机制,而是每一层都寻找最大的分数，但是在返回上一层的时候要加上一个负号,这种实现相对比较优雅。同时再传入alpha/beta参数的时候也需要加一个负号。这里很容易弄错导致搜索的结果一直不对。

其次关于直线的提取,我利用四个函数进行提取直线的功能,这样就可以把分析的过程全部抽象为对一条直线进行分析。当然在提取直线的时候要计算边界什么的,这里也要小心计算,不小心弄错了也会导致不明显的bug。

关于棋形的分析,这一部分相对比较核心,也比较容易错。首先可以做几个简单的判断。如果传入直线在当前位置是一个空子,立刻返回。如果不是空的子,从当前位置开始向两边搜索边界,分别找到还能下子的边界和连续的边界（这里的搜索很简单,但是也要注意出错很难找bug）,如果能下子的部分少于5个,立刻返回。否则可以开始进行分析了。首先判断连续的子有几个,如果是一个不用分析(注意可能有0 000)这样的情况,但是我们可以在后面的连续部分进行判断),如果多余1个还不到5个，就需要判断多种可能的棋形。这里举一例:有两个连续的棋子,那么可能的情况有(0 00),(00 00),( 00 ),(x00x),(x 00 ),(x00   x),（x00 0）等这些情况，当然我们不需要全部分析,我们只需要看这个连续的两个子能变成几个子,如果可以,是变成活三还是冲三？或者这个连续的两子其实是一个冲四。其他的分析同理。当我们找到一个棋形之后,就要将这个棋形记录下来。并且将其他组成这个棋形的子记录为已分析过。 这里一定要做到不重不漏,很容易就重复计算棋形或者漏掉一些棋形了。

关于状态的统计,这一部分需要我们维护一个数组即可,f[i][j][k]代表第i行第j列第k各方向产生的状态。统计状态到一个数组里面,这样就知道双方各有多少状态。最后就是对这些状态的分析,这里的分析部分非常繁琐,也容易出错,主要是组织好if语句的顺序,比如先判断是不是5个子,再判断我方有4子的情况下一定是胜利的。再后来就代表我方一定没有四子,那么如果有双三二对方没有我们也胜利,按照这样写很多判断语句即可。

关于界面：因为一个漂亮的界面不是我的目标，所以只用了字符串来显示,同时利用了json来维护我们的历史记录,方便撤销。

关于测试:测试主要就是看看几个基本的模块有没有问题,以及使用了一个两个AI同时对战来测试优化的结果和搜索能力。

[TODO]:

继续优化的方向:

现在存在的效率瓶颈主要在于统计状态,每一次修改一个点改变的状态以后就要全部统计一次,这样每一个节点都对应所有棋子总数的操作,这里可以这样优化。

假如我们分析一条直线的状态时,可以取出原来的状态,并在对应的统计状态里面减少1,然后将新的状态加1。这样避免了统计状态这件事,这样做看起来简单,但是我实现的时候出现了一些bug,弄了2个小时没有解决,所以留待以后优化吧,思路上是可行的。

分析直线导致了另一个性能的瓶颈,这里主要由两块构成,提取直线和分析直线。提取直线部分主要在于要拷贝一份直线,这里可以考虑如果是水平的直线可以直接返回一行即可。不需要重新拷贝。其他方向似乎无法避免。

我们其实还可以优化一个地方,但是可能会造成搜索能力的下降。注意到我们每拿到一个节点,就生成了下一层子节点,但是如果我们在当前的搜索中找到了最优解,那么新生成的子节点就浪费了。如果我们考虑用一个节点生成一个,又会导致无法较好的给子节点打分排序,这样会影响剪枝的性能。我认为中间可能存在一个平衡点使得不损失太多搜索能力的情况下提高性能。即一次生成部分子节点并利用堆维护起来,每次出去一个子节点,若堆的大小小于固定阈值,就生成新的子节点,这可以用迭代器实现。这样维护的一个最大堆可以保证至少出来的节点是k个里面最大的。

最后考虑使用神经网络来训练打分的权值,因为这里面的权值除了必赢的局面以外就是凭感觉给出的依据,所以考虑通过学习来确定合理的阈值。