原文鏈接：A step-by-step guide to building a simple chess AI

我們先來了解一下三妈，在我們創(chuàng)建一個簡單的國際象棋 AI 過程中所會接觸到的一些基本概念：

• 棋子的移動
• 繪制棋盤
• Minimax（極小化極大算法）
• Alpha-beta 剪枝

我們將一步一步將這些加入最終的算法中，并分別展示它們對算法所產(chǎn)生的影響莫绣。

你可以在 Github 上查看最終版本畴蒲。

譯者試了下最終版本，一不小心就被吊打了...??

第一步：棋子的移動和繪制棋盤

這里我們使用 chess.js 和 chessboard.js 分別來控制棋子的移動和繪制棋盤对室。chess.js 庫實現(xiàn)了所有棋子的移動規(guī)則模燥，基于此我們可以根據(jù)棋局狀態(tài)得到棋子所有可能的移動。

根據(jù)輸入的棋盤狀態(tài)生成所有可能的棋子移動

有了以上兩個類庫掩宜，我們就能將精力放在最有趣的事上——創(chuàng)建一個能夠找到最佳移動的 AI蔫骂。

接下來就開始創(chuàng)建這樣一個 AI，我們先創(chuàng)建一個方法牺汤，它會在所有合法的移動中隨機選取一個辽旋。

var calculateBestMove =function(game) {
    //generate all the moves for a given position
    var newGameMoves = game.ugly_moves();
    return newGameMoves[Math.floor(Math.random() * newGameMoves.length)];
};

盡管，這個 AI 像一個剛懂規(guī)則的新手檐迟，但是补胚，我們已經(jīng)可以和它下棋了，這是一個好的開始追迟。

隨機移動，[點擊試玩](https://jsfiddle.net/lhartikk/m14epfwb/4)

第二步：棋盤狀態(tài)評估

現(xiàn)在敦间，我們試著計算在棋局某一狀態(tài)下哪邊更具優(yōu)勢瓶逃，最簡單的方法就是根據(jù)下表來統(tǒng)計棋局剩余棋子權(quán)重束铭。

棋子對應(yīng)權(quán)重表

根據(jù)這個方法，我們就能讓我們的 AI 選擇在棋局某一狀態(tài)下使棋局權(quán)重最高的移動了厢绝。

var calculateBestMove = function (game) {

    var newGameMoves = game.ugly_moves();
    var bestMove = null;
    //use any negative large number
    var bestValue = -9999;

    for (var i = 0; i < newGameMoves.length; i++) {
        var newGameMove = newGameMoves[i];
        game.ugly_move(newGameMove);

        //take the negative as AI plays as black
        var boardValue = -evaluateBoard(game.board())
        game.undo();
        if (boardValue > bestValue) {
            bestValue = boardValue;
            bestMove = newGameMove
        }
    }

    return bestMove;

};

加入了計算權(quán)重后契沫，我們的 AI 就會盡可能地去吃對方的棋子。

盡可能地吃子埠褪，[點擊試玩](https://jsfiddle.net/lhartikk/m5q6fgtb/1/)

第三步：使用極小化極大算法來探索樹

下一步，我們使用 極小化極大算法(Minimax) 來使我們的 AI 能從探索樹中選出最優(yōu)移動挤庇。

首先钞速，我們先根據(jù)給定深度遞歸構(gòu)建棋子所有可能移動的樹，并用上一節(jié)的方法來計算所有子節(jié)點的權(quán)重

然后嫡秕，依據(jù)不同的行棋顏色渴语，父節(jié)點取子節(jié)點的最大或最小值，若白子則取子節(jié)點的最大值返回給父節(jié)點昆咽，反之返回最小值驾凶。

深度為 2 的情況下掷酗，極小化極大算法圖解

var minimax = function (depth, game, isMaximisingPlayer) {
    if (depth === 0) {
        return -evaluateBoard(game.board());
    }
    var newGameMoves = game.ugly_moves();
    if (isMaximisingPlayer) {
        var bestMove = -9999;
        for (var i = 0; i < newGameMoves.length; i++) {
            game.ugly_move(newGameMoves[i]);
            bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
            game.undo();
        }
        return bestMove;
    } else {
        var bestMove = 9999;
        for (var i = 0; i < newGameMoves.length; i++) {
            game.ugly_move(newGameMoves[i]);
            bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer));
            game.undo();
        }
        return bestMove;
    }
};

加入了極小化極大算法之后调违，我們的 AI 已經(jīng)不再是任人宰割了。

加入了極小化極大算法技肩，[點擊試玩](https://jsfiddle.net/lhartikk/m5q6fgtb/1/)

極小化極大算法很大程度上取決于我們能夠探索深度混巧，下一步我們就來優(yōu)化它叙赚。

第四步：Alpha-beta 剪枝

Alpha-beta 剪枝 是對極小化極大算法的一種優(yōu)化，用于減少搜索樹中需要探索的節(jié)點數(shù)插勤。這樣在同樣的資源條件下泳挥，就增加了探索樹的搜索深度然痊。

當(dāng)探索路徑的結(jié)果比之前探索的更糟時，Alpha-beta 剪枝就不再搜索該子樹屉符。它并不影響極小化極大算法的計算結(jié)果剧浸，而是加快極小化極大算法運算速度。無論何種情況筑煮，Alpha-beta 剪枝總是能優(yōu)化計算效率辛蚊，即使，我們最初探索的就是最優(yōu)解真仲。

alpha-beta 剪枝用于極小化極大算法

如下圖所示袋马，通過 alpha-beta 剪枝，我們能顯著減少極小化極大算法的計算次數(shù)秸应。

深度為 4 時碑宴，使用或不使用 alpha-beta 剪枝時的計算次數(shù)

var minimax = function (depth, game, alpha, beta, isMaximisingPlayer) {
    positionCount++;
    if (depth === 0) {
        return -evaluateBoard(game.board());
    }

    var newGameMoves = game.ugly_moves();

    if (isMaximisingPlayer) {
        var bestMove = -9999;
        for (var i = 0; i < newGameMoves.length; i++) {
            game.ugly_move(newGameMoves[i]);
            bestMove = Math.max(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
            game.undo();
            alpha = Math.max(alpha, bestMove);
            if (beta <= alpha) {
                return bestMove;
            }
        }
        return bestMove;
    } else {
        var bestMove = 9999;
        for (var i = 0; i < newGameMoves.length; i++) {
            game.ugly_move(newGameMoves[i]);
            bestMove = Math.min(bestMove, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
            game.undo();
            beta = Math.min(beta, bestMove);
            if (beta <= alpha) {
                return bestMove;
            }
        }
        return bestMove;
    }
};

第五步：升級計算權(quán)重方法

最初計算權(quán)重的方法相當(dāng)簡單就是通過計算棋盤上棋子所對應(yīng)的權(quán)重，單憑這一點無法判斷棋的局勢桑谍。為了改善這一點延柠，我們需要將棋子在棋盤中的位置因素計算在內(nèi)。比如锣披，騎士在棋盤中間就比在棋盤邊緣位置更優(yōu)贞间，這樣它可以有更多的選擇。

這里我們在 chess-programming-wiki 所提供的表格的基礎(chǔ)上稍作修改已適應(yīng)我們的程序雹仿。

棋子位置所對應(yīng)的權(quán)重表

這樣我們的 AI 就已經(jīng)像模像樣了增热，至少從業(yè)余玩家的角度來說。

優(yōu)化后峻仇，[點擊試玩](https://jsfiddle.net/lhartikk/m5q6fgtb/1/)

結(jié)語

總的來說，我們所創(chuàng)造的這個簡單的 AI 不會犯一些愚蠢的錯誤邑商，但依舊缺乏大局觀摄咆。

通過以上我介紹的方法，已經(jīng)能夠使我們的 AI 進(jìn)行基本的對戰(zhàn)人断。最終 AI 部分的代碼（不包括移動棋子）不足 200 行吭从，這意味著它實現(xiàn)來非常簡單。你可以在 Github 上查看最終版本恶迈。

我們還可以繼續(xù)優(yōu)化我們的 AI影锈，比如：

• 落子排序，在 alpha-beta 剪枝的過程中蝉绷，將可能的最優(yōu)解先進(jìn)行探測，從而減少計算量
• 加快遍歷所有落子可能的計算
• 勝負(fù)判定

如果你對此感興趣枣抱，你可以到 chess programming wiki 中發(fā)現(xiàn)更多內(nèi)容熔吗。

感謝閱讀。

更多文章歡迎訪問譯者博客佳晶，已升級為 PWA桅狠，支持離線訪問、訂閱和添加至桌面轿秧。