首先讓我們先看幾個對開發簡單國際象棋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 的話，需要評估的狀態總數。）
初始的評估函數非常簡單，只是數了盤面上的數值而已。下面我們來改善它，把棋子的位置因素也考慮到評估結果裡面去。例如在棋盤中間的馬會比在棋盤邊緣的馬位置更好（因為它的可選擇性更多，也更加活躍）。
我們來稍微調整一下棋盤上棋子狀態的權重，這一圖表是在國際象棋程序-維基百科中給出的。
（棋盤權值表的可視化。可以根據棋子的位置增加或者減少相應位置的權重）
通過上面的一系列改進，我們的算法可以下出像樣的棋局了，起碼開始像一個業餘棋手這樣了。
（改進後的評估函數加上搜索樹深度設置成3的α-β算法，可以在這個地址看到：https://jsfiddle.net/q76uzxwe/1/）
這個簡單的國際象棋算法不會犯一些很傻的錯誤，但是它依然是缺乏策略理解的。
通過我所介紹的這種方法，可以開發一個國際象棋程序來實現一些基本的玩法。“AI部分”（不包括移動生成）只有200行代碼，也就是說這裡只實現了基本的概念。你可以在GitHub中獲取最終版本的代碼。
如果你想要了解更多，查看國際象棋程序維基百科，這裡介紹了很多有用的資源，本文只是演示了國際象棋AI算法實現的基本步驟。
轉貼自： 36大數據
留下你的回應
以訪客張貼回應