王新民 編譯
在程式設計之前， 我們先瞭解一些基本的概念， 來幫助我們創建一個簡單的象棋AI機器人：移動生成、棋局評估、最大最小搜索和α-β剪枝搜索過程這四個概念。
在每個步驟中， 我們將會在已有的程式上加入上述經典的象棋程式設計優化技術， 來進行改進我們的象棋機器人。 同時我會向大家演示各種優化參數是怎麼影響演算法的下棋風格和計算速度的。
作者Lauri Hartikka提到：“我已經無法戰勝我創造出來的象棋機器人。 我覺得導致這個結果的原因不是因為我下棋技術太爛， 就是演算法已經足夠優秀。 ”
步驟1：移動生成和棋局視覺化我們將使用chess.js庫實現移動生成功能， 並使用chessboard.js來視覺化棋局。 chess.js庫基本上實現了象棋的所有規則。 基於這個應用庫， 我們可以在給定某個棋局狀態下計算出所有合法操作。
圖1：對移動生成功能進行視覺化：起始位置作為輸入， 輸出是該棋局的所有可能移動.
使用這些庫將有助於我們專注於最核心的任務：創建找到最佳走法的演算法。 接下來先創建一個函數， 該函數能從棋局中所有可能的移動中返回一個隨機移動的結果。
雖然加入這個函數的機器人還不是一個高超的象棋玩家，
圖2：黑色點代表下一步所有的合法移動
步驟2：位置評估現在我們來試試看一下在確定位置上雙方的哪個棋子具有更高的評估強度。 實現這一點的最簡單的方法是使用下表來計算棋局中的相對強度。
通過這個評估表， 我們可以創建一個演算法， 能夠讓棋子選擇具有最高評估分數的移動方向。
目前已經有了不錯的進展， 因為我們的演算法現在已經可以盡可能吃掉對方的棋子。
圖3：借助簡單的評估功能，雙方進行遊戲
步驟3：使用Minimax搜尋樹接下來，我們要利用Minimax（極大極小）搜尋樹演算法，它可以從多種選擇中確定最佳方法。
在該演算法中，能將遞迴樹的所有可能移動探索到給定深度，並且在遞迴樹的子節點處評估該位置的好壞。
之後，我們將子節點的最小值或最大值返回給父節點，父節點通過下步將移動白棋還是黑棋來選擇合適值。也就是說，我們試圖盡可能地減少或最大限度地提高每一級的評估值。
圖4：在人為選擇位置時，視覺化極大極小演算法。白棋的最佳走法是b2-c3，此時能夠達到評估為-50的位置
通過加入極大極小演算法，我們的演算法瞭解象棋的基本策略。
圖5：深度級別為2的極大極小演算法
評估極大極小演算法的有效性，在很大程度上取決於計算性能可以實現的搜索深度。我們接下來的工作是通過優化演算法來加大搜索深度。
步驟4：α-β剪枝搜索α-β剪枝搜索是極小極大演算法的一種優化方法，允許我們忽略搜尋樹中的一些分支，這有助於我們在使用相同的計算資源時更深入地評估極大極小搜尋樹。
α-β剪枝搜索的原理是是如果我們找到比已經發現的動作更糟糕的情況，那我們可以停止評估搜尋樹那一部分的情況。
α-β剪枝搜索不會影響極大極小演算法的結果，而是大大加速其計算過程。
如果我們碰巧剛開始就得到了產生最優操作的路徑，那麼α-β剪枝演算法也更有效。
圖6：我們不需要關注使用α-β剪枝搜索所刪去的分支，以及是否按照規定循序存取搜尋樹
使用α-β剪枝搜索，我們可以顯著提升極大極小演算法的計算速度，如下例所示：
圖7：如果我們要執行深度為4的Minmax演算法，使用α-β剪枝的優化演算法和正常演算法所需要評估的位置數
步驟5：改進評估功能初始的評估功能非常簡單，因為我們只能計算在棋局上發現的資訊。為了改善這一點，我們將棋子的位置也作為評估的一個因素。在實際情況中，棋盤中心的棋子比棋盤邊緣的棋子更好，因為它有更多的選擇，顯得更加活躍。
我們將使用在維琪象棋程式設計中提出的一種棋子價值表。
圖8：對棋子價值表進行視覺化，我們可以根據棋子的位置減少或增加評估值。
通過如上改進，我們已經獲得了象棋機器人，至少已經能夠與業餘玩家進行對戰了。
圖9：加上評估方法和α-β剪枝優化的極大極小演算法表現，設置搜索深度為3。
結論對於一個簡單的象棋機器人，它的優點是不會產生愚蠢的錯誤操作。但是它仍然缺乏對象棋的戰略性理解。
通過上面介紹的方法，我們能夠創建一個象棋機器人，可以和你一起玩象棋。最終的實現代碼只有200行，這意味著這個演算法的基本概念實現起來非常簡單，你可以在GitHub上查看象棋機器人的最終版本。
我們還可以對這個演算法進行深入的改進，例如移動排序、更快的移動生成和對殘局的具體評估等。如果您想瞭解更多關於象棋機器人的資訊，請查看維琪上象棋專案程式，去探索更多關於搜索演算法的優化程式。
今天AI界還有哪些事值得關注？
今天”，看我們全網搜羅的AI行業和研究動態。筆芯❤~qbitbot，如果你研究或者從事AI領域，小助手會把你帶入量子位的交流群裡。
圖3：借助簡單的評估功能，雙方進行遊戲
步驟3：使用Minimax搜尋樹接下來，我們要利用Minimax（極大極小）搜尋樹演算法，它可以從多種選擇中確定最佳方法。
在該演算法中，能將遞迴樹的所有可能移動探索到給定深度，並且在遞迴樹的子節點處評估該位置的好壞。
之後，我們將子節點的最小值或最大值返回給父節點，父節點通過下步將移動白棋還是黑棋來選擇合適值。也就是說，我們試圖盡可能地減少或最大限度地提高每一級的評估值。
圖4：在人為選擇位置時，視覺化極大極小演算法。白棋的最佳走法是b2-c3，此時能夠達到評估為-50的位置
通過加入極大極小演算法，我們的演算法瞭解象棋的基本策略。
圖5：深度級別為2的極大極小演算法
評估極大極小演算法的有效性，在很大程度上取決於計算性能可以實現的搜索深度。我們接下來的工作是通過優化演算法來加大搜索深度。
步驟4：α-β剪枝搜索α-β剪枝搜索是極小極大演算法的一種優化方法，允許我們忽略搜尋樹中的一些分支，這有助於我們在使用相同的計算資源時更深入地評估極大極小搜尋樹。
α-β剪枝搜索的原理是是如果我們找到比已經發現的動作更糟糕的情況，那我們可以停止評估搜尋樹那一部分的情況。
α-β剪枝搜索不會影響極大極小演算法的結果，而是大大加速其計算過程。
如果我們碰巧剛開始就得到了產生最優操作的路徑，那麼α-β剪枝演算法也更有效。
圖6：我們不需要關注使用α-β剪枝搜索所刪去的分支，以及是否按照規定循序存取搜尋樹
使用α-β剪枝搜索，我們可以顯著提升極大極小演算法的計算速度，如下例所示：
圖7：如果我們要執行深度為4的Minmax演算法，使用α-β剪枝的優化演算法和正常演算法所需要評估的位置數
步驟5：改進評估功能初始的評估功能非常簡單，因為我們只能計算在棋局上發現的資訊。為了改善這一點，我們將棋子的位置也作為評估的一個因素。在實際情況中，棋盤中心的棋子比棋盤邊緣的棋子更好，因為它有更多的選擇，顯得更加活躍。
我們將使用在維琪象棋程式設計中提出的一種棋子價值表。
圖8：對棋子價值表進行視覺化，我們可以根據棋子的位置減少或增加評估值。
通過如上改進，我們已經獲得了象棋機器人，至少已經能夠與業餘玩家進行對戰了。
圖9：加上評估方法和α-β剪枝優化的極大極小演算法表現，設置搜索深度為3。
結論對於一個簡單的象棋機器人，它的優點是不會產生愚蠢的錯誤操作。但是它仍然缺乏對象棋的戰略性理解。
通過上面介紹的方法，我們能夠創建一個象棋機器人，可以和你一起玩象棋。最終的實現代碼只有200行，這意味著這個演算法的基本概念實現起來非常簡單，你可以在GitHub上查看象棋機器人的最終版本。
我們還可以對這個演算法進行深入的改進，例如移動排序、更快的移動生成和對殘局的具體評估等。如果您想瞭解更多關於象棋機器人的資訊，請查看維琪上象棋專案程式，去探索更多關於搜索演算法的優化程式。
今天AI界還有哪些事值得關注？
今天”，看我們全網搜羅的AI行業和研究動態。筆芯❤~qbitbot，如果你研究或者從事AI領域，小助手會把你帶入量子位的交流群裡。