谈谈五子棋的人工智能算法

    电脑下子实际上是分两个步骤的，第一个步骤是尽可能的收集棋盘格局的信息，并且使这些信息以一定的格式存放再内存中，以便于第二步的处理。第二个步骤就是，对收集到的信息进行分析处理，即要给出一个规则，用穷举搜索的办法遍历所有收集到的信息，搜索的过程实际上是用所定下的规则去衡量每一点的权值，搜索的目的是为了找到一个权值最大的点，这个点就是当前的最优解，也就是应该下的子。

    具体的说来，在第一步中，可以用一个13×13的二维数组来存放棋盘上每一个点的信息。每下一步棋，就用一个13×13的二重循环去遍历棋盘上的每一个点，可以参照如下的方法，即对于每一个点，我们假定这个点放上黑子，这时候就判断这个黑子放上去后，会形成多少个活2、活3、活4和五，然后把对应的数值填入上面所说的二维数组里面，然后再假定这个点放白棋，又会形成多少个活2、活3、活4和五，也填入二维数组里面。当然你也可以用两个二维数组分别存储黑子和白子的情况，而且最好采用结构体数组。这样遍历完棋盘后，再数组里面就保存了有用的棋盘格局信息。如下：
typedef struct tagNodeInfo
{
    int numof2;
    int numof3;
    int numof4;
    int numof5;
}NodeInfo,*PNodeInfo;

NodeInfo WHITE_CHESS[13][13];
NodeInfo BLACK_CHESS[13][13];

    下面就是如何利用所得到的信息去下棋了。这个过程也是遍历分析所得的信息的过程。对上面的信息，我们可以很好的处理。比如，假定四三是必胜的，则我们给他的权值就很大比如100吧，而活二给的权值应该比较小，就给1吧。然后你可以得到一个权值的计算公式，比如
             权值＝活二的个数×1+活三的个数×5+活四的个数×10+四三的个数×100
    就是类似这样的公式，当然我上面是随便举的。

    下棋是就是遍历每一个点的信息，对每一个点计算权值，找到权值最大的就是要下的点了。上面说了用两个数组分别保存黑子和白子的信息也是有必要的，因为可以计算出某一点对黑白双方的重要程度。就是说如果轮到你下白子了，你光看哪一点对白子有利也不行呀，还要看那些点对黑子有利，并且要比较这种有利的程度。如果你放某一点能成活3，而别人放另一点就是四三了，你就要抢先吧那一点占了。

    当然这样的算法也仅仅是考虑了当前的最优解，如果要进一步提高人工智能，就要用更高级的搜索法，对未来的几步进行搜索了。一般都是将搜索空间组织成二叉树的结构。这个我学的也不是很好，所以就不讲了。

    实际上，上面讲的办法还具有一般意义，不光是可以用到五子棋，再其他的棋类里面也是这样的，先搜索信息，再分析。

    这个五子棋的程序不是我写的，是我们班上的温宗臣写的，代码很乱，我也不大能看懂，但具体的算法思想大概就是这样了，如果有空，我也想自己实现一个五子棋的算法。

（注：以上所说的五子棋源程序可以在我的网站上面下载，地址：http://rockcarry.126.com）

    

                                                                   作者：陈凯
                                                                   2005.1.3
                                                                   版权所有、不得转载

 

本文地址：http://com.8s8s.com/it/it23916.htm