极大极小搜索，即minimax搜索算法，专门用来做博弈论的问题的暴力.
多被称为对抗搜索算法.
这个搜索算法的基本思想就是分两层，一层是先手，记为a，还有一层是后手，记为b.
这个搜索是认为这a与b的利益关系是对立的，即假设a要是分数更大，b就要是分数更小.
而且这两个人都是用最优策略.
对，就是这样.
假设我们现在有一道题，给出一串数列，有两个选手按顺序选数，也就是一个选手选了ai，接下来另一个选手就必须选ai后面的任意一个数，然后每个选手选的数的累加和即为选手的分数，求先手比后手最多多几分.（两个选手都会选择最优策略）
保证序列里所有的数为正数.
那么我们可以设计一个算法：
先手的框架为：枚举上一次另一个选手选的数字后面开始选，取最大值.
后手的框架为：枚举上一次另一个选手选的数字后面开始选，取最小值.
即：
1 int dfsb(int k){ 2 ??int minn=1000000000; 3 ??for (int i=k;i<=n;i++) ?????//枚举接下来的要取的数 ?4 ????minn=min(minn,dfsa(i+1)-a[i]); ?????//搜索接下来对b最优的结果，也就是分数最小 ?5 ??minn=min(minn,0); ?????//考虑不取的情况 ?6 ??return minn; ?????//返回最优策略的得分 ?7 } 8 int dfsa(int k){ 9 ??int maxx=-1000000000;10 ??for (int i=k;i<=n;i++) ?????//枚举接下来的要取的数11 ????maxx=max(maxx,a[i]+dfsb(i+1)); ?????//搜索接下来对a最优的结果，也就是分数最大 12 ??maxx=max(maxx,0); ?????//考虑不取的情况 13 ??return maxx; ?????//返回最优策略的得分 14 }接下来是一个对于对抗搜索的最佳搭档——alpha-beta优化.
这个优化的思想很简单，即对于a来说，需要的是最大值，而下面的b取得是最小值.
而接下来如果b的已求出的最小值比a的已求出的最大值小，还有必要继续搜吗？
同样的，对于b来说，需要的是最小值，而下面的b取得是最大值.
于是这就是alpha-beta剪枝.
具体实现如下：
1 int dfsb(int k,int maxx){ ?????//多传一个maxx值表示上一层已经求出的最大值 ?2 ??int minn=1000000000; 3 ??for (int i=k;i<=n;i++) { ?????//枚举接下来的要取的数 ?4 ????minn=min(minn,dfsa(i+1,minn)-a[i]); ?????//搜索接下来对b最优的结果，也就是分数最小 ?5 ????if (minn<maxx) return; ?????//alpha-beta优化 ?6 ??} 7 ??minn=min(minn,0); ?????//考虑不取的情况 ?8 ??return minn; ?????//返回最优策略的得分 ?9 }10 int dfsa(int k,int minn){ ?????//多传一个minn值表示上一层已经求出的最小值 11 ??int maxx=-1000000000;12 ??for (int i=k;i<=n;i++) { ?????//枚举接下来的要取的数13 ????maxx=max(maxx,a[i]+dfsb(i+1,maxx)); ?????//搜索接下来对a最优的结果，也就是分数最大 14 ????if (maxx>minn) return; ?????//alpha-beta优化 15 ??}16 ??maxx=max(maxx,0); ?????//考虑不取的情况 17 ??return maxx; ?????//返回最优策略的得分 18 }极大极小搜索思想+（α/β）减枝 ?【转自-----https://blog.csdn.net/hzk_cpp/article/details/79275772】
原文地址：https://www.cnblogs.com/xidian-mao/p/9304119.html