五子棋人机对弈的算法

（程序下载：http://www.wowtc.com/bbs/read.php?tid=204030&keyword=　）

摘要  算法事实上就是N条规则, 每条规则就是对原始数据的一次筛选, 即一次链表删除操作, 经过N条规则的N次操作, 最后留下的数据(一个坐标串)就是最好的下棋位置.

0  简介
    本算法与使用语言无关, 但从手机移植角度考虑故本算法使用的是C语言, 便于移植, 同时具有算法简单, 效率高, 可扩展性强,等特点.

1  算法分析
五子棋的规则非常简单，每人一对一子下，五子横竖斜有连续五子为胜。
如何让计算机学会下五子棋, 首先要将此问题转化为一个计算模型, 事实上从计算机角度考虑, 原理图如图1五子棋算法的原理图所示：
让计算机下棋事实上就是一个输入输出的系统结构, 根据输入数据, 通过计算输出结果的过程.

2 建立模型数据结构
首先, 应该将棋盘进行了数据化,
五子棋采用的一般是N*N的棋盘，为了计算简单取了20。
采用的一个20*20的2维数组：MATRIX来存储数据
为了方便我建的数组就是MATRIX[21][21]，直接使用从MATRIX[1][1]- MATRIX[20][20]表示每个格子。每个数据单元为一int数据，表示三种情况：
无子：0  白子：1  黑子：2
然后每次下一次, 根据下子方和下子位置, 将相应的MAXTRIX单元置1或者置2。

3  算法实现
为了保持MATRIX中的数据, 原始数据并不是MATRIX数据, 而是根据MATRIX新建一个链表, 首先是节点数据结构
Struct Point
{
 int state； /* 表示当前状态 state=0表示无子，1表示白子，2表示红子 */
 int x;  /* 该点的X轴坐标 */
 int y:   /* 该点的Y轴坐标 */
 int Kb;  /* 黑子该点的总权值 */
 int Kw;  /* 白子该点的总权值 */
 Point *next;
 /* 对其他规则所需要的数据在此补充 */
}；
然后是链表结构：
设P11（x1, y1）表示 Matrix[x1][y1]
START->P11->P12->P13->…->P2020->END
通过对原始数据进行简单处理，问题已经转化成对一个链表的操作，如果操作这个链表，可以用下图2表来表示：
所以本算法事实上就是N条规则, 每条规则就是对链表中的数据的一次筛选操作或者说链表删除操作, 经过N条规则的N次删除操作, 最后留下的数据(链表中的最后几个节点)就是最好的下棋位置.
用程序来表示如下：
void Caculate()
{
 RuleNumber1();  /* 规则一 */
 RuleNumber2();  /* 规则二 */
 RuleNumber3();  /* 规则三 */
 ……
 RuleNumberN();  /* 最后一条规则N */
}
本算法采用到的规则:
规则一: 如果当前格有子, 则不考虑, 只要用个简单一个IF就行了
设当前指针为pt, 则只需要做一个循环，循环体内，做如下操作：
While(!EOF)
{
 if(pt->state) deletepoint;
 pt = pt->next;
}

规则二: 如果当前格的根据当前位置的权值来删除节点
在判断每个点的价值的方法，本算法所采取的办法是用权值来确实最好的下子位置的方法。五子棋不管是横竖斜, 只要满五个子就可以了, 由于横竖斜(正斜, 反斜)四个方向独立的, 可以分别考虑, 即计算一个方向上的权值, 然后四个方向再相加.
对单一方向的权值计算方法，以横向右边为例对当前位置左右四子范围进行判断:
a) 默认权值为2
b) 无子 不靠边权值 +0
  靠边 权值 -1
c) 有子 己方子每一子权值 +1
       对方子有且只有一次加权 -1
以下图3为例来计算X的位置的黑方权值:

单一方向的权值计算共有四个, 由于他们之间是独立的, 但是该点的价值应该体现在最大权值的方向, 并且同样对于两个点, 同样最大权值的情况下, 又要考虑其他方向, 所以采用如下计算公式计算总权值:
K = a0*4^0+a1*4^1+a2*4^2+a3*4^3+a4*4^4+a5*4^5
利用此公式即可计算出的权值就可以基本上反映出当前位置的价值
以下图为例:
 
如所图4所示, 按权值K的算法, 可以得到X的位置是对黑棋最有价值的点, 其价值超过O所在的位置,

利用K的计算方法, 计算出每一点的Kw和Kb然后再确实下子, 假设下一步是黑棋走, 有如下规则:
a)计算权值最大的权是多少(kbmax, kwmax)
b)如果该点没有一个达到最大权的, 删除该节点

更多规则
为了增加计算机的水平, 还可以在算法中继续增加规则, 如对一下步的预测, 在几个比较合适的点中, 对对手的下一步进行, 预测对手下一步可能下的位置, 不管从精简算法角度, 还是从实际效果考虑, 都没有必要对所有位置考虑, 事实上只需要对对手最可能下的一两个位置, 然后对此位置后进行预测即可, 其他位置正常算法就可以, 不需要用推测下一步去年. 对于需要预测的位置, 再次计算新的棋局的权值, 设本步为KT1, 下一步为KT2(在节点的数据结构中增加此变量即可), 以此类推, 根据需要预测计算步数, 然后再根据KT1和KT2等的权值综合计算出最合适的点, 将会计算机下棋的水平更具有策略性.

规则N
  根据所有的计算结果所留下的最后几个节点，综合关系，选出最合适的点。

4  输出结果
 本程序计算机使用是红子，所以最后根据计算的最后输出结果将结果指向的坐标矩阵MATRIX置1，然后显示。等待下次对手下子。

5 其他一些问题:
5.1  判断胜负
   每下一次子都要判断一次, 从精简算法角度考虑, 只需要计算最后下子的位置即可. 计算最后下子的位置的横竖斜四个方向, 有满五子则给出相应处理, 无则继续.
5.2  算法的智能性, 对于算法中最可能会出现低级错误(比如说边角问题), 可以通过追加相应规则来解决.
5.3  算法的强壮性, 本算法没有过多循环, 没有跳转, 不会出现严重错误
5.4  算法效率,  本算法效率非常高, 即使在移植到手机上也会瞬间给出结果.

附图: