五子棋算法.doc

五子棋算法 五子棋算法问题描述：人们通常喜爱的五子棋。某方将结果连成五子即获胜。问题规模：15x15棋盘。算法：博弈树，极大极小算法+Alpha-Beta剪枝法棋。数据结构描述如下。棋盘类：棋盘为一个M*N的矩阵TblMN（定义LEDGE为左边界，REDGE为右边界，TEDGE为上边界，BEDGE为下边界）。每个棋盘矩阵有两个评估矩阵CpuPriMN4和UserPriMN4，矩阵的第三维分别记录了该点（0水平、1垂直、2左上右下、3左下-右上）的棋子数。若该点上棋子为USER下的，则UserPri中有值，CpuPri中值为0，反之亦然。该点无子时，两个评估矩阵上该点评估值均为0.CpuSum：CpuPri矩阵的所有元素之和。UserSum：UserPri矩阵的所有元素之和。tag：tag=CpuSum/UserSum，CPU战术选择标记。当tag大于1时CPU进攻，小于1时CPU防守。Depth：深度。标记该棋盘位于博弈图的层次。Father：该棋盘的前驱。Child：该棋盘的孩子棋盘链。nextBro：兄弟节点。Node：一个点类，标记该棋盘下子的点。算法描述如下。一、由于存在对抗性，CPU分为进攻和防守两种方式。Tag1时进攻，tag1时防守。Tag的实际含义是对敌我的一个评估，当我方比敌方有利时选择进攻，当敌方比我方有利时选择防守。二、对任意一棋盘生成博弈图的算法。算法2-1当CPU接到一张已落子n个的棋盘时：1、计算此棋盘的CpuSum值和UserSum值，并得出tag值决定进攻还是防守。此标志在本次生成整个博弈树时都不变，也就是决定了进攻或防守后，选择时都依据此标志。2、以CPU身份在棋盘的每个未落子的点上分别下一步棋，生成M*N-n个已落子n+1个的棋盘，分别计算评估值，并生成博弈树第一层；3、再以USER身份在每个棋盘（已落子n+1个）每个未落子的点上再下一步棋生成M*N-n-1个棋盘，分别计算评估值并加入博弈树第二层。4、回到步骤2，依次类推，CPU的身份不断在CPU和USER之间变化，直到生成树的深度大于给定深度MAX_DEP时为止，停止建图。5、此时，将叶子节点的CpuSum和UserSum计算出来。6、若决定进攻，则极大极小过程如下：1）若某步为CPU走（depth值为偶数），则应当选择CpuSum最大的一个棋盘，即CPU选择了对CPU最有利的一步。（极大过程）2）若某步为USER走（depth值为奇数），则应当选择CpuSum最小的一个棋盘（即相当于此时用户防守），此时相当于USER选择了对CPU最不利的一步。（极小过程）7、若决定防守，则极大极小过程如下：1）若某步为CPU走（depth值为偶数），则应当选择UserSum最小的一个棋盘，即CPU选择了对USER最不利的一步。（极大过程）2）若某步为USER走（depth值为奇数），则应当选择UserSum最大的一个棋盘（即相当于此时用户进攻），此时相当于USER选择了对USER最有利的一步。（极小过程）8、按照6、7的选择算法，从下至上，得到第1层的（M*N-n）个棋盘的CpuSum值和UserSum值。注：向上传递时，同时传递CpuSum和UserSum值，不论如何挑选。但棋盘并不向上传递。9、在第0层决定如何走下一步，方法同6（1）或7（1），取决于CPU是防守还是进攻。此时将最适合的棋局的棋盘（位于博弈树第1层）返回，即完成了原棋局下一步的选择过程。10、删除该图，算法结束。三、剪枝一个已经落子n的棋盘按照上面的算法向前预测k步会产生(M*N-n)!/(M*N-n-k)!)个棋盘。例如，最大生成深度为3时，若一个15x15的棋盘已经由用户走了1步，那么CPU在预测下一步时会产生224*223*222=11089344个棋盘。若每个棋盘大小为8k（15*15+15*15*2*2=2025个int），则空间大小为86635.5MB=86.6GB，同时会有极大的耗时，这是用户无法接受的。 由于向前预测时会进行大量计算，同时产生巨大的数据，所以必须进行剪枝。 首先使用书上给出的Alpha-Beta剪枝计算，取得了一定的效果，但仍有很大的空间消耗。为了追求更高的速度，经过自己分析，采用了一个变形的Alpha-Beta剪枝法。剪枝算法如下：算法3-1在生成一个棋盘的子棋盘前，将该图的CpuSum值和UserSum值计算出来，用2-1-6和2-1-7类似的判别方法，（此处以CPU进攻为例），当其子棋盘CpuSum值小于该棋盘的CpuSum值时则舍弃不加入博弈树，否则加入博弈树。其他情况同理。算法分析：该剪枝算法不能保证得到最优解（类贪心算法），但有更快的速度和更小的空间占用，而且也在短时间内有更大概率搜到Threat-Space。其弱点在于容易被对手用一定的战术蒙骗。实验证明，下棋时几