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

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

鏈

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

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

作者 | Serge Zaitsev

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

出品 | CSDN（ID：CSDNnews）

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

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

• 如何表示棋盤(pán)（棋格、棋子、走位）。

• 如何判斷輸贏。

• 如何搜索最佳走位。

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

棋格與棋子的畫(huà)法

首先，我們需要找到一種方便且內(nèi)存使用效率很高的方法來(lái)表示棋盤(pán)，因?yàn)樵谒阉髯顑?yōu)走位期間，我們需要將數(shù)千個(gè)棋盤(pán)保存在內(nèi)存中。

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

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

所以，我們需要在棋盤(pán)周圍添加 2 個(gè)棋格大小的填充，即創(chuàng)建一塊 12×12 的棋盤(pán)，用一個(gè)線性數(shù)組來(lái)表示。但其實(shí)，我們只需要一塊 12×10 的棋盤(pán)，因?yàn)樯弦恍凶钣疫叺奶畛湟部梢宰鳛橄乱恍凶钭筮叺奶畛?，如下所示（x 代表填充）：

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

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

下面，我們來(lái)寫(xiě)代碼：

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 { ... }

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

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

走位生成器

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

走位是由兩個(gè)棋格構(gòu)成的元組，即棋子移動(dòng)前所在的棋格和棋子移動(dòng)后所在的棋格。而局勢(shì)指的是一個(gè)棋盤(pán)、分值、每個(gè)玩家的王車易位規(guī)則以及吃過(guò)路兵的棋格、王車易位妨礙棋格等。這兩種類型都有一個(gè) 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 { ... }

下面，我們來(lái)編寫(xiě)一個(gè)重要的方法：有效走位生成器。我們只關(guān)心白棋，因?yàn)楹谄逯恍枰D(zhuǎn)棋盤(pán)，然后當(dāng)作白棋來(lái)走即可。

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

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

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

• 對(duì)于每個(gè)白色棋子向每個(gè)有效方向移動(dòng)一步；

• 如果棋子不是只能移動(dòng)一步的棋子（不是兵、馬或國(guó)王），則一直移動(dòng)到遇到障礙物為止，如對(duì)手的棋子或棋盤(pán)填充。

這里的代碼做了簡(jiǎn)化，并沒(méi)有考慮吃過(guò)路兵、王車易位等。完整的實(shí)現(xiàn)，請(qǐng)參見(jiàn) GitHub 代碼庫(kù)（https://github.com/zserge/carnatus）。

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

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ó)際象棋規(guī)則，根據(jù)這些規(guī)則就能有效移動(dòng)棋子。下一步是根據(jù)移動(dòng)后的位置生成新的局勢(shì)。具體的代碼如下，注意這里沒(méi)有考慮吃過(guò)路兵、兵升變、王車易位等：

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

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

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

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

棋盤(pán)計(jì)算

每個(gè)棋盤(pán)位置都有一個(gè)分值。最初，這個(gè)分值為零，因?yàn)閮蓚€(gè)玩家的局勢(shì)完全對(duì)等。等到一方移動(dòng)棋子后，棋盤(pán)的分值就會(huì)發(fā)生改變，具體取決于哪些棋子被吃，以及棋子對(duì)局勢(shì)的影響。

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

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

事實(shí)上，更好的國(guó)際象棋引擎會(huì)在游戲的過(guò)程中修改變 PST 表，因?yàn)槠遄拥膬r(jià)值會(huì)隨著時(shí)間而改變（棋子在殘局中更有價(jià)值）。但是，我們的引擎還是采用較為簡(jiǎn)單的處理。

為了計(jì)算移動(dòng)后的局勢(shì)，我們需要：

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

• 減去移動(dòng)棋子的 PST 值；

• 加上新的 PST 值；

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

此外，我們需要在王車易位時(shí)調(diào)整車的 PST 值，并在吃過(guò)路兵或兵升變時(shí)調(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ī)走位了。實(shí)際上，真正的國(guó)際象棋引擎會(huì)更進(jìn)一步，分析每一方可能的走法，并從最長(zhǎng)遠(yuǎn)的角度找到最佳走法。

搜索算法

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

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

單一的“極小化極大算法”對(duì)于國(guó)際象棋引擎來(lái)說(shuō)太慢了，因?yàn)樗枰钊氲嗟淖呶唬拍苷业阶顑?yōu)解。我們可以利用“Alpha-beta 剪枝”刪除沒(méi)必要考慮到節(jié)點(diǎn)，從而提高“極小化極大算法”的速度。

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

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

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

這里省略了搜索算法的代碼，實(shí)際上其中只包含幾行遞歸搜索。完整的源代碼請(qǐng)參見(jiàn) GitHhub。

下一步

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

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