过程。这个 Max节点最终的倒推值就确定为α值。
2.5.4 静态估值函数
当极大极小树到达叶子节点时，需要估算一下当前盘面的值。这个就根据某个计算规则计算也即是估值函数。因为这个值是已经确定的所以称为静态。
? 当只有一个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”
就给他50，否则给予10。
? 当两个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”给予
1000，若存在一方有“阻碍物”则给以100，否则给予10。
? 当是活三的时候给予3600，当存在一边被堵时，就给予500。否则给予
10。
? 当是活四的时候给以500000，当一边被堵时，给予50000。否则给予
10
? 当是五连子的时候就给予最高分1000000。 ? 最后判断是否是己方的，若不是则给予负号。
静态估值函数会很严重的影响到算法的智能，所以可根据在下棋的过程中不断的做出调整，使其更加的合理。根据一些测试，这组静态估值函数能够很好的反映棋盘重要性指标。
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; //该点赋予己方的子 21 temp=LayChess_MaxMin(chessboard, depth-1,px,py);//进行下一层递归判断 if(temp>=best) //若该点更优则记录 { best=temp; if(depth==DEPTH) //判断是否是根节点 { *px=i; //记录最优点的坐标 *py=j; } } chessboard[i][j]=0; //恢复该点先前状态 } else { chessboard[i][j]=1; temp=LayChess_MaxMin(chessboard,depth-1,px,py); 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, 22 depth-1,px,py,Alpha,Beta); chessboard[i][j]=0; if(temp>Alpha) //确定最大的Alpha值 { Alpha=temp; if(depth==DEPTH) { *px=i; *py=j; } if(Beta<=Alpha) return Beta; //进行α剪枝 } } else { chessboard[i][j]=1; temp=LayChess_MaxMin1(chessboard, depth-1,px,py,Alpha,Beta); chessboard[i][j]=0; if(temp Beta=temp; if(Beta<=Alpha) //进行β剪枝 return Alpha; } } } } return depth%2==1 ? Alpha : Beta; } 该算法也进行3个深度的搜索，并且采用了剪枝，速度上得到了很到的提高，只用了30秒。当在某些点时提高的速度更高。取得了很大的进步，不过距离系统的可使用性，还是有差距的。所以我们继续得用方法去优化。 2.5.5.2 算法改进 影响算法时间有两个主要的方面，一个是搜索的深度，另外一个是搜索的宽度。现在只能从宽度上进行入手。 我们知道在开局的时候，棋盘的棋子很少，Alpha—Beta剪的枝的数目并不可观。这时我们想到由于开局的时候觉大部分都是先在棋盘中心区域。那么我们就可以动态的将搜索的范围由很小的区域向整个棋盘扩展。还有一点需要考虑的是我们尽量由有棋子的地方开始。这样就能提前的进行剪枝。这样会节省大量的时间。 当我采用动态改变的增量为increment3[]={2,3,3,4,4,5,5,6,6,7};时，简单的测 23 试了几个点，发现时间上大大的减缩了，已经感觉不到时间了，远小于1秒时间，取得了我们预期的效果。 后来又尝试了将搜索深度变为4时，动态变化的增量放缓惊讶发现大部分情况下，明显的感觉不到延缓但是某些点时间有点慢。同样简单得测试了一下，某些点大概都不超过15秒。属于正常容忍的范围。可以很容易的知道,当我们越早的获取到Alpha 和 Beta的值剪的枝就越多.基于这样的考虑,我们应该从下的棋子旁边开始搜索.这样就有可能达到我们要的效果.所以这里我们采用了由中心向外的方向去搜索. increment4[]={2,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,6,6,6,6,7}; 24 运行测试 下面对系统集成后进行了初步的测试。 3.1网络部分 分别运行两个程序实例，A当作客服端，B当作服务器。A连接B成功后提示如下图： 图2.10 A端提示和B端提示 图2.11联机对战 图2.12 发出悔棋请求 图 2.13对方同意 25