摘要：2016 年，AlphaGo 一連戰(zhàn)勝多位人類職業(yè)圍棋選

手，從此一炮而紅，各種下棋機(jī)器人近幾年也層出不窮。那么，你是否想過要自己做一個呢？

鏈

接：https://zserge.com/posts/carnatus/

聲明：本文為 CSDN 翻譯，未經(jīng)允許禁止轉(zhuǎn)載。

作者 | Serge Zaitsev

譯者 | 彎月 責(zé)編 | 鄭麗媛

出品 | CSDN（ID：CSDNnews）

在這篇文章中，我們來嘗試將國際象棋引擎Sunfish（https://github.com/thomasahle/sunfish）移植到 Go 語言，從而了解國際象棋引擎的工作原理。Sunfish 是一個簡單而又小巧的庫，但下棋水平還不錯。而 Go 是一種簡單且可讀性很強(qiáng)的編程語言，所以我打算將二者強(qiáng)強(qiáng)聯(lián)合。

構(gòu)建國際象棋引擎必須考慮以下三個主要方面：

• 如何表示棋盤（棋格、棋子、走位）。

• 如何判斷輸贏。

• 如何搜索最佳走位。

本文中的代碼片段經(jīng)過了簡化，僅包含核心部分，完整代碼請參見：https://GitHub.com/zserge/carnatus。

棋格與棋子的畫法

首先，我們需要找到一種方便且內(nèi)存使用效率很高的方法來表示棋盤，因為在搜索最優(yōu)走位期間，我們需要將數(shù)千個棋盤保存在內(nèi)存中。

棋盤通常表示為格子的陣列。我們會在傳統(tǒng)的 8×8 棋盤周圍添加一些額外的填充，這樣無效的棋子走位會落入這片填充區(qū)域，免去邊界檢查，并且可以大大簡化代碼。

這里，我們將使用線性數(shù)組。移動距離最長的棋子是馬，移動格數(shù)為 2 格。當(dāng)然，其他走直線的棋子可以移動更遠(yuǎn)的距離，但這些走位可以逐步計算，而且如果走位到達(dá)棋盤邊界，就能更快結(jié)束計算。

所以，我們需要在棋盤周圍添加 2 個棋格大小的填充，即創(chuàng)建一塊 12×12 的棋盤，用一個線性數(shù)組來表示。但其實，我們只需要一塊 12×10 的棋盤，因為上一行最右邊的填充也可以作為下一行最左邊的填充，如下所示（x 代表填充）：

用本文的符號表示的話，“a1”的位置是 9×10 1=91，而“a8”將是“2×10 1”=21。

棋盤數(shù)組中的每個格子代表一個棋子、一個空白棋格或填充。我們可以使用數(shù)字常量來保存這些值，但為了方便調(diào)試，我們使用方便人類閱讀的字符：大寫字母和小寫字母代表棋子，空格為填充，點(diǎn)代表空白棋格，如下所示：

下面，我們來寫代碼：

type Piece bytefunc (p Piece) Value int { ... }func (p Piece) Ours bool { ... }func (p Piece) Flip Piece { ... }type Board [120]piecefunc (b Board) Flip Board { ... }type Square intfunc (s Square) Flip Square { ... }

每個棋子都有其價值。我們需要根據(jù)棋子的價值來評估局勢，并計算哪方會獲勝。一般，兵 = 100，馬 = 280，象 = 320，車 = 479，后 = 929，王應(yīng)該設(shè)置成一個非常大的數(shù)字，至少要大于 8 個后（兵會升變成后） 兩個馬、兩個象和兩個車。這樣就算我們擁有所有這些棋子，只丟了王，結(jié)果依然會被判定為負(fù)。

每種類型都有一個 Flip 方法，其返回值相當(dāng)于在對手行動之前翻轉(zhuǎn)棋盤。對于棋子來說，該方法將改變棋子符號的大小寫。對于空白棋格，該方法將返回119 – s（即從棋盤的另一端開始數(shù)）。對于整個棋盤，該方法將以逆序復(fù)制所有棋子，然后再翻轉(zhuǎn)每個棋子的大小寫。

走位生成器

基本模塊構(gòu)建好后，接下來我們考慮局勢。這里的“局勢”指的是棋盤上的棋子，以及一些額外的棋盤狀態(tài)，例如允許吃過路兵的棋格、妨礙王車易位的棋格、是否允許王車易位等等。為了簡化游戲，我們可以重用 Board 類型，但此處我們來單獨(dú)創(chuàng)建一個 Position 類型，負(fù)責(zé)棋盤走位以及價值的計算。

走位是由兩個棋格構(gòu)成的元組，即棋子移動前所在的棋格和棋子移動后所在的棋格。而局勢指的是一個棋盤、分值、每個玩家的王車易位規(guī)則以及吃過路兵的棋格、王車易位妨礙棋格等。這兩種類型都有一個 Flip 方法。

type Move struct {from Squareto Square}func (m Move) Flip Move { ... }type Position struct {board Board // current boardscore int // board score, the higher the betterwc [2]bool // white castling possibilitiesbc [2]bool // black castling possibilitiesep Square // en-passant square where pawn can be capturedkp Square // king passent during castling, where kind can be captured}func (p Position) Flip Position { ... }

下面，我們來編寫一個重要的方法：有效走位生成器。我們只關(guān)心白棋，因為黑棋只需要翻轉(zhuǎn)棋盤，然后當(dāng)作白棋來走即可。

為了生成所有的有效走位，我們需要：

• 生成一個列表，列出每個棋子在每個方向上移動一步的結(jié)果；

• 遍歷所有棋格，忽略非白色棋格；

• 對于每個白色棋子向每個有效方向移動一步；

• 如果棋子不是只能移動一步的棋子（不是兵、馬或國王），則一直移動到遇到障礙物為止，如對手的棋子或棋盤填充。

這里的代碼做了簡化，并沒有考慮吃過路兵、王車易位等。完整的實現(xiàn)，請參見 GitHub 代碼庫（https://github.com/zserge/carnatus）。

為了方便閱讀，我們使用常量 N/E/S/W 來表示方向：

const N, E, S, W = -10, 1, 10, -1var directions = map[Piece]Square{\'P\': {N, N N, N W, N E},\'N\': {N N E, E N E, E S E, S S E, S S W, W S W, W N W, N N W},\'B\': {N E, S E, S W, N W},\'R\': {N, E, S, W},\'Q\': {N, E, S, W, N E, S E, S W, N W},\'K\': {N, E, S, W, N E, S E, S W, N W},}func (pos Position) Moves (moves []Move) {for index, p := range pos.board {if !p.ours {continue}i := Square(index)for _, d := range directions[p] {for j := i d; ; j = j d {q := pos.board[j]if q == \' \' || (q != \'.\' && q.ours) {break}if p == \'P\' {if (d == N || d == N N) && q != \'.\' {break}if d == N N && (i < A1 N || pos.board[i N] != \'.\') {break}}moves = append(moves, Move{from: i, to: j})if p == \'P\' || p == \'N\' || p == \'K\' || (q != \' \' && q != \'.\' && !q.ours) {break}}}}return moves

以上就是我們需要考慮的所有國際象棋規(guī)則，根據(jù)這些規(guī)則就能有效移動棋子。下一步是根據(jù)移動后的位置生成新的局勢。具體的代碼如下，注意這里沒有考慮吃過路兵、兵升變、王車易位等：

func (pos Position) Move(m Move) (np Position) {np = posnp.board[m.to] = pos.board[m.from]np.board[m.from] = \'.\'return np.Flip}

這個方法非常簡單，移動棋子，然后將之前的棋格標(biāo)記為空，并翻轉(zhuǎn)棋盤。完整的實現(xiàn)請參見 GitHub，其中包含有關(guān)兵和王的特殊移動。

到這里，我們就可以由兩個玩家來控制下棋了，或者也可以制作一個傻瓜式國際象棋引擎，隨機(jī)下棋直至一方輸?shù)簟?/p>

但是，我們?nèi)绾闻卸ㄝ斱A呢？

棋盤計算

每個棋盤位置都有一個分值。最初，這個分值為零，因為兩個玩家的局勢完全對等。等到一方移動棋子后，棋盤的分值就會發(fā)生改變，具體取決于哪些棋子被吃，以及棋子對局勢的影響。

最簡單的方法是直接數(shù)一數(shù)棋盤上的棋子，并求出棋子價值的總和（減去對手的棋子），這樣我們就能知道何時被將軍，但這個計算太粗糙了。

一種更好且非常簡單的方法是使用棋子棋格表（Piece-Square Tables，簡稱 PST）。我們?yōu)槊總€棋子創(chuàng)建一個表格，大小與棋盤相同，并為每個棋格分配一個價值。這些值是經(jīng)驗值，所以我借用了 Sunfish 引擎中的 PST 值。

事實上，更好的國際象棋引擎會在游戲的過程中修改變 PST 表，因為棋子的價值會隨著時間而改變（棋子在殘局中更有價值）。但是，我們的引擎還是采用較為簡單的處理。

為了計算移動后的局勢，我們需要：

• 取當(dāng)前位置的分值；

• 減去移動棋子的 PST 值；

• 加上新的 PST 值；

• 如果吃掉了棋子，則加上相應(yīng)的價值。

此外，我們需要在王車易位時調(diào)整車的 PST 值，并在吃過路兵或兵升變時調(diào)整兵的 PST 值。但本文中省略了：

var pst = map[Piece][120]int{\'P\': { ... },\'N\': { ... },\'B\': { ... },\'R\': { ... },\'Q\': { ... },\'K\': { .... },}func (pos Position) value(m Move) int {i, j := m.from, m.top, q := Piece(pos.board[i]), Piece(pos.board[j])// Adjust PST for the moving piecescore := pst[p][j] - pst[p][i]if q != \'.\' && q != \' \' && !q.ours {// Adjsut PST for captured piecescore = pst[q.Flip()][j.Flip()]}return score}

這樣引擎的改進(jìn)就完成了，它能夠選擇最佳走位，而不是隨機(jī)走位了。實際上，真正的國際象棋引擎會更進(jìn)一步，分析每一方可能的走法，并從最長遠(yuǎn)的角度找到最佳走法。

搜索算法

娛樂性質(zhì)的國際象棋引擎中，最流行的搜索算法是深度優(yōu)先搜索。我們從根開始，下降到一定的深度，迭代所有可能的走位，然后回溯。對于每個可能的走位，我們使用“Alpha-beta 剪枝”的“極小化極大算法”計算局勢的分值。

“極小化極大算法”是一種規(guī)則，可將最壞情況下的潛在損失降至最低，這里玩家需要考慮對手的所有最優(yōu)走位，并選擇在對手采用最佳策略的情況下得分最高的走位。

單一的“極小化極大算法”對于國際象棋引擎來說太慢了，因為它需要深入迭代太多的走位，才能找到最優(yōu)解。我們可以利用“Alpha-beta 剪枝”刪除沒必要考慮到節(jié)點(diǎn)，從而提高“極小化極大算法”的速度。

“Alpha-beta 剪枝”的基本思路如下：假設(shè)你正在下棋，發(fā)現(xiàn)了很好的一步 A，而后發(fā)現(xiàn) B 似乎更好。但經(jīng)過深入思考后，你發(fā)現(xiàn)如果選擇 B，對手會在幾步之內(nèi)將死你。所以，你根本不會考慮 B，也不會浪費(fèi)時間去調(diào)查 B 的其他可能結(jié)果。

“Alpha-beta 剪枝”和“極小化極大算法”對于理解國際象棋引擎的工作原理非常重要。Sunfish 引擎使用的是改進(jìn)后的 MDF(f) 搜索算法，這也是帶有剪枝的極小極大算法的變體。

我們的引擎將逐漸增加搜索深度，并調(diào)用 MDF(f) 算法來查找最佳分值的下限和上限。MDF(f) 算法將使用帶局勢緩存的 A/B 修剪迭代——局勢緩存是一種緩存，用于保存每個棋盤的局勢，以及移動到該位置的深度、得分和走位。之后，在考慮一個新局勢時，我們就可以先從局勢表中查找。

這里省略了搜索算法的代碼，實際上其中只包含幾行遞歸搜索。完整的源代碼請參見 GitHhub。

下一步

如果你對小型的國際象棋引擎感興趣，我強(qiáng)烈建議你試試看 Sunfish。

最后，我在這個用 Go 語言編寫的引擎中添加了一個 UCI 協(xié)議實現(xiàn)，并結(jié)合了PyChess UI。雖然這個引擎十分粗糙，需要改進(jìn)的地方很多，但此次嘗試非常有趣，我真的親手實現(xiàn)了一個可以玩的國際象棋程序。