只需五步！手把手教你搭建國際象棋AI機器人
王新民 編譯
量子位 報道 | 公眾號 QbitAI
要創建一個簡單的象棋AI，我們在開始編程之前要先了解四個基本的概念：移動生成、棋局評估、最大最小搜索和α-β剪枝搜索過程。
在每個步驟中，我們將會在已有的程序上加入上述經典的象棋編程優化技術，來進行改進我們的象棋機器人。同時我會向大家演示各種優化參數是怎麼影響演算法的下棋風格和計算速度的。
作者Lauri Hartikka提到：「我已經無法戰勝我創造出來的象棋機器人。我覺得導致這個結果的原因不是因為我下棋技術太爛，就是演算法已經足夠優秀。」
步驟1：移動生成和棋局可視化
我們將使用chess.js庫實現移動生成功能，並使用chessboard.js來可視化棋局。chess.js庫基本上實現了象棋的所有規則。基於這個應用庫，我們可以在給定某個棋局狀態下計算出所有合法操作。
圖1：對移動生成功能進行可視化：起始位置作為輸入，輸出是該棋局的所有可能移動.
使用這些庫將有助於我們專註於最核心的任務：創建找到最佳走法的演算法。接下來先創建一個函數，該函數能從棋局中所有可能的移動中返回一個隨機移動的結果。
步驟2：位置評估
現在我們來試試看一下在確定位置上雙方的哪個棋子具有更高的評估強度。實現這一點的最簡單的方法是使用下表來計算棋局中的相對強度。
通過這個評估表，我們可以創建一個演算法，能夠讓棋子選擇具有最高評估分數的移動方向。
步驟3：使用Minimax搜索樹
接下來，我們要利用Minimax（極大極小）搜索樹演算法，它可以從多種選擇中確定最佳方法。
在該演算法中，能將遞歸樹的所有可能移動探索到給定深度，並且在遞歸樹的子節點處評估該位置的好壞。
之後，我們將子節點的最小值或最大值返回給父節點，父節點通過下步將移動白棋還是黑棋來選擇合適值。也就是說，我們試圖儘可能地減少或最大限度地提高每一級的評估值。
圖5：深度級別為2的極大極小演算法
評估極大極小演算法的有效性，在很大程度上取決於計算性能可以實現的搜索深度。我們接下來的工作是通過優化演算法來加大搜索深度。
步驟4：α-β剪枝搜索
α-β剪枝搜索是極小極大演算法的一種優化方法，允許我們忽略搜索樹中的一些分支，這有助於我們在使用相同的計算資源時更深入地評估極大極小搜索樹。
α-β剪枝搜索的原理是是如果我們找到比已經發現的動作更糟糕的情況，那我們可以停止評估搜索樹那一部分的情況。
α-β剪枝搜索不會影響極大極小演算法的結果，而是大大加速其計算過程。
如果我們碰巧剛開始就得到了產生最優操作的路徑，那麼α-β剪枝演算法也更有效。
使用α-β剪枝搜索，我們可以顯著提升極大極小演算法的計算速度，如下例所示：
步驟5：改進評估功能
初始的評估功能非常簡單，因為我們只能計算在棋局上發現的信息。為了改善這一點，我們將棋子的位置也作為評估的一個因素。在實際情況中，棋盤中心的棋子比棋盤邊緣的棋子更好，因為它有更多的選擇，顯得更加活躍。
我們將使用在維基象棋編程中提出的一種棋子價值表。
通過如上改進，我們已經獲得了象棋機器人，至少已經能夠與業餘玩家進行對戰了。
結論
對於一個簡單的象棋機器人，它的優點是不會產生愚蠢的錯誤操作。但是它仍然缺乏對象棋的戰略性理解。
通過上面介紹的方法，我們能夠創建一個象棋機器人，可以和你一起玩象棋。最終的實現代碼只有200行，這意味著這個演算法的基本概念實現起來非常簡單，你可以在GitHub上查看象棋機器人的最終版本。
我們還可以對這個演算法進行深入的改進，例如移動排序、更快的移動生成和對殘局的具體評估等。如果您想了解更多關於象棋機器人的信息，請查看維基上象棋項目程序，去探索更多關於搜索演算法的優化程序。
今天AI界還有哪些事值得關注？在量子位（QbitAI）公眾號會話界面回復「今天」，看我們全網搜羅的AI行業和研究動態。筆芯?~
想和更多小夥伴一起學習進步，歡迎加量子位小助手的微信：qbitbot，註明「加入門群」，如果是認真學習的好同學，小助手會帶你進群。
推薦閱讀：