摘要：實現這一功能最簡單的方法是計算棋盤上棋子的相對強度大小，用下面的對照表。本鏈接是基于算法優化的國際象棋。我們來稍微調整一下棋盤上棋子狀態的權重，這一圖表是在國際象棋程序維基百科中給出的。

本文作者： Lauri Hartikka 
編譯：胡子大哈 
翻譯原文：http://huziketang.com/blog/posts/  
英文連接：A step-by-step guide to building a simple chess AI

轉載請注明出處，保留原文鏈接以及作者信息

首先讓我們先看幾個對開發簡單國際象棋 AI 很有幫助的概念：

移動生成

局面評估

極大極小算法

α-β 剪枝

每一步中我們都會對經過時間檢驗的國際象棋程序進行改進，我會展示不同算法風格所產生的影響。你也可以在 GitHub 上看到最終的 AI 算法。

使用 chess.js 庫來生成移動規則，使用 chessboard.js 來可視化棋盤。移動生成庫實現了所有國際象棋的規則，對于任意給定的棋盤狀態我們都可以計算出下一步的合法的走棋方法。

(移動生成函數的可視化版本。起始位置作為輸入，輸出是所有可能的走法。)

使用這些庫可以使我們專注于我們所感興趣的任務：開發最佳下棋的算法。我們首先從創建以一個函數開始，在所有可能走法中返回一個隨機的結果。

    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)];
    };

用這種方法，盡管它不是一個合格的棋手，但是起碼我們可以和它玩起來了。

下面我們試著讓它理解在一個確定的位置上怎么走比較好。實現這一功能最簡單的方法是計算棋盤上棋子的相對強度大小，用下面的對照表。

通過評估函數，可以選擇評估結果最佳的走法。

    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;
    
    };

這樣一來，一個切實的改善是，算法會吃掉它可以吃掉的棋子。

（黑子使用了簡單評估算法，在這里可以看到：https://jsfiddle.net/lhartikk...）

接下來我們來創建一個搜索樹，通過它算法可以選擇最佳走法，這里需要用到極大極小算法。

在這個算法中，會根據給定的樹深度對遞歸樹進行遍歷，所要評估的狀態就是樹的葉子節點。

這一步完成以后我們把子節點中的最大或者最小值返回給父節點，這要依賴于白棋還是黑棋來走這一步（這就是說在樹的每一層中都最大或者最小化輸出）。

（給定狀態的最大最小算法的可視化。白棋最好的走法是 b2-c3，因為可以保證獲取一個狀態評估值是 -50）

    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;
        }
    };

有了最大最小步驟以后，我們的算法可以下出一些國際象棋的基本策略了。

極大極小算法的效率取決于搜索樹的深度，這就是我們后面步驟要優化的地方。

Alpha-beta 剪枝是極大極小算法的一種優化方法，可以砍掉搜索樹中的某些分支。這可以幫助我們用同樣的資源的情況下，盡可能深地遍歷極大極小搜索樹。

α-β 剪枝的原理是在遍歷搜索樹的過程中發現可以終止遍歷的狀態，進而把整個分支剪掉的過程。這是因為發現下一步會導致比上一步更糟的結果，那么就不用再遍歷下去了。

α-β 剪枝不影響極大極小算法的結果，僅僅是使極大極小算法運行的更快。假設遍歷時恰巧第一個狀態就是最佳走法，那么 α-β 剪枝會更加有效。

有了 α-β，極大極小算法如虎添翼，可以看下面的例子。

（本圖是給定的起始棋盤狀態，下面的數字是如果遍歷深度是 4 的話，需要評估的狀態總數。）

本鏈接是基于 α-β 算法優化的國際象棋 AI。

初始的評估函數非常簡單，只是數了盤面上的數值而已。下面我們來改善它，把棋子的位置因素也考慮到評估結果里面去。例如在棋盤中間的馬會比在棋盤邊緣的馬位置更好（因為它的可選擇性更多，也更加活躍）。

我們來稍微調整一下棋盤上棋子狀態的權重，這一圖表是在國際象棋程序維基百科中給出的。

（棋盤權值表的可視化。可以根據棋子的位置增加或者減少相應位置的權重）

通過上面的一系列改進，我們的算法可以下出像樣的棋局了，起碼開始像一個業余棋手這樣了。

（改進后的評估函數加上搜索樹深度設置成 3 的 α-β 算法，可以在這個地址看到：https://jsfiddle.net/q76uzxwe/1/）

這個簡單的國際象棋算法不會犯一些很傻的錯誤，但是它依然是缺乏策略理解的。

通過我所介紹的這種方法，可以開發一個國際象棋程序來實現一些基本的玩法。“AI 部分”（不包括移動生成）只有 200 行代碼，也就是說這里只實現了基本的概念。你可以在 GitHub 中獲取最終版本的代碼。

關于算法的一些更深層次的改善可以見下面鏈接：

移動順序

快速移動生成策略

游戲結束策略評估

如果你想要了解更多，查看國際象棋程序維基百科，這里介紹了很多有用的資源，本文只是演示了國際象棋 AI 算法實現的基本步驟。

Happy Coding！如果本文對你有幫助，歡迎關注我的專欄-前端大哈，定期發布高質量前端文章。

我最近正在寫一本《React.js 小書》，對 React.js 感興趣的童鞋，歡迎指點。