内容发布更新时间 : 2025/6/22 4:20:08星期一 下面是文章的全部内容请认真阅读。
过程。这个 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