参考1：https://www.zhihu.com/question/27221568
参考2：https://blog.csdn.net/hzk_cpp/article/details/79275772
参考3：https://blog.csdn.net/BIT1120172185/article/details/80963609
极小极大搜索算法即minimax搜索算法
主要应用于零和博弈（非胜即负，如围棋，象棋，井子棋等），完全信息（玩家知道之前所有的步骤。象棋就是完全信息，因为玩家是交替着落子，且之前的步骤都能在棋盘上体现）
这个算法采用搜索算法递归实现，一层为先手，记为a, 一层为后手，记为b, 交替出现
对于最终局面，有一个分数（比如：先手胜分数为1， 平局分数为0，先手输分数为-1）
先手a想要让这个分数越大越好，后手b想要让这个分数越小越好，于是搜索到先手这一层，取最大返回，搜索到后手这一层，取最小返回
如下图：
于是伪代码为：
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; }
关于alpha-beta剪枝：
如果当前层为取最小，如果取最小后比上一层当前最大值还小，则不需要往下搜索，因为上一层根本不会选择当前节点往下搜，还有更好的选择
同理，如果当前层为取最大，如果取最大后比上一层当前最小值还大，则不需要往下搜索，因为上一层根本不会选择当前节点往下搜
具体推荐看最上面的知乎链接点赞最多的回答。
alpha-beta剪枝后的伪代码：
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;//返回最小值 } }
原文：https://www.cnblogs.com/widsom/p/10153159.html