<>教材

极小极大搜索算法

alpha-beta剪枝算法


课后习题




<>PPT

提高博弈程序效率



(PS:极大极小值算大应该是深度优先算法)

alpha-beta剪枝算法


<>博客

极大极小算法例题







极大极小算法伪代码
int MaxMin(position,int d) { int bestvalue,value; if(game over) //检查游戏是否结束
return evaluation(p);// 游戏结束,返回估值 if(depth<=0) //检查是否是叶子节点 return evaluation(p);
//叶子节点,返回估值 if(max) //极大值点 bestvalue=-INFINTY; else //极小值点 bestvalue=INFINTY;
for(each possibly move m) { MakeMove(m); //走棋 value=MaxMin(p,d-1); UnMakeMove(m
); //恢复当前局面 if(max) bestvalue=max(value,bestvalue);//取最大值 else bestvalue=min(
value,bestvalue);//取最小值 } return bestvalue; } // end of MaxMin algorithm
alpha-beta剪枝算法例题










alpha-beta算法伪代码
//伪代码,Alpha剪枝和Beta剪枝+MaxMin搜索 int AlphaBeta(nPlay,nAlpha,nBeta) { if(game over)
return Eveluation; //胜负已分,返回估值 if(nPly==0) return Eveluation; //叶子节点返回估值 if(Is
Min Node) //判断 节点类型 { // 极小值节点 for(each possible move m) { make move m; //生成新节点
score=AlphaBeta(nPly-1,nAlpha,nBeta)//递归搜索子节点 unmake move m;//撤销搜索过的节点 if(score<
nBeta) { nBeta=score;//取极小值 if(nAlpha>=nBeta) return nAlpha;//alpha剪枝,抛弃后继节点 } }
return nBeta;//返回最小值 } else {//取极大值的节点 for(each possible move m) { make move m;
//生成新节点 score=AlphaBeta(nPly-1,nAlpha,nBeta)//递归搜索子节点 unmake move m;//撤销搜索过的节点
if(score>nAlpha) { nAlpha=score;//取极小值 if(nAlpha>=nBeta) return nBeta;
//nBeta剪枝,抛弃后继节点 } } return nAlpha;//返回最小值 } } //end of AlphaBeta pseudocode

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信