五子棋AI优化：α-β剪枝
我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第7篇文章，点击查看活动详情
本文首发于我的个人博客：xeblog.cn/articles/76
前言
回顾上文，我们介绍了 极大极小值搜索 算法的实现原理，使得我们的 AI 可以进行更深层次的思考，棋力突飞猛进。但此时，我们又发现了一个新的问题，由于 博弈树 的分支太多，计算量太过庞大，从而使得 AI 的响应时间变长，原本思考一步的 AI 在毫秒之间就能计算出最佳落子点，现在思考两步的 AI 需要花费好几秒的时间才能找出最佳走步。棋力虽然是提升了很多，但面对这么长的耗时，我们能否做一些优化呢？
有些人可能就会说了，你特么标题不都写了吗？还问我？
所以，本文将介绍一种优化算法：α-β剪枝。
Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝。—— 百度百科
α-β剪枝
算法实现原理
这个算法的实现原理并不难，甚至还特别简单。在讲解算法之前，我们先搞清楚一个问题：下图中，博弈树 A1 分支的深度优先遍历（后序遍历）的过程是怎样的？
只要搞清楚这个问题，后面讲解算法的时候就不会被弄糊涂啦。
上图描绘出了 A1 访问左子树 B1 的过程。标了数字的节点表示的是处理的顺序，优先处理最深层的节点，然后将深层节点的处理结果返回给上一层的节点，如果这一层还有节点，则继续处理，直至所有节点都处理完毕。
我们回顾一下之前 A1 分支 极大极小值搜索 的过程：
B5 ~ B12 节点是 AI和对手交替落子第四步后所形成的局面，局面对应的评分都标在了节点的下方。我们都知道，B5 ~ B12 的分支都是 Min 分支，Min 分支会将得分最低的节点返回给上层的 Max 分支，所以 A3 ~ A6 分支的得分都是对手给的最低分。接下来，轮到 A3 ~ A6 分支做选择，Max 分支会将得分最高的节点返回给上层的 Min 分支，也就是说 B1 ~ B2 分支的得分是从 A3 ~ A6 分支里挑选出来的最高分，然后 B1 ~ B2 分支又会将最小的得分返回给 A1。
在 极大极小值搜索 的过程中，其实有些分支是可以不用访问的，比如上图中 A4 不用访问 B8 分支，B2 不用访问 A6 分支，为什么呢？
我们下面利用 α-β剪枝 算法来解释为什么有些节点不用访问。
定义变量：Max 分支挑选出来的最高分记为 α；Min 分支挑选出来的最低分记为 β。初始时， α 值为无穷小 -∞，β 值为无穷大 +∞。
从 A1 分支开始，将 α 和 β 变量向下传递，如图所示
我们先从 Max 分支 A3 看起，A3 下一步会访问 Min 分支的 B5 节点，并且将 α 和 β 变量向下传递到 B5，如图所示
此时，B5 计算出了局面评分为 4，将这个评分和 β 进行比较，如果评分 < β 就更新 β 的值为当前评分。因为 4 < +∞ ，所以当前的 β 值被更新为了 4，如图所示
继续访问 B6 节点。此时，B6 节点评分为 2，与当前 β 值进行比较， 因为 2 < 4 满足条件，所以更新 β 值为 2，如图所示
B5 ~ B6 节点都访问完毕后，要将当前的 β 的值返回给上一层的 Max 分支 A3，A3 此时需要做一步操作：如果 β > α，则更新 α 的值为 β，如图所示
此时，A3分支的 α 值为 2，β 值为 +∞，A3 分支结束，进入到 A4 分支，并将 α 和 β 变量传递，如图所示
A4 下一步会访问 Min 分支的 B7 节点，并且将 α 和 β 变量向下传递到 B7，如图所示
此时，B7 局面评分为 1，因为 1 < +∞，所以当前 β 更新为 1。此时，α 值为 2，β 值为 1。
这时候，我们要做一步操作：如果 α >= β 则结束当前层次的遍历。这就叫做 剪枝。
因为 α(2) >= β(1) ，所以我们可以跳过B8 节点的访问。
这是为什么呢？
原因很简单，因为 α 储存着当前最大分值，β 储存着当前最小分值，在 Min 分支的时候，一直都在搜索小于 β 值的节点，找到之后会更新 β 值，并返回给 Max 分支，如果 α 此时的值就比 β 要大，那你返回给我的 β 值肯定也是会小于我当前的 α 值的，你给我我也不会要，因为我要的是比 α 大的值才对。这里说的可能会有点难以理解，我们可以这么理解：
抢劫犯已经从张三的口袋中拿到了1000元现金，张三此时却想要拿《Java从入门到入土》这本破书给他换，你说抢劫犯他能同意吗？
就是这个意思，我手中已经有好东西了，你却想拿一个不值钱的东西给我换？我肯定是不答应的。B5 ~ B6 分支给到 A3 的分数为 2，B7 ~ B8 分支给到 A4 的分数为 1，A4 的分数小于 A3，已经没有选择他的必要了，这个结果在 B7 节点的时候就已经能确定了，所以 B7 之后的节点都不用再去访问了，我们可以剪掉那些不用访问的分支。最后 A4 节点将当前的 α 值返回给了 B1 分支，如图所示
我们再来看 B2 分支，B2 分支将当前的 α、β 值向下传递到 B9，如图所示
B9 评分为 4，由于 4 > 2，不满足 β 的更新条件，接着访问 B10，同样也不满足更新条件，最后 β 值还是 2，将该值返回给 A5，因为 2 > -∞，所以需要将当前的 α 值更新为 2，此时 α(2) >= β(2) 条件成立，又可以跳过后面的节点了，A6 分支可以剪掉。
最后，A5 将当前的 α 返回给 B2，B2 将当前的 β 返回给 A1，所以A1 最终的得分为 2。
有一个地方大家可能还会有疑问：为什么 Min 分支返回给 Max 分支 β 时，Max 分支不是更新 β 而是更新 α ？
回看一下，我们上文对 α 和 β 的定义：
Max分支挑选出来的最高分记为α；Min分支挑选出来的最低分记为β。初始时，α值为无穷小-∞，β值为无穷大+∞。
Min 分支返回给 Max 分支的最小分值其实就是当前 Max 分支的分值，所以需要更新的是 α 值，同样的，Max 分支会选择最大的一个 α 值返回给 Min 分支，这个 α 值也就是当前 Min 分支的分值，所以需要更新的是 β 值。我们只需要记住一点：α 值的来源是 β，β 值的来源是 α（除了叶子结点，因为叶子结点的值来源于评估函数）。
代码实现
我们再接着上次的代码，稍微修改下之前写的 minimax 方法，新增两个输入参数：alpha 和 beta ，代码改动其实不是很大。
/**
* 极大极小值搜索、AlphaBeta剪枝
*
* @param type 当前走棋方 0.根节点表示AI走棋 1.AI 2.玩家
* @param depth 搜索深度
* @param alpha 极大值
* @param beta 极小值
* @return
*/
private int minimax(int type, int depth, int alpha, int beta) {
// 是否是根节点
boolean isRoot = type == 0;
if (isRoot) {
// 根节点是AI走棋
type = this.ai;
}
// 当前是否是AI走棋
boolean isAI = type == this.ai;
// 到达叶子结点
if (depth == 0) {
/**
* 评估每棵博弈树的叶子结点的局势
* 比如：depth=2时，表示从AI开始走两步棋之后的局势评估，AI(走第一步) -> 玩家(走第二步)，然后对局势进行评估
* 注意：局势评估是以AI角度进行的，分值越大对AI越有利，对玩家越不利
*/
return evaluateAll();
}
for (int i = 0; i < this.cols; i++) {
if (alpha >= beta) {
/*
AlphaBeta剪枝
解释：
AI当前最大分数为：alpha 搜索区间 (alpha, +∞]
对手当前最小分数为：beta 搜索区间 [-∞, beta)
因为对手要选择分数小于beta的分支，AI要从对手给的分支里面选最大的分支，这个最大的分支要和当前的分支(alpha)做比较，
现在alpha都比beta大了，下面搜索给出的分支也都是小于alpha的，所以搜索下去没有意义，剪掉提高搜索效率。
*/
break;
}
for (int j = 0; j < this.rows; j++) {
if (this.chessData[i][j] != 0) {
// 该处已有棋子，跳过
continue;
}
/* 模拟 AI -> 玩家 交替落子 */
Point p = new Point(i, j, type);
// 落子
putChess(p);
// 递归生成博弈树，并评估叶子结点的局势
int score = minimax(3 - type, depth - 1, alpha, beta);
// 撤销落子
revokeChess(p);
if (isAI) {
// AI要选对自己最有利的节点（分最高的）
if (score > alpha) {
// 最高值被刷新，更新alpha值
alpha = score;
if (isRoot) {
// 根节点处更新AI最好的棋位
this.bestPoint = p;
}
}
} else {
// 对手要选对AI最不利的节点（分最低的）
if (score < beta) {
// 最低值被刷新，更新beta值
beta = score;
}
}
if (alpha >= beta) {
// 剪枝
break;
}
}
}
return isAI ? alpha : beta;
}
调整入口方法 getPoint，minimax 方法传入 α 和 β，α 值初始为 -INFINITY，β 值初始为 INFINITY。
@Override
public Point getPoint(int[][] chessData, Point point, boolean started) {
initChessData(chessData);
this.ai = 3 - point.type;
this.bestPoint = null;
this.attack = 2;
if (started) {
// AI先下，首子天元
int centerX = this.cols / 2;
int centerY = this.rows / 2;
return new Point(centerX, centerY, this.ai);
}
// 基于极大极小值搜索获取最佳棋位
minimax(0, 2, -INFINITY, INFINITY);
return this.bestPoint;
}
经过优化后，思考两步棋的 AI 耗时基本控制在 1s 内。
α-β剪枝 算法对节点价值的顺序要求很高，如果价值高的节点都排在后面，那这个算法的优化效果不会太好，所以后续还需要对节点进行价值排序，以便将 α-β剪枝的效果发挥到极致。