参考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<=) //检查是否是叶子节点
return evaluation(p);//叶子节点，返回估值
if(max) //极大值点
bestvalue=-INFINTY;
else //极小值点
bestvalue=INFINTY;
for(each possibly move m)
{
MakeMove(m); //走棋
value=MaxMin(p,d-);
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==)
return Eveluation; //叶子节点返回估值
if(Is Min Node) //判断 节点类型
{ // 极小值节点
for(each possible move m)
{
make move m; //生成新节点
score=AlphaBeta(nPly-,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-,nAlpha,nBeta)//递归搜索子节点
unmake move m;//撤销搜索过的节点
if(score>nAlpha)
{
nAlpha=score;//取极小值
if(nAlpha>=nBeta)
return nBeta;//nBeta剪枝，抛弃后继节点
}
}
return nAlpha;//返回最小值
}
}
例题1：POJ - 1568
思路：井子棋下的步数小于等于4必平局
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
using namespace std;
#define fi first
#define se second
#define pi acos(-(long double)1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head char s[], mp[][];
int cnt = , ansx, ansy;
int check(char c) {
for (int i = ; i < ; i++) {
int a = ;
for (int j = ; j < ; j++) {
if(mp[i][j] == c) a++;
}
if(a == ) return ;
a = ;
for (int j = ; j < ; j++) {
if(mp[j][i] == c) a++;
}
if(a == ) return ;
}
int a = ;
for (int i = ; i < ; i++) if(mp[i][i] == c) a++;
if(a == ) return ;
a = ;
for (int i = ; i < ; i++) if(mp[i][-i] == c) a++;
if(a == ) return ;
return ;
}
int dfs(int step, int a, int b) {
if((cnt-step)% == ) {
int tmp = check('o');
if(tmp || step == ) return -tmp;
}
else {
int tmp = check('x');
if(tmp || step == ) return tmp;
}
if((cnt-step)% == ) {
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
if(mp[i][j] == '.') {
mp[i][j] = 'x';
int tmp = dfs(step-, a, b);
mp[i][j] = '.';
if(tmp >= a) {
if(step == cnt) {
ansx = i;
ansy = j;
}
a = tmp;
if(b <= a) return b;
}
}
}
}
return a;
}
else {
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
if(mp[i][j] == '.') {
mp[i][j] = 'o';
int tmp = dfs(step-, a, b);
mp[i][j] = '.';
if(tmp <= b) {
b = tmp;
if(a >= b) return a;
}
}
}
}
return b;
}
}
int main() {
while(~scanf("%s", s)) {
if(s[] == '$') return ;
for (int i = ; i < ; i++) scanf("%s", mp[i]);
cnt = ;
for (int i = ; i < ; i++) for (int j = ; j < ; j++) if(mp[i][j] == '.') cnt++;
if(cnt >= ) {
printf("#####\n");
continue;
}
int ans = dfs(cnt, -, );
if(ans == ) printf("(%d,%d)\n", ansx, ansy);
else printf("#####\n");
}
return ;
}
例题2：POJ - 1085
思路1：记忆化搜索dp, dp[s]表示从状态s出发先手所能获得的最大利益。
特点：空间大，时间短
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head int line[][] = {{, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }};
int tri[][] = {{, , }, {, , }, {, , }, {, , }, {, , }, {, , }, {, , }, {, , }, {, , }};
int num[][];
int dp[<<];
int count(int s) {
int cnt = ;
for (int i = ; i < ; i++) if((s&(<<tri[i][])) && (s&(<<tri[i][])) && (s&(<<tri[i][]))) cnt++;
return cnt;
}
int dfs(int s) {
if(~dp[s]) return dp[s];
if(__builtin_popcount(s) == ) return ;
int prenum = count(s);
int ans = INT_MIN;
for(int i = ; i < ; i++) {
if(!(s&(<<i))) {
int nownum = count(s|(<<i));
if(nownum == prenum) {
ans = max(ans, -dfs(s|<<i));
}
else {
ans = max(ans, nownum - prenum + dfs(s|<<i));
}
}
}
return dp[s] = ans;
}
int main() {
int T, m, u, v;
for (int i = ; i < ; i++) num[line[i][]][line[i][]] = num[line[i][]][line[i][]] = i;
mem(dp, -);
scanf("%d", &T);
for(int cs = ; cs <= T; cs++) {
int st = ;
scanf("%d", &m);
int prenum = , nownum = ;
int cnt = , step = ;
for (int i = ; i <= m; i++) {
scanf("%d %d", &u, &v);
st |= <<num[u][v];
nownum = count(st);
if(nownum > prenum) {
if(step% == ) cnt += nownum - prenum;
else cnt -= nownum - prenum;
}
else step++;
prenum = nownum;
}
if(step% == ) cnt += dfs(st);
else cnt -= dfs(st);
if(cnt > ) printf("Game %d: A wins.\n", cs);
else printf("Game %d: B wins.\n", cs);
}
return ;
}
思路2：极大极小搜索+alpha-beta剪枝
特点：空间小，时间长
代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<long double, long double>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head int line[][] = {{, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }, {, }};
int tri[][] = {{, , }, {, , }, {, , }, {, , }, {, , }, {, , }, {, , }, {, , }, {, , }};
int num[][];
int count(int s) {
int cnt = ;
for (int i = ; i < ; i++) if((s&(<<tri[i][])) && (s&(<<tri[i][])) && (s&(<<tri[i][]))) cnt++;
return cnt;
}
int dfs(int s, int a, int b, int alpha, int beta, int step) {
if(__builtin_popcount(s) == ) {
if(a > b) return ;
else return -;
}
int prenum = count(s);
for(int i = ; i < ; i++) {
if(!(s&(<<i))) {
int nownum = count(s|(<<i));
if(nownum == prenum) {
if(step% == ) {
int tmp = dfs(s|<<i, a, b, alpha, beta, step+);
if(tmp >= alpha) {
alpha = tmp;
if(alpha >= beta) return alpha;
}
}
else {
int tmp = dfs(s|<<i, a, b, alpha, beta, step+);
if(tmp <= beta) {
beta = tmp;
if(alpha >= beta) return beta;
}
}
}
else {
if(step% == ) {
int tmp = dfs(s|<<i, a+nownum-prenum, b, alpha, beta, step);
if(tmp >= alpha) {
alpha = tmp;
if(alpha >= beta) return alpha;
}
}
else {
int tmp = dfs(s|<<i, a, b+nownum-prenum, alpha, beta, step);
if(tmp <= beta) {
beta = tmp;
if(alpha >= beta) return beta;
}
}
}
}
}
if(step% == ) return alpha;
else return beta;
}
int main() {
int T, m, u, v;
for (int i = ; i < ; i++) num[line[i][]][line[i][]] = num[line[i][]][line[i][]] = i;
scanf("%d", &T);
for(int cs = ; cs <= T; cs++) {
int st = ;
scanf("%d", &m);
int prenum = , nownum = ;
int step = , a = , b = ;
for (int i = ; i <= m; i++) {
scanf("%d %d", &u, &v);
st |= <<num[u][v];
nownum = count(st);
if(nownum > prenum) {
if(step% == ) a += nownum - prenum;
else b += nownum - prenum;
}
else step++;
prenum = nownum;
}
int cnt = dfs(st, a, b, -, , step);
if(cnt > ) printf("Game %d: A wins.\n", cs);
else printf("Game %d: B wins.\n", cs);
}
return ;
}