零和博弈和 Alpha-Beta 剪枝搜索

发布于
2603字 & 6分钟
Algorithm

Alpha-Beta 剪枝算法是极小极大搜索算法的优化，主要解决博弈问题和对策问题。这类算法被广泛运用于棋类等零和博弈问题，比如井字棋 (Tic-Tac-Toe)、中国象棋、国际象棋等。本文将简单介绍零和博弈和 Alpha-Beta 剪枝算法，探索下棋类游戏 AI 是如何实现的。

零和博弈和非零和博弈#

零和博弈，又称零和游戏或零和赛局，与非零和博弈相对，是博弈论的一个概念，属非合作博弈。

零和博弈表示所有博弈方的利益之和为零或一个常数，即一方有所得，其他方必有所失。在零和博弈中，博弈各方是不合作的。

非零和博弈表示在不同策略组合下各博弈方的得益之和是不确定的变量，故又称之为变和博弈。如果某些战略的选取可以使各方利益之和变大，同时又能使各方的利益得到增加，那么，就可能出现参加方相互合作的局面。因此，非零和博弈中，博弈各方存在合作的可能性。

常见的博弈示例：

  • 零和博弈：剪刀石头布、井字棋、黑白棋、五子棋、中国象棋等。（你死我活）
  • 非零和博弈：囚徒困境。（允许双赢或双输）

简单来说，如果把收益和亏损都用分数表示，那在零和博弈中总分数必定为 0，而非零和博弈中总分数不一定为 0。

而在零和博弈类游戏中，存在人与电脑两种角色，当我们需要实现一个游戏 AI 时，我们则需要扮演电脑，且电脑所使用的算法需要尽可能使得电脑的分数最大化。

算法实现示例#

在讲解算法之前，先放一些本人以前利用 Alpha-Beta 剪枝算法实现的示例，感兴趣可以查阅一下源码实现。

极小极大值搜索#

极小极大值搜索算法 (Minimax) 是在有限深度范围内搜索博弈树的一种求解方法。它的基本思想是在博弈双方对弈若干步之后，从可能的步数中选择最好的一种走法来走。

其中，电脑为 MAX 方，人为 MIN 方，按照该回合是电脑回合还是人回合来分成极大值层和极小值层。由于我们扮演的是电脑，因此无论是极大值层还是极小值层，都应该由 MAX 方考虑该怎么走。

极小极大值搜索算法的策略如下：

  • 轮到 MAX 方回合时，MAX 方应该考虑最好的情况，因此该层称为极大值层；
  • 轮到 MIN 方回合时，MAX 方应该考虑最坏的情况，因此该层称为极小值层；
  • 搜索到固定深度后，应该往上一层以极大极小交替的形式传递倒推值。

在 MIN 方回合时为什么需要考虑最坏的情况呢？这是因为我们需要认为 MIN 方始终选择对于它最好的对弈行为，而对于 MAX 方则是最坏的情况。经过这个算法所得到的最终估计值分数，则是当前状况的局部最优解了。

在绘图中，我们通常使用正方形表示极大值层，使用圆形表示极小值层。

minimax

如上图所述，当前轮到 MAX 回合，而我们需要预测未来两回合来找到获取最大分数的行动方案。当在树上搜索达到深度 2 后，就要开始向上传递极小值，然后上一层再向上上层传递极大值。

可以看到在 B 的情况下，虽然选择 b2 最佳，但是由于处于极小值层，既处于 MIN 方的回合，MIN 方必定选择最小分数的行动路线，因此 B 的最优分数是 4。同理，C 和 D 的最优分数分别是 3。而在 A 的情况下，由于处于极大值层，我们必定选择一个最大分数，因此 A 的最优分数是 4。因此对于当前情况，MAX 方的最优路线就是选择 a1 到达 B 情况。

一个简单的极小极大值搜索算法实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 伪代码
func Minimax(node *Node, depth int) int {
    // 到达搜索深度, 返回分数
    if depth == 0 {
        return node.EvaluateScore()
    }

    // 遍历子节点列表
    children := node.GetChildren()
    var score int
    if node.IsMaxLayer() { // 极大值层, 找最大的分数
        score = math.MinInt32
        for _, child := range children {
            score = max(score, Minimax(child, depth - 1))
        }
    } else { // 极小值层, 找最小的分数
        score = math.MaxInt32
        for _, child := range children {
            score = min(score, Minimax(child, depth - 1))
        }
    }
    return score
}

当我们想要在井字棋、象棋之类的棋类 AI 中使用极小极大值搜索算法来计算电脑的下棋位置的时候，只需要修改一下代码，将分数计算替换为电脑胜利的可能性或分数，将子节点遍历修改为走棋方案遍历，即可实现一个简单的电脑 AI。

Alpha-Beta 剪枝搜索#

极小极大值算法虽然能在固定的搜索深度内找到局部最优解，但是随着深度的增加，其搜索时间指数增长。对于象棋、围棋这类复杂的棋类游戏，每一个局面都有非常多的走棋方式，构成的树状结构分支也非常多，通常情况可能搜索到 4~6 层就得消耗数秒或者数十秒，这时候就需要对算法进行一些优化。

Alpha-Beta 剪枝算法就是在极小极大值搜索的基础上，对部分不需要考虑的节点或分支进行剪枝操作。

极小极大值搜索算法生成搜索树之后，会对整个搜索树的节点进行遍历。但实际上，在某些情况下，我们计算出某个节点的估计值之后，将其倒推给它的前驱，它的前驱将得到一个前驱的估计值的不等式，并且可以判断出该前驱的估计值不再需要计算，即最初节点的剩下的兄弟节点不再需要计算估计值。在这个剪枝过程中，我们定了两个值：alpha 值和 beta 值。

  • alpha 值：极大值层的下界，即极大值至少要比 alpha 大或者相等；
  • beta 值：极小值层的上界，即极小值至少要比 beta 小或者相等。

因此，在剪枝的过程中也分为两类剪枝方式：

  • alpha 剪枝：在计算极大值层的估计值时，如果存在一个分支的估计值必定比极大值的下界还小，那么这个分支就是比已遍历的分支更差，那这个分支就无需继续考虑了；
  • beta 剪枝：在计算极小值层的估计值时，如果存在一个分支的估计值必定比极小值的上界还大，那么这个分支就是比已遍历的分支更好，那这个分支就无需继续考虑了。(在极小值层对方始终选择更差的分支)

下图描绘一个简单的剪枝示例。

alpha-beta-pruning

  1. 首先沿着 d1、d2 计算出 D 的 alpha 值为 4，那么倒推可得 B 的 beta 值为 4；
  2. 接着沿着 e1 可计算出 E 的 alpha 值为 5，说明 E 的估计值要比 B 的 beta 值要高，对于 B 来说需要优先考虑更差的结果，于是不再考虑 E，因此 e2 无需再遍历，这就是 beta 剪枝；
  3. 接着倒推可得 A 的 alpha 值为 4；
  4. 接着沿着 f1、f2 计算出 F 的 alpha 值为 3，那么倒推可得 C 的 beta 值为 3；
  5. 对于 A 来说需要优先考虑更优的结果，而 C 的估计值要比 A 的 alpha 值要低，于是不再考虑 C，因此 c2、g1、g2 无需再遍历，这就是 alpha 剪枝；
  6. 最终得出 A 的局部最优解即为 4，最优路线即为 a1。

从数学的角度看，alpha < beta 即为有解。

一个简单的 Alpha-Beta 剪枝算法实现如下：

 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

// 伪代码
func AlphaBetaPruning(node *Node, depth, alpha, beta int) int {
    // 到达搜索深度, 返回分数
    if depth == 0 {
        return node.EvaluateScore()
    }

    // 遍历子节点列表
    children := node.GetChildren()
    if node.IsMaxLayer() { // 极大值层, 找最大的分数
        for _, child := range children {
            alpha = max(alpha, AlphaBetaPruning(child, depth-1, alpha, beta))
            if alpha >= beta { // beta 剪枝
                break
            }
        }
        return alpha
    } else { // 极小值层, 找最小的分数
        for _, child := range children {
            beta = min(beta, AlphaBetaPruning(child, depth-1, alpha, beta))
            if alpha >= beta { // alpha 剪枝
                break
            }
        }
        return beta
    }
}

结语#

极小极大值搜索算法和 Alpha-Beta 剪枝搜索算法是人机对战类游戏实现的基础算法，实现起来也比较简单。当然，实际上人机对战 AI 实现中，除了使用这类算法外，还可以根据游戏本身规则进行定制优化等。

使用 Webpack 进行项目构建