[学习笔记] Minimax 算法和 Alpha-Beta 剪枝

SnowSlug / 2024-10-23 / 原文

题目引入

在博弈论中，有这样一类题目：

两个玩家 A、B 轮流行动，A 先手，B 后手。
有一个结果，A 想要使它最大，B 想要使它最小。

Minimax 算法

把每个状态作为一个点，每个转移作为一条边建出一棵树。这棵树好像叫博弈树。

两种实现（都没有真正地建树）：

直接搜索（可能有结点被重复经过）
记忆化搜索。

现在我们不考虑 当前的 先手和后手，而是考虑当前结点是 一开始的 先手还是后手行动，即是 A 还是 B 行动。

每个状态得到一个确定的权值。因为 A 想让 根节点的 权值尽量大，所以 Ta 会在 Ta 行动的每一步都取子结点权值的 max。类似地，B 会在 Ta 行动的每一步取子结点的 min。

那么直接用上面提到的两种实现来实现这个“树形 DP”的过程即可。

注意叶子结点的权值怎么赋。这里以游戏有胜负（没有平，但要加上平的情况似乎是类似的），胜负优先为例：

无论如何，A 获胜的权值比 A 失败的权值大。
同样是获胜（或失败），更优的情况权值更大。

可以通过 和一个大常数加减 来实现，具体见后面的例题。

Alpha-Beta 剪枝

jsh: 画图！

这是一个不会影响答案正确性的剪枝。

假设在搜索过程中，一个结点 $u$ 是一个结点 $v$ 的 祖先结点，且 $u$ 和 $v$ 是不同的人行动，而且这两个结点都有值了，虽然这个值可能不是最终的值。下面以 $u$ 是 A 行动，$v$ 是 B 行动的情况为例，记 $u$ 当前的值为 $x$，$v$ 当前的值为 $y$：

$u$ 要取 $\max$，那么 $u$ 最终的值一定 $\geq x$。
$v$ 要取 $\min$，那么 $v$ 最终的值一定 $\leq y$。
那么如果已经有 $y \leq x$ 了，那么 $v$ 就一定不会更新 $u$ 的值了。否则 $v$ 还有可能更新 $u$。

如果 $u$ 是 A 行动，$v$ 是 B 行动，那么有类似的结论。

我们把两种情况和剪枝策略总结如下：

$u$ 和 $v$ 是一对 行动的人不同 的 祖先、子孙 结点（不管哪个是祖先、哪个是子孙）。设 A 先手的点（max）的当前权值为 Alpha，B 先手的点（min）的当前权值为 Beta。
那么如果 Alpha >= Beta，那个子孙结点就可以不用接着搜了，直接返回。
实际上，因为我们只要求得到根结点的最终权值，所以一条链上有任意的两个点满足限制就可以返回了。于是记录当前结点到根的链上 A 结点权值的 max（代码里记为 al）和 B 结点权值的 min（代码里记为 be），比较这二者即可。
但是代码实现上好像有所不同，之前子树里的结点的 min、max 好像也会被算进当前结点，不知道对不对、如果对那么为什么是对的。（我这里的代码实现是从 OI-Wiki 上学的，见后面的“参考”部分里 oi-wiki 的链接）

代码建议参考 OI-Wiki，其中重复的部分应该可以合到一起写。但是 OI-Wiki 上的写法我还不确定正确性。不过我用这个写法过了下面的例题。

例题代码

这里给出 2024.10.16 考试 T3（这道题应该算是 Minimax 算法 + Alpha-Beta 剪枝的板子题）我的代码。

#include <bits/stdc++.h>
using namespace std;

const int N = 20, M = 20, INF = 1000000000, C = 1000;
int n, m;
int a[N + 1][M + 1];
int dx[] = {1, - 1, 0, 0}; // ?
int dy[] = {0, 0, 1, - 1}; // ?

int DFS(int x, int y, int xx, int yy, int cnt, int al, int be, bool ismax)
{
	bool flag = 0;
//	int res;
//	if(ismax) res = (- INF);
//	else res = INF;
	for(int i = 0; i < 4; ++ i){
		int nx = x + dx[i], ny = y + dy[i];
		if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 0){
			flag = 1;
			a[nx][ny] = 4; //
			if(ismax){
//				res = max(res, DFS(xx, yy, nx, ny, cnt + 1, al, be, ! ismax)); // max
				al = max(al, DFS(xx, yy, nx, ny, cnt + 1, al, be, ! ismax)); // max
			}
			else{
//				res = min(res, DFS(xx, yy, nx, ny, cnt + 1, al, be, ! ismax)); // min
				be = min(be, DFS(xx, yy, nx, ny, cnt + 1, al, be, ! ismax)); // min
			}
			a[nx][ny] = 0; //
			if(al >= be) break; //
		}
	}
	if(flag){
		if(ismax) return al; // ?
		else return be; // ?
//		return res;
	}else{
		// 注意“估价”（这里不是估计）问题，即怎么给终止状态赋值
		if(ismax) return (cnt - C); // 1 号蛇输，1 号蛇要让 cnt 尽量大
		else return (C - cnt); // 2 号蛇输，2 号蛇要让 cnt 尽量大，1 号蛇要让 cnt 尽量小
		// 2 号蛇输的情况一定比 1 号蛇输的情况的权值更大
	}
}

void Solve()
{
	scanf("%d%d", & n, & m);
	int x, y, xx, yy;
	for(int i = 1; i <= n; ++ i){
		for(int j = 1; j <= m; ++ j){
			scanf("%d", & a[i][j]);
			if(a[i][j] == 1){
				x = i;
				y = j;
			}else if(a[i][j] == 2){
				xx = i;
				yy = j;
			}
		}
	}
	int ans = DFS(x, y, xx, yy, 1, - INF, INF, true);
//	printf("%d %d", ((ans > 0) ? 1 : 2), ((ans < 0) ? (- ans) : ans)); // ans 可能是负的，不要乱用 ans & 1，我不知道结果是什么样的
	if(ans > 0) printf("1 %d", C - ans);
	else printf("2 %d", C + ans);
}

int main()
{
	freopen("h.in", "r", stdin);
	freopen("h.out", "w", stdout);
	Solve();
	fclose(stdin);
	fclose(stdout);
	return 0;
}
// alpha-beta 剪枝
/*
参考：
https://zhuanlan.zhihu.com/p/404144927（应该不全）
https://oi-wiki.org/search/alpha-beta/#%E5%AE%9E%E7%8E%B0
关于给终止状态赋值参考 std
*/
// 一回合是一步
/*
4 4
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2

2 15 )（？）
*/