<>教材
极小极大搜索算法
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
热门工具 换一换