吴锴的博客

Life? Don't talk to me about life!

0%

Minimax 和 Alpha-beta 剪枝算法简介，及以此实现的井字棋游戏（Tic-tac-toe）

发表于 更新于

前段时间用 React 写了个2048 游戏来练练手，准备用来回顾下 React 相关的各种技术，以及试验一下新技术。在写这个2048的过程中，我考虑是否可以在其中加入一个 AI 算法来自动进行游戏，于是我找到了这篇文章：2048-AI程序算法分析，文中介绍了 minimax 算法和 alpha-beta 剪枝算法。于是我决定先学习下这两种算法，并以此写了这个 tic-tac-toe 游戏：tic-tac-toe-js（代码见此处）。本文将说明如何用 JavaScript 来简单地实现算法，并将其运用到 tic-tac-toe 游戏中。

Minimax 算法简介

我觉得要解释 minimax 算法的原理，需要用示意图来解释更清晰，以下的几篇文章都对原理说的足够清楚。

  1. 2048-AI程序算法分析
  2. Tic Tac Toe: Understanding the Minimax Algorithm
  3. An Exhaustive Explanation of Minimax, a Staple AI Algorithm

其中后面的两篇文章都是以 tic-tac-toe 游戏为例，并用 Ruby 实现。

以棋类游戏为例来说明 minimax 算法，每一个棋盘的状态都会对应一个分数。双方将会轮流下棋。轮到我方下子时，我会选择分数最高的状态；而对方会选择对我最不利的状态。可以这么认为，每次我都需要从对手给我选择的最差（min）局面中选出最好（max）的一个，这就是这个算法名称 minimax 的意义。

minimax tree （图片来自于 http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html）

我们接下来会解决这样一个问题，如上图所示，正方形的节点对应于我的决策，圆形的节点是对手的决策。双方轮流选择一个分支，我的目标是让最后选出的数字尽可能大，对方的目标是让这个数字尽可能小。

Minimax 算法的实现

为了简单起见，对于这个特定的问题，我用了一个嵌套的数组来表示状态树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const dataTree = [
    [
        [
            [3, 17], [2, 12]
        ],
        [
            [15], [25, 0]
        ]
    ],
    [
        [
            [2, 5], [3]
        ],
        [
            [2, 14]
        ]
    ]
];

图中的节点分为两种类型：

  1. Max 节点：图中的正方形节点，对应于我的回合，它会选取所有子节点中的最大值作为自身的值
  2. Min 节点：图中的圆形节点，对应于对手的回合，它会选取所有子节点中的最小值作为自身的值

先定义一个 Node 类，constructor 如下：

1
2
3
4
5
constructor(data, type, depth) {
    this.data = data;
    this.type = type; // 区分此节点的种类是 max 或 min
    this.depth = depth;
}

根节点的 depth 为0，以下的每一层 depth 依次加一。最底层的节点 depth 为4，其 data 是写在图中的数字，其它层节点的 data 均是一个数组。

接下来考虑如何给每个节点打分，可能会出现这样的几种情况：

  1. 最底层的节点，直接返回本身的数字
  2. 中间层的 max 节点，返回子节点中的最大分数
  3. 中间层的 min 节点，返回子节点中的最小分数

为方便描述，我们按照由上到下、由左到右的顺序给图中节点进行标号。节点1是 max 节点，从节点2和节点3中选择较大值；而对于节点2来说，需要从节点4，5中选取较小值。很显然，我们这里要用递归的方法来实现，当搜索到最底层的节点时，递归过程开始返回。

minimax tree mark

以下是打分函数 score 的具体代码：

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
score() {
    // 到达了最大深度后，此时的 data 是数组最内层的数字
    if (this.depth >= 4) {
        return this.data;
    }

    // 对于 max 节点，返回的是子节点中的最大值
    if (this.type === 'max') {
        let maxScore = -1000;

        for (let i = 0; i < this.data.length; i++) {
            const d = this.data[i];
            // 生成新的节点，子节点的 type 会和父节点不同
            const childNode = new Node(d, changeType(this.type), this.depth + 1);
            // 递归获取其分数
            const childScore = childNode.score();

            if (childScore > maxScore) {
                maxScore = childScore;
            }
        }

        return maxScore;
    }

    // 对于 min 节点，返回的是子节点中的最小值
    else if (this.type === 'min') {
        // 与上方代码相似，省略部分代码
    }
}

完整的 minimax 算法代码

Alpha-beta 剪枝算法简介

Alpha-beta 剪枝算法可以认为是 minimax 算法的一种改进，在实际的问题中，需要搜索的状态数量将会非常庞大，利用 alpha-beta 剪枝算法可以去除一些不必要的搜索。

关于 alpha-beta 算法的具体解释可以看这篇文章 Minimax with Alpha Beta Pruning。我们在前文中考虑的那张图就来自这篇文章，之后我们会用 alpha-beta 剪枝算法来改进之前的解决方案。

剪枝算法中主要有这么些概念：

每一个节点都会由 alpha 和 beta 两个值来确定一个范围 [alpha, beta]，alpha 值代表的是下界，beta 代表的是上界。每搜索一个子节点，都会按规则对范围进行修正。

Max 节点可以修改 alpha 值，min 节点修改 beta 值。

如果出现了 beta <= alpha 的情况，则不用搜索更多的子树了，未搜索的这部分子树将被忽略，这个操作就被称作剪枝（pruning）。

接下来我会尽量说明为什么剪枝这个操作是合理的，省略了一部分节点为什么不会对结果产生影响。用原图中以4号节点（第三层的第一个节点）为根节点的子树来举例，方便描述这里将他们用 A - G 的字母来重新标记。

子树

从 B 节点看起，B 是 min 节点，需要在 D 和 E 中寻找较小值，因此 B 取值为3，同时 B 的 beta 值也设置为 3。假设 B 还有更多值大于3的子节点，但因为已经出现了 D 这个最小值，所以不会对 B 产生影响，即这里的 beta = 3 确定了一个上界。

A 是 max 节点，需要在 B 和 C 中找到较大值，因为子树 B 已经搜索完毕，B 的值确定为 3，所以 A 的值至少为 3，这样确定了 A 的下界 alpha = 3。在搜索 C 子树之前，我们希望 C 的值大于3，这样才会对 A 的下界 alpha 产生影响。于是 C 从 A 这里获得了下界 alpha = 3 这个限制条件。

C 是 min 节点，要从 F 和 G 里找出较小值。F 的值为2，所以 C 的值一定小于等于 2，更新 C 的上界 beta = 2。此时 C 的 alpha = 3, beta = 2，这是一个空区间，也就是说即使继续考虑 C 的其它子节点， 也不可能让 C 的值大于 3，所以我们不必再考虑 G 节点。G 节点就是被剪枝的节点。

重复这样的过程，会有更多的节点因为剪枝操作被忽略，从而对 minimax 算法进行了优化。

Alpha-beta 剪枝算法的实现

接下来讨论如何修改前面实现的 minimax 算法，使其变为 alpha-beta 剪枝算法。

第一步在 constructor 中加入两个新属性，alpha、beta。

1
2
3
4
5
6
7
8
constructor(data, type, depth, alpha, beta) {
    this.data = data;
    this.type = type; // 区分此节点的种类是 max 或 min
    this.depth = depth;

    this.alpha = alpha || -Infinity;
    this.beta = beta || Infinity;
}

然后每次都搜索会视情况更新 alpha, beta 的值，以下的代码片段来自于搜索 max 节点的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// alphabeta.js 中的 score() 函数

for (let i = 0; i < this.data.length; i++) {
    // ...

    if (childScore > maxScore) {
        maxScore = childScore;
        // 相对于 minimax 算法，alpha-beta 剪枝算法在这里增加了一个更新 alpha 值的操作
        this.alpha = maxScore;
    }

    // 如果满足了退出的条件，我们不需要继续搜索更多的节点了，退出循环
    if (this.alpha >= this.beta) {
        break;
    }

相对应的是在 min 节点中，我们更新的将是 beta 值。好了，只需要做这么些简单的改变，就将 minimax 算法改变成了 alpha-beta 剪枝算法了。

最后看看如何将算法应用到 tic-tac-toe 游戏中。

完整的 alpha-beta 剪枝算法代码

Tic-tac-toe 游戏中的应用

Tic-tac-toe，即井字棋游戏，规则是在双方轮流在 3x3 的棋盘上的任意位置下子，率先将三子连成一线的一方获胜。

这就是一个非常适合用 minimax 来解决的问题，即使在不考虑对称的情况，所有的游戏状态也只有 9! = 362880 种，相比于其它棋类游戏天文数字般的状态数量已经很少了，因而很适合作为算法的示例。

我在代码中将棋盘的状态用一个长度为9的数组来表示，然后利用 canvas 绘制出一个简易的棋盘，下子的过程就是修改数组的对应位置然后重绘画面。

现在我们已经有了现成的 minimax 和 alpha-beta 剪枝算法，只要加上一点儿细节就能完成这个游戏了😀。

先来定义一个 GameState 类，其中保存了游戏的状态，对应于之前分析过程中的节点，其 constructor 如下：

1
2
3
4
5
6
7
8
9
10
11
constructor(board, player, depth, alpha, beta) {
    this.board = board;
    // player 是用字符 X 和 O 来标记当前由谁下子，以此来判断当前是 max 还是 min 节点
    this.playerTurn = player;
    this.depth = depth;

    // 保存分数最高或最低的状态，用于确定下一步的棋盘状态
    this.choosenState = null;
    this.alpha = alpha || -Infinity;
    this.beta = beta || Infinity;
}

为进行游戏，首先需要一个 checkFinish 函数，检查游戏是否结束，结束时返回胜利者信息。搜索的过程是在 getScore 函数中完成的，每次搜索先检查游戏是否结束，平局返回零分，我们的算法是站在 AI 的角度来考虑的，因此 AI 胜利时返回10分，AI 失利时返回-10分。

1
2
3
4
5
6
7
8
// alphabeta.js 中的 getScore() 方法

const winner = this.checkFinish();
if (winner) {
    if (winner === 'draw') return 0;
    if (winner === aiToken) return 10;
    return -10;
}

接着是对 max 和 min 节点的分类处理：

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
32
33
34
35
36
37
38
// alphabeta.js 中的 getScore() 方法

// 获得所有可能的位置，利用 shuffle 加入随机性
const availablePos = _.shuffle(this.getAvailablePos());

// 对于 max 节点，返回的是子节点中的最大值
if (this.playerTurn === aiToken) {
    let maxScore = -1000;
    let maxIndex = 0;

    for (let i = 0; i < availablePos.length; i++) {
        const pos = availablePos[i];
        // 在给定的位置下子，生成一个新的棋盘
        const newBoard = this.generateNewBoard(pos, this.playerTurn);

        // 生成一个新的节点
        const childState = new GameState(newBoard, changeTurn(this.playerTurn), this.depth + 1, this.alpha, this.beta);
        // 这里开始递归调用 getScore() 函数
        const childScore = childState.getScore();

        if (childScore > maxScore) {
            maxScore = childScore;
            maxIndex = i;
            // 这里保存产生了最大的分数的节点，之后会被用于进行下一步
            this.choosenState = childState;
            this.alpha = maxScore;
        }

        if (this.alpha >= this.beta) {
            break;
        }
    }

    return maxScore;
}

// min 节点的处理与上面类似
// ...

完整代码见alphabeta.js

总结

这样就简单地介绍了 minimax 算法和 alpha-beta 算法，并分别给出了一个简单的实现，然后在 tic-tac-toe 游戏中应用了算法。

文章中所提到的所有代码可见此项目：Tic-tac-toe-js。其中的 algorithms 文件夹中是两种算法的简单实现，src 文件中是游戏的代码。

文章开头说到了这篇文章起源于写2048游戏项目的过程中，之后我将 minimax 算法应用到了2048游戏的 AI 中，不过对于局面的评估函数尚不完善，现在 AI 只能勉强合成1024😢， 还有很大的改进空间。

如果我的文章对你有帮助，欢迎打赏支持！

欢迎关注我的其它发布渠道