棋类博弈：极小化极大算法与α-β剪枝

发表于2020-12-12更新于2020-12-12字数统计2.7k阅读时长14分

我一直好奇传统的棋类AI（指非机器学习的传统算法实现）是如何实现的，这次在做一个UC San Diego的一个C语言课程作业的时候有了一点点初步了解。

这个作业很简单，就是实现一个人机对弈的屏风式四子棋程序。但是问题来了，“人”一方好办，只需要处理一下输入输出，但是“机”一方怎么决定落子策略？题目的基础分要求是实现一个随机落子的方法，但是同时提出了一个开放式的附加题，要求实现一个best_move()方法，即尝试让机器做出最佳的落子决策。

一般我是不做附加题的（逃），但是这个问题实在有趣，于是我决定初步地探索一下。

本文是棋类博弈初步探索的第一篇，主要来了解什么是极小化极大算法（Minimax Algorithm）。

博弈树

可以注意到，在棋类博弈中，一般是我方和对方交替落子。于是根据动态博弈参与者行动的先后顺序，我们可以依次将参与者的行动展开成一个树状图形。

  • 博弈的初始格局是初始节点。
  • 在博弈树中，“或”节点和“与”节点是逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮流地扩展节点。
  • 所有自己一方获胜的终局相应的节点是可解节点；所有使对方获胜的终局都认为是不可解节点。

一个井字棋的博弈树的简单示例如上。

极大极小树

在设计博弈类AI时，我们一般都假设对弈双方是聪明绝顶的博弈高手，每次都能根据当前的局面做出对自己一方最有利的决策。

在轮到我们做出决策时，我们总是希望最大化我们的收益，叫做极大层，此时树的节点叫做极大层节点；同样，在对方做决策时，总是希望最小化我们的收益，叫做极小层，此时树的节点叫做极小层节点。故而双方交替进行决策时，总是极大曾和极小层交替出现的，这样一种特殊的博弈树就叫做极大极小树。

如果使用圆圈○表示轮到到我方决策极小层节点，方框□表示轮到对方决策极大层节点，于是可以画成：

极小化极大算法

了解了什么是博弈树和极大极小树之后，我们就可以来了解一下什么是极小化极大算法了。

简介

一句话概括，极小化极大算法其实就是，找出失败的最大可能性中的最小值的算法，或，找出成功最小可能性中的最大值的算法。

听起来很绕，我们来理解一下。以上文极大极小树的例图来讲，面对初始局面的我们，一定会想从第二层分支局面中选择收益最高的进行决策，而面对每个第二层分支局面（局面1, 2, 3），对手都会想办法选择自己收益最高（也即对于我们收益最低）的第三层分支局面。也就是，在对手绝对精明的情况下，我们选择的每个第二层局面，会走向结局最差的第三层局面，也就是第二层每个局面的收益其实是第三层的最低收益，而我们需要在这些最低收益中寻找最高的那个。

看到这里，相信你已经明白了，极小化极大算法是一种悲观算法，即假设对手每一步都会将我方引入从当前看理论上价值最小的格局方向，即对手具有完美决策能力。因此我方的策略应该是选择那些对方所能达到的让我方最差情况中最好的，也就是让对方在完美决策下所对我造成的损失最小。极小化极大算法不找理论最优解，因为理论最优解往往依赖于对手是否足够愚蠢，极小化极大算法中我方完全掌握主动，如果对方每一步决策都是完美的，则我方可以达到预计的最小损失格局，如果对方没有走出完美决策，则我方可能达到比预计的最悲观情况更好的结局。总之我方就是要在最坏情况中选择最好的。

为了比较每个局面的收益，我们需要将局面的收益进行量化。极小化极大算法的核心之一就是局面评估算法，如果这个算法写的好，能完美的描述当前的局面，那么在极大极小树中，计算机总能选择到最好的分支。反之，如果评估算法写的稀烂，计算机是没办法做出正确决策的。但是局面评估算法没有固定的套路，只能依靠我们对游戏本身的理解、经验进行编写。不过一般来讲，局面对我方有利时局面分是正值，对对方有利时是负值，平局是0分，我方胜利是+∞分，对方胜利是-∞分。

图解

极小化极大算法是一个深度优先搜索算法。我们这里先规定搜索深度为3（实际情况中由于算力的原因必须限制搜索深度）。

虽然α-β剪枝在上文中一直没有提到，但是看了下面的图解你自然明白。

  1. 从根节点开始一直搜索到第一个叶节点

  2. 此时我们的搜索深度已经达到了3，所以此时需要调用评估函数，返回局面分，回溯一层。

  3. 仔细思考，如果我们继续获得其子节点的局面分，为一个比3要大的值，假设为5，那么当前的父节点必然不会采纳5这个值，因为对手希望我们的收益最低。也即得到第一个子节点局面分为3之后，我们就能知道父节点的取值范围为(-∞, 3]。也就是说，我们的子节点其实是在更新父节点的上界值（越低越好）。这里就是α-β剪枝的一部分了，但是并不是剪枝，而是更新了β的值，也就是上界值。

  4. 鉴于这个父节点的所有子节点都已经被搜索完，我们也就确定了它的收益就是3了，这时候就能修改它的下界为3。

  5. 我们继续搜索，此时回溯一层，回溯到了根节点。根节点的原本的局面分取值范围是(-∞, +∞)，而现在我们找到了它的一个子节点局面分是3。根节点与其子节点不同，是极大层节点，是我们的回合，我们总希望收益越大越好，所以这里子节点会更新极大层节点的下界，也即α值。

  6. 继续进行深度优先搜索，这时我们搜索到根节点第二分支的第一个子节点，注意我们带着根节点的范围进行搜索，根节点的范围被传递给他的第二个子节点。此时搜索深度达到了3，我们调用局面评估算法，假设返回值是2。

  7. 注意，剪枝部分来了。我们知道，当前节点的父节点是一个极小层节点，所以子节点会更新父节点的上界，也就是父节点的局面分取值范围变成了矛盾区间[3, 2]。这是个明显矛盾的结论，所以这整个分支我们都可以抛弃，不必继续搜索了。

这样我们的搜索就结束了，可以确定我们应该选择左侧局面，并且预期最低收益为3。

总之，只要局面分的取值区间变成了矛盾的，就说明该分支不可能变成最优决策，应当抛弃。

通过维护一个局面分的最佳区间，在搜索过程中对于造成区间矛盾（不可能取到更优值）的情况下剪枝，就是所谓的α-β剪枝。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function get_min_val(node, a, b) {  // a, b　分别是下上界，此函数作用于极小层节点
	if (termination_condition) {  // 达到搜索深度，或者赢了输了平局等
		return eval_situ(node);  // 返回局面评估分
	}
	v = +INF;  // v是子节点的值，预设为正无穷
	for (next_action in all_actions_possible) {
		child = result(node, next_action);
		v = min(v, get_max_val(child, a, b));
		if (v <= a) {
			return v;  // 剪枝，v突破了下限，出现[a, v]矛盾区间
		}
		b = min(b, v);  // 更新上限
	}
	return v;  // 返回找到的最小值
}

function get_max_val(node, a, b) {
	if (termination_condition) {
		return eval_situ(node);
	}
	v = -INF;
	for (next_action in all_actions_possible) {
		child = Result(node, next_action);
		v = max(v, get_min_val(child, a, b));
		if (v >= b) {
			return v;  // 剪枝，v突破了上限，出现了[v, b]矛盾区间
		}
		a = max(a, v);  // 更新下限
	}
	return v;
}

可以看到，上述伪代码中，eval_situ(node)和child = Result(node, next_action)都表明，一个节点中存储了全部的棋盘信息，这样会占用大量空间，实际使用过程中，如果是用于棋类博弈，可以直接在函数开始时在正式的棋盘（一般是个二维数组）上下棋，然后return之前弹出之前下的子，这样就不占用额外空间了。

关于这两个函数的具体用法，假设是屏风式四子棋，要决定当前局面的最佳步骤。很明显，我们总是有7个可选项（对于7×6棋盘），用数字1到7表示七个列的选择，则可以这样写：

1
2
3
function best_choice(board) {
	return get_max_val(board, -INF, INF);  // 得到当前的最佳选择
}

参考

中文维基百科——极小化极大算法

中文维基百科——Alpha-beta剪枝

博弈树——MBA智库百科

博弈游戏的AI设计（二）：博弈树与α-β剪枝

隔三岔五聊算法之极小极大算法