内容发布更新时间 : 2024/5/19 8:31:25星期一 下面是文章的全部内容请认真阅读。

认

BOOL m_fail; 发出认输请求

BOOL m_failconfirm; 发出认输确认回复 BOOL m_dogfail; 发出和棋请求

BOOL m_dogfailconfirm; 发出和棋确认回复 int m_turn; 当前轮到哪方下棋了 int m_x; 对方下的棋子的横坐标 int m_y; 对方下的棋子的纵坐标

2.消息类的成员函数：

? void Init()初始化函数

在该函数中将全部的值置为不可用状态。

? virtual void Serialize(CArchive& ar)------序列化函数

Cobject类拥有序列化虚函数，消息类派生自该类，根据C++继承性质子类就可以重写该函数。从传递进来的Carchive 的类型进入相应的函数部分。当它是load类型时将数据写入ar中也就是相当于接收到了对方发过来的消息；当它是store类型时该函数就将值读入ar中，实现了向对方发送数据的功能。

2.4.3.3 Ccomputer-----电脑类

1. 消息类的数据成员：

int m_step; 表示当前电脑走了几步 int m_grade; 表示电脑的等级

int x,y; 电脑给出的最佳位置 2. 消息类的成员函数：

? OptimizeLayChess_MaxMin4(chessboard[][LW],de

pth,*px,py,Alpha, Beta);

OptimizeLayChess_MaxMin_2_1(chessboard[][L

W],depth,*px,*py, Alpha, Beta);

LayChess_MaxMin2(chessboard[][LW], depth,

*px,i*py, Alpha, Beta);

以上三个函数分别对应电脑中的高级，中级，初级智能。

第一个采用了动态优化功能深度为4；第二用也采用了动态优化，深度为3；第三个只用了剪枝。关于他们详细的介绍参看算法分析部分。

? Repair(chessboard[][LW],*px,*py);

由于AI算法中本身存在的问题(详细见4.2节 不足说明),所以需要进行必要的修补.这个函数遵循的原则是:己五必填,活四看对方,若对方不可能形成连五,同样必填.不是活四也不是死四的话,若对方可形成连五,必堵!

? Int Count_135(chessboard[][LW],i*p_135,*p_315,

i,j,who); int Count_90(chessboard[][LW],i*p_90,

*p_270, i, j, who);

int Count_45(chessboard[][LW], *p_45, *p_225, i, j, who);

16 int Count_0(chessboard[][LW],*p_0,*p_180, i,j, who);

这组函数是用于计算i,j点的各个方向上连续的who类型的棋子数,并且将每个方向上的被”阻碍”的类型. ? GetScorce(int total,int edge1,int edge2);

Get_0_Scorce(chessboard[][LW],Eva_Tab

ScoTab,i,j);

Get_45_Scorce(chessboard[][LW],Eva_TabScoTab

,i,;

Get_90_Scorce(chessboard[][LW], ScoTab, i, j); Get_135_Scorce(chessboard[][LW], ScoTab, i,ij); evaluate(int chessboard[][LW]);

这几个函数是分别用于计算，一个棋子在四个方向上的值。就是对应水平上，45度，90度，135度调用GetScorce计算。

2.5 人机对战中AI算法

人工智能(Artificial Intelligence) ，英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式作出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

在该部分我们尽量去模拟人类在下棋中思考的方式，找出一种合乎逻辑的规则。

根据我们平常下棋的经验，当放入一个棋子时总是尽量的往利于己方的位置也既是“攻”；同时要提防对方使其不能得逞也既是“防”；我们可以用计算机模拟这个过程。假设我们在棋盘中放入一个己方棋子，然后考虑对方最可能下的棋子位置，也就是最有利于对方的点。（我们假设只进行两次的探索），再逐个的比较每个可下棋的点，最后得出最有利于我方的点。这就是本个系统中所采用的一个思路。对于人说用手工去比较计算是不现实的。当考虑的深度加深的话甚至无法在有效的时间内实现的。我们正是利用计算机快速的计算机能力进行这样的笨重检索，就能够在很短的时间内计算完。下面对AI算法中所涉及的几个重要概念作下介绍。

2.5.1 极大极小树

目前绝大部分的博弈类游戏中的人工算法都采用这种方法。假设己方为MAX点，对方则为MIN点。如果当层的节点为奇数时那么就为MAX层，同样为偶数时就为MIN层。当在MAX层时，该层的值就应该为下一个MIN层中的最大一个的值。当在MIN层是，该层的值就应该为它子层MAX的最小的一个。通俗的说就是当轮到我方时，我们就应该选择一个最有利于我们的点，预测对方可能下的最有利他方的点（相对我方来说就是最坏的点）。这样反复计算下去就能够得到根节点的最大值，这个点也就是我们最佳下棋点。在计算这个点时

17 可以很明显的看出这是一个不断递归的过程，到达叶子节点时根据相关的计算规则算出该值然后向上一层不断的返回。下图中矩形代表极大层，椭圆代表极小层。

图 2.7 极大极小树

2.5.2 深度优先搜索（DFS）

在图论中有两个很重要的遍历的方法，一个是深度优先搜索（DFS）,另外一个是广度优先搜索(BFS).这两个方法的主要区别在于下一个节点的选择。DFS首先选择它的连接节点，若它的下个节点已经全部被遍历过或者不存在的话。则向上返回到上一个节点，在遍其他的未被访问过的点。很容易想到这要用到堆栈结构，使用一个递归来实现。而BFS则是逐个的遍历它的联接接点，将已经访问过的点放入队列中。然后再依次取出继续这个过程。

图2.8

DFS遍历过程如下：

首先从A点出发访问它的领接点B，因为B的领接点C,F均未被访问过，所以B点选择C（当然也可以选择F点）作为下一个要访问的点，C点的领接点是D,F选择下个节点D，而D的邻接点只有一个E且未被访问过，就将E作为了它下个节点。这时因为E已经没有可访问的邻点，所以向上一层返回到D，发现D也已经没有可访问的点了，继续向上层返回到C，由于C的邻节点F未被访问过，那么就访问F。所以整个过程的遍历结果为：A-->B?C?D?E?F。

BFS的的遍历过程为：A?B?E?C?F?D。

2.5.3 剪枝方法

在上面中提到当预测的深度达到3的时候，最坏情况下225*225*225=个，这在目前的一些常规平均的机器性能下也需要40多秒的时间，这是不能够容忍的。那么是否有很好的改进技术，去除哪些不必要的节点，并且在剪去了这些点后不影响结果呢？答案是肯定的，这种方法就是Alpha---Beta剪枝。

下面通过图来说明，矩形代表极大层，椭圆代表极小层。

图 2.9 Alpha—Beta剪枝

从上图可以看出，由于C节点的值肯定不大于30而B节点的值为40大于C节点，那么目前为止可以很肯定的说A节点值一定不小于40。 所以C点的其他子节点无须去访问也不会对结果的值有影响。这个就是α剪枝。

在I节点的值确定为25后，我们就可以断定H节点一定不小于25,而F点的值为20，那么就可以很确定的说D的值为20。这个就是β剪枝。

下面给出完整的定义：

α剪枝:若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值 ,即α(先辈层)≥β(后继层) ,则可终止该最小值层中这个 Min 节点的搜索过程。这个 Min 节点最终的倒推值就确定为β值。

β剪枝:若任一极小值层节点的α值大于或等于它任一先辈极大值层节点的β值 ,即α(后继层)≥β(先辈层) ,则可终止该最大值层中这个 Max 节点的搜索过程。这个 Max节点最终的倒推值就确定为α值。

2.5.4 静态估值函数

当极大极小树到达叶子节点时，需要估算一下当前盘面的值。这个就根据

18 某个计算规则计算也即是估值函数。因为这个值是已经确定的所以称为静态。

? 当只有一个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”

就给他50，否则给予10。

? 当两个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”给予

1000，若存在一方有“阻碍物”则给以100，否则给予10。

? 当是活三的时候给予3600，当存在一边被堵时，就给予500。否则给予

10。

? 当是活四的时候给以500000，当一边被堵时，给予50000。否则给予

10

? 当是五连子的时候就给予最高分。

? 最后判断是否是己方的，若不是则给予负号。

静态估值函数会很严重的影响到算法的智能，所以可根据在下棋的过程中不断的做出调整，使其更加的合理。根据一些测试，这组静态估值函数能够很好的反映棋盘重要性指标。

2.5.5 AI算法的分析和改进

2.5.5.1 算法分析

下面对该次设计中的主要代码进行做个分析：

1) 该函数进行了深度为3的预测，没有使用剪枝方法。

LayChess_MaxMin(chessboard[][LW],int depth,int *px,int *py) {

if(depth<=0)return evaluate(chessboard);当到达叶子节点时调用

估值函数计算

int best,temp=0;

if(depth%2==1) 初始化best值 best=MIN; else

best=MAX;

for(int i=0;i

for(int j=0;j

if(chessboard[i][j]==0) 若该点是空的就进行判断

if(depth%2==1) 判断该层是哪种类型 {

chessboard[i][j]=2; 该点赋予己方的子 temp=LayChess_MaxMin(chessboard,

depth-1,px,py);进行下一层递归判断

if(temp>=best) 若该点更优则记录 {

best=temp;

if(depth==DEPTH) 判断是否是根节点

19

{

*px=i; 记录最优点的坐标 *py=j;

} }

chessboard[i][j]=0; 恢复该点先前状态 } else {

chessboard[i][j]=1;

temp=LayChess_MaxMin(chessboard,depth-1,px,p

y);

if(temp<=best) best=temp; chessboard[i][j]=0; } } }

return best; }

2) 以上由于没有采用剪枝技术，搜索深度为3时间已经达到130秒。所以要用上面提到的Alpha—Beta进行剪枝优化，代码如下：

int CComputer::LayChess_MaxMin1(int chessboard[][LW],int depth,int *px,int *py,int Alpha,int Beta) {

if(depth<=0)return evaluate(chessboard); int temp=0;

for(int i=0;i

for(int j=0;j

if(chessboard[i][j]==0) if(depth%2==1) {

chessboard[i][j]=2;

temp=LayChess_MaxMin1(chessboard,

depth-1,px,py,Alpha,Beta);

chessboard[i][j]=0;

if(temp>Alpha) 确定最大的Alpha值 {

Alpha=temp;

if(depth==DEPTH)

20