摘要：我們?cè)谇拔闹锌紤]的那張圖就來(lái)自這篇文章，之后我們會(huì)用剪枝算法來(lái)改進(jìn)之前的解決方案。剪枝算法的實(shí)現(xiàn)接下來(lái)討論如何修改前面實(shí)現(xiàn)的算法，使其變?yōu)榧糁λ惴ā，F(xiàn)在我們已經(jīng)有了現(xiàn)成的和剪枝算法，只要加上一點(diǎn)兒細(xì)節(jié)就能完成這個(gè)游戲了。

前段時(shí)間用 React 寫了個(gè)2048 游戲來(lái)練練手，準(zhǔn)備用來(lái)回顧下 React 相關(guān)的各種技術(shù)，以及試驗(yàn)一下新技術(shù)。在寫這個(gè)2048的過(guò)程中，我考慮是否可以在其中加入一個(gè) AI 算法來(lái)自動(dòng)進(jìn)行游戲，于是我找到了這篇文章：2048-AI程序算法分析，文中介紹了 minimax 算法和 alpha-beta 剪枝算法。于是我決定先學(xué)習(xí)下這兩種算法，并以此寫了這個(gè) tic-tac-toe 游戲：tic-tac-toe-js（代碼見此處）。本文將說(shuō)明如何用 JavaScript 來(lái)簡(jiǎn)單地實(shí)現(xiàn)算法，并將其運(yùn)用到 tic-tac-toe 游戲中。

我覺(jué)得要解釋 minimax 算法的原理，需要用示意圖來(lái)解釋更清晰，以下的幾篇文章都對(duì)原理說(shuō)的足夠清楚。

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

其中后面的兩篇文章都是以 tic-tac-toe 游戲?yàn)槔⒂?Ruby 實(shí)現(xiàn)。

以棋類游戲?yàn)槔齺?lái)說(shuō)明 minimax 算法，每一個(gè)棋盤的狀態(tài)都會(huì)對(duì)應(yīng)一個(gè)分?jǐn)?shù)。雙方將會(huì)輪流下棋。輪到我方下子時(shí)，我會(huì)選擇分?jǐn)?shù)最高的狀態(tài)；而對(duì)方會(huì)選擇對(duì)我最不利的狀態(tài)。可以這么認(rèn)為，每次我都需要從對(duì)手給我選擇的最差（min）局面中選出最好（max）的一個(gè)，這就是這個(gè)算法名稱 minimax 的意義。

（圖片來(lái)自于 http://web.cs.ucla.edu/~rosen...）

我們接下來(lái)會(huì)解決這樣一個(gè)問(wèn)題，如上圖所示，正方形的節(jié)點(diǎn)對(duì)應(yīng)于我的決策，圓形的節(jié)點(diǎn)是對(duì)手的決策。雙方輪流選擇一個(gè)分支，我的目標(biāo)是讓最后選出的數(shù)字盡可能大，對(duì)方的目標(biāo)是讓這個(gè)數(shù)字盡可能小。

為了簡(jiǎn)單起見，對(duì)于這個(gè)特定的問(wèn)題，我用了一個(gè)嵌套的數(shù)組來(lái)表示狀態(tài)樹。

const dataTree = [
    [
        [
            [3, 17], [2, 12]
        ],
        [
            [15], [25, 0]
        ]
    ],
    [
        [
            [2, 5], [3]
        ],
        [
            [2, 14]
        ]
    ]
];

圖中的節(jié)點(diǎn)分為兩種類型：

Max 節(jié)點(diǎn)：圖中的正方形節(jié)點(diǎn)，對(duì)應(yīng)于我的回合，它會(huì)選取所有子節(jié)點(diǎn)中的最大值作為自身的值

Min 節(jié)點(diǎn)：圖中的圓形節(jié)點(diǎn)，對(duì)應(yīng)于對(duì)手的回合，它會(huì)選取所有子節(jié)點(diǎn)中的最小值作為自身的值

先定義一個(gè) Node 類，constructor 如下：

constructor(data, type, depth) {
    this.data = data;
    this.type = type; // 區(qū)分此節(jié)點(diǎn)的種類是 max 或 min
    this.depth = depth;
}

根節(jié)點(diǎn)的 depth 為0，以下的每一層 depth 依次加一。最底層的節(jié)點(diǎn) depth 為4，其 data 是寫在圖中的數(shù)字，其它層節(jié)點(diǎn)的 data 均是一個(gè)數(shù)組。

接下來(lái)考慮如何給每個(gè)節(jié)點(diǎn)打分，可能會(huì)出現(xiàn)這樣的幾種情況：

最底層的節(jié)點(diǎn)，直接返回本身的數(shù)字

中間層的 max 節(jié)點(diǎn)，返回子節(jié)點(diǎn)中的最大分?jǐn)?shù)

中間層的 min 節(jié)點(diǎn)，返回子節(jié)點(diǎn)中的最小分?jǐn)?shù)

為方便描述，我們按照由上到下、由左到右的順序給圖中節(jié)點(diǎn)進(jìn)行標(biāo)號(hào)。節(jié)點(diǎn)1是 max 節(jié)點(diǎn)，從節(jié)點(diǎn)2和節(jié)點(diǎn)3中選擇較大值；而對(duì)于節(jié)點(diǎn)2來(lái)說(shuō)，需要從節(jié)點(diǎn)4，5中選取較小值。很顯然，我們這里要用遞歸的方法來(lái)實(shí)現(xiàn)，當(dāng)搜索到最底層的節(jié)點(diǎn)時(shí)，遞歸過(guò)程開始返回。

以下是打分函數(shù) score 的具體代碼：

score() {
    // 到達(dá)了最大深度后，此時(shí)的 data 是數(shù)組最內(nèi)層的數(shù)字
    if (this.depth >= 4) {
        return this.data;
    }

    // 對(duì)于 max 節(jié)點(diǎn)，返回的是子節(jié)點(diǎn)中的最大值
    if (this.type === "max") {
        let maxScore = -1000;

        for (let i = 0; i < this.data.length; i++) {
            const d = this.data[i];
            // 生成新的節(jié)點(diǎn)，子節(jié)點(diǎn)的 type 會(huì)和父節(jié)點(diǎn)不同
            const childNode = new Node(d, changeType(this.type), this.depth + 1);
            // 遞歸獲取其分?jǐn)?shù)
            const childScore = childNode.score();

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

        return maxScore;
    }

    // 對(duì)于 min 節(jié)點(diǎn)，返回的是子節(jié)點(diǎn)中的最小值
    else if (this.type === "min") {
        // 與上方代碼相似，省略部分代碼
    }
}

完整的 minimax 算法代碼

Alpha-beta 剪枝算法可以認(rèn)為是 minimax 算法的一種改進(jìn)，在實(shí)際的問(wèn)題中，需要搜索的狀態(tài)數(shù)量將會(huì)非常龐大，利用 alpha-beta 剪枝算法可以去除一些不必要的搜索。

關(guān)于 alpha-beta 算法的具體解釋可以看這篇文章 Minimax with Alpha Beta Pruning。我們?cè)谇拔闹锌紤]的那張圖就來(lái)自這篇文章，之后我們會(huì)用 alpha-beta 剪枝算法來(lái)改進(jìn)之前的解決方案。

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

每一個(gè)節(jié)點(diǎn)都會(huì)由 alpha 和 beta 兩個(gè)值來(lái)確定一個(gè)范圍 [alpha, beta]，alpha 值代表的是下界，beta 代表的是上界。每搜索一個(gè)子節(jié)點(diǎn)，都會(huì)按規(guī)則對(duì)范圍進(jìn)行修正。

Max 節(jié)點(diǎn)可以修改 alpha 值，min 節(jié)點(diǎn)修改 beta 值。

如果出現(xiàn)了 beta <= alpha 的情況，則不用搜索更多的子樹了，未搜索的這部分子樹將被忽略，這個(gè)操作就被稱作剪枝（pruning）。

接下來(lái)我會(huì)盡量說(shuō)明為什么剪枝這個(gè)操作是合理的，省略了一部分節(jié)點(diǎn)為什么不會(huì)對(duì)結(jié)果產(chǎn)生影響。用原圖中以4號(hào)節(jié)點(diǎn)（第三層的第一個(gè)節(jié)點(diǎn)）為根節(jié)點(diǎn)的子樹來(lái)舉例，方便描述這里將他們用 A - G 的字母來(lái)重新標(biāo)記。

從 B 節(jié)點(diǎn)看起，B 是 min 節(jié)點(diǎn)，需要在 D 和 E 中尋找較小值，因此 B 取值為3，同時(shí) B 的 beta 值也設(shè)置為 3。假設(shè) B 還有更多值大于3的子節(jié)點(diǎn)，但因?yàn)橐呀?jīng)出現(xiàn)了 D 這個(gè)最小值，所以不會(huì)對(duì) B 產(chǎn)生影響，即這里的 beta = 3 確定了一個(gè)上界。

.A 是 max 節(jié)點(diǎn)，需要在 B 和 C 中找到較大值，因?yàn)樽訕?B 已經(jīng)搜索完畢，B 的值確定為 3，所以 A 的值至少為 3，這樣確定了 A 的下界 alpha = 3。在搜索 C 子樹之前，我們希望 C 的值大于3，這樣才會(huì)對(duì) A 的下界 alpha 產(chǎn)生影響。于是 C 從 A 這里獲得了下界 alpha = 3 這個(gè)限制條件。

.C 是 min 節(jié)點(diǎn)，要從 F 和 G 里找出較小值。F 的值為2，所以 C 的值一定小于等于 2，更新 C 的上界 beta = 2。此時(shí) C 的 alpha = 3, beta = 2，這是一個(gè)空區(qū)間，也就是說(shuō)即使繼續(xù)考慮 C 的其它子節(jié)點(diǎn)， 也不可能讓 C 的值大于 3，所以我們不必再考慮 G 節(jié)點(diǎn)。G 節(jié)點(diǎn)就是被剪枝的節(jié)點(diǎn)。

重復(fù)這樣的過(guò)程，會(huì)有更多的節(jié)點(diǎn)因?yàn)榧糁Σ僮鞅缓雎裕瑥亩鴮?duì) minimax 算法進(jìn)行了優(yōu)化。

接下來(lái)討論如何修改前面實(shí)現(xiàn)的 minimax 算法，使其變?yōu)?alpha-beta 剪枝算法。

第一步在 constructor 中加入兩個(gè)新屬性，alpha、beta。

constructor(data, type, depth, alpha, beta) {
    this.data = data;
    this.type = type; // 區(qū)分此節(jié)點(diǎn)的種類是 max 或 min
    this.depth = depth;

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

然后每次都搜索會(huì)視情況更新 alpha, beta 的值，以下的代碼片段來(lái)自于搜索 max 節(jié)點(diǎn)的過(guò)程：

// alphabeta.js 中的 score() 函數(shù)

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

    if (childScore > maxScore) {
        maxScore = childScore;
        // 相對(duì)于 minimax 算法，alpha-beta 剪枝算法在這里增加了一個(gè)更新 alpha 值的操作
        this.alpha = maxScore;
    }

    // 如果滿足了退出的條件，我們不需要繼續(xù)搜索更多的節(jié)點(diǎn)了，退出循環(huán)
    if (this.alpha >= this.beta) {
        break;
    }

相對(duì)應(yīng)的是在 min 節(jié)點(diǎn)中，我們更新的將是 beta 值。好了，只需要做這么些簡(jiǎn)單的改變，就將 minimax 算法改變成了 alpha-beta 剪枝算法了。

最后看看如何將算法應(yīng)用到 tic-tac-toe 游戲中。

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

Tic-tac-toe，即井字棋游戲，規(guī)則是在雙方輪流在 3x3 的棋盤上的任意位置下子，率先將三子連成一線的一方獲勝。

這就是一個(gè)非常適合用 minimax 來(lái)解決的問(wèn)題，即使在不考慮對(duì)稱的情況，所有的游戲狀態(tài)也只有 9! = 362880 種，相比于其它棋類游戲天文數(shù)字般的狀態(tài)數(shù)量已經(jīng)很少了，因而很適合作為算法的示例。

我在代碼中將棋盤的狀態(tài)用一個(gè)長(zhǎng)度為9的數(shù)組來(lái)表示，然后利用 canvas 繪制出一個(gè)簡(jiǎn)易的棋盤，下子的過(guò)程就是修改數(shù)組的對(duì)應(yīng)位置然后重繪畫面。

現(xiàn)在我們已經(jīng)有了現(xiàn)成的 minimax 和 alpha-beta 剪枝算法，只要加上一點(diǎn)兒細(xì)節(jié)就能完成這個(gè)游戲了?。

先來(lái)定義一個(gè) GameState 類，其中保存了游戲的狀態(tài)，對(duì)應(yīng)于之前分析過(guò)程中的節(jié)點(diǎn)，其 constructor 如下：

constructor(board, player, depth, alpha, beta) {
    this.board = board;
    // player 是用字符 X 和 O 來(lái)標(biāo)記當(dāng)前由誰(shuí)下子，以此來(lái)判斷當(dāng)前是 max 還是 min 節(jié)點(diǎn)
    this.playerTurn = player;
    this.depth = depth;

    // 保存分?jǐn)?shù)最高或最低的狀態(tài)，用于確定下一步的棋盤狀態(tài)
    this.choosenState = null;
    this.alpha = alpha || -Infinity;
    this.beta = beta || Infinity;
}

為進(jìn)行游戲，首先需要一個(gè) checkFinish 函數(shù)，檢查游戲是否結(jié)束，結(jié)束時(shí)返回勝利者信息。搜索的過(guò)程是在 getScore 函數(shù)中完成的，每次搜索先檢查游戲是否結(jié)束，平局返回零分，我們的算法是站在 AI 的角度來(lái)考慮的，因此 AI 勝利時(shí)返回10分，AI 失利時(shí)返回-10分。

// alphabeta.js 中的 getScore() 方法

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

接著是對(duì) max 和 min 節(jié)點(diǎn)的分類處理：

// alphabeta.js 中的 getScore() 方法

// 獲得所有可能的位置，利用 shuffle 加入隨機(jī)性
const availablePos = _.shuffle(this.getAvailablePos());

// 對(duì)于 max 節(jié)點(diǎn)，返回的是子節(jié)點(diǎn)中的最大值
if (this.playerTurn === aiToken) {
    let maxScore = -1000;
    let maxIndex = 0;

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

        // 生成一個(gè)新的節(jié)點(diǎn)
        const childState = new GameState(newBoard, changeTurn(this.playerTurn), this.depth + 1, this.alpha, this.beta);
        // 這里開始遞歸調(diào)用 getScore() 函數(shù)
        const childScore = childState.getScore();

        if (childScore > maxScore) {
            maxScore = childScore;
            maxIndex = i;
            // 這里保存產(chǎn)生了最大的分?jǐn)?shù)的節(jié)點(diǎn)，之后會(huì)被用于進(jìn)行下一步
            this.choosenState = childState;
            this.alpha = maxScore;
        }

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

    return maxScore;
}

// min 節(jié)點(diǎn)的處理與上面類似
// ...

完整代碼見alphabeta.js

這樣就簡(jiǎn)單地介紹了 minimax 算法和 alpha-beta 算法，并分別給出了一個(gè)簡(jiǎn)單的實(shí)現(xiàn)，然后在 tic-tac-toe 游戲中應(yīng)用了算法。

文章中所提到的所有代碼可見此項(xiàng)目：Tic-tac-toe-js。其中的 algorithms 文件夾中是兩種算法的簡(jiǎn)單實(shí)現(xiàn)，src 文件中是游戲的代碼。

文章開頭說(shuō)到了這篇文章起源于寫2048游戲項(xiàng)目的過(guò)程中，之后我將 minimax 算法應(yīng)用到了2048游戲的 AI 中，不過(guò)對(duì)于局面的評(píng)估函數(shù)尚不完善，現(xiàn)在 AI 只能勉強(qiáng)合成1024?， 還有很大的改進(jìn)空間。

本文原鏈接