人工智能 | alpha-beta剪枝算法

发布时间：2019-01-15 20:59,

浏览次数：683

, 标签：

alpha

beta

<>教材

极小极大搜索算法

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