摘要：我們在前文中考慮的那張圖就來自這篇文章，之后我們會用剪枝算法來改進之前的解決方案。剪枝算法的實現接下來討論如何修改前面實現的算法，使其變為剪枝算法。現在我們已經有了現成的和剪枝算法，只要加上一點兒細節就能完成這個游戲了。

前段時間用 React 寫了個2048 游戲來練練手，準備用來回顧下 React 相關的各種技術，以及試驗一下新技術。在寫這個2048的過程中，我考慮是否可以在其中加入一個 AI 算法來自動進行游戲，于是我找到了這篇文章：2048-AI程序算法分析，文中介紹了 minimax 算法和 alpha-beta 剪枝算法。于是我決定先學習下這兩種算法，并以此寫了這個 tic-tac-toe 游戲：tic-tac-toe-js（代碼見此處）。本文將說明如何用 JavaScript 來簡單地實現算法，并將其運用到 tic-tac-toe 游戲中。

我覺得要解釋 minimax 算法的原理，需要用示意圖來解釋更清晰，以下的幾篇文章都對原理說的足夠清楚。

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

其中后面的兩篇文章都是以 tic-tac-toe 游戲為例，并用 Ruby 實現。

以棋類游戲為例來說明 minimax 算法，每一個棋盤的狀態都會對應一個分數。雙方將會輪流下棋。輪到我方下子時，我會選擇分數最高的狀態；而對方會選擇對我最不利的狀態。可以這么認為，每次我都需要從對手給我選擇的最差（min）局面中選出最好（max）的一個，這就是這個算法名稱 minimax 的意義。

（圖片來自于 http://web.cs.ucla.edu/~rosen...）

我們接下來會解決這樣一個問題，如上圖所示，正方形的節點對應于我的決策，圓形的節點是對手的決策。雙方輪流選擇一個分支，我的目標是讓最后選出的數字盡可能大，對方的目標是讓這個數字盡可能小。

為了簡單起見，對于這個特定的問題，我用了一個嵌套的數組來表示狀態樹。

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

圖中的節點分為兩種類型：

Max 節點：圖中的正方形節點，對應于我的回合，它會選取所有子節點中的最大值作為自身的值

Min 節點：圖中的圓形節點，對應于對手的回合，它會選取所有子節點中的最小值作為自身的值

先定義一個 Node 類，constructor 如下：

constructor(data, type, depth) {
    this.data = data;
    this.type = type; // 區分此節點的種類是 max 或 min
    this.depth = depth;
}

根節點的 depth 為0，以下的每一層 depth 依次加一。最底層的節點 depth 為4，其 data 是寫在圖中的數字，其它層節點的 data 均是一個數組。

接下來考慮如何給每個節點打分，可能會出現這樣的幾種情況：

最底層的節點，直接返回本身的數字

中間層的 max 節點，返回子節點中的最大分數

中間層的 min 節點，返回子節點中的最小分數

為方便描述，我們按照由上到下、由左到右的順序給圖中節點進行標號。節點1是 max 節點，從節點2和節點3中選擇較大值；而對于節點2來說，需要從節點4，5中選取較小值。很顯然，我們這里要用遞歸的方法來實現，當搜索到最底層的節點時，遞歸過程開始返回。

以下是打分函數 score 的具體代碼：

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 剪枝算法可以認為是 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 算法進行了優化。

接下來討論如何修改前面實現的 minimax 算法，使其變為 alpha-beta 剪枝算法。

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

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 節點的過程：

// 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，即井字棋游戲，規則是在雙方輪流在 3x3 的棋盤上的任意位置下子，率先將三子連成一線的一方獲勝。

這就是一個非常適合用 minimax 來解決的問題，即使在不考慮對稱的情況，所有的游戲狀態也只有 9! = 362880 種，相比于其它棋類游戲天文數字般的狀態數量已經很少了，因而很適合作為算法的示例。

我在代碼中將棋盤的狀態用一個長度為9的數組來表示，然后利用 canvas 繪制出一個簡易的棋盤，下子的過程就是修改數組的對應位置然后重繪畫面。

現在我們已經有了現成的 minimax 和 alpha-beta 剪枝算法，只要加上一點兒細節就能完成這個游戲了?。

先來定義一個 GameState 類，其中保存了游戲的狀態，對應于之前分析過程中的節點，其 constructor 如下：

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分。

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

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

接著是對 max 和 min 節點的分類處理：

// 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?， 還有很大的改進空間。

本文原鏈接