文档介绍：五子棋算法
五子棋算法
问题描述:人们通常喜爱的五子棋。某方将结果连成五子即获胜。
问题规模:15x15棋盘。
算法:博弈树,极大极小算法+Alpha-Beta剪枝
法棋。
数据结构描述如下。
棋盘类:
棋盘为一个M*N的矩阵Tbl[M][N](定义LEDGE为左边界,REDGE为右边界,TEDGE为上边界,BEDGE为下边界)。
每个棋盘矩阵有两个评估矩阵CpuPri[M][N][4]和UserPri[M][N][4],矩阵的第三维分别记录了该点([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分为进攻和防守两种方式。Tag>1时进攻,tag<1时防守。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