象棋编程方面的书籍（《揭秘编程世界中的象棋高手，如何成为智能博弈的佼佼者？》）

摘要：2016 年，alphago 一连战胜多位人类职业围棋选手，从此一炮而红，各种下棋机器人近几年也层出不穷。那么，你是否想过要自己做一个呢？

链接：

在这篇文章中，我们来尝试将国际象棋引擎sunfish（https://github.com/thomasahle/sunfish）移植到 go 语言，从而了解国际象棋引擎的工作原理。sunfish 是一个简单而又小巧的库，但下棋水平还不错。而 go 是一种简单且可读性很强的编程语言，所以我打算将二者强强联合。

构建国际象棋引擎必须考虑以下三个主要方面：

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

• 如何判断输赢。

• 如何搜索最佳走位。

本文中的代码片段经过了简化，仅包含核心部分，完整代码请参见：https://github.com/zserge/carnatus。

棋格与棋子的画法

首先，我们需要找到一种方便且内存使用效率很高的方法来表示棋盘，因为在搜索最优走位期间，我们需要将数千个棋盘保存在内存中。

棋盘通常表示为格子的阵列。我们会在传统的 8x8 棋盘周围添加一些额外的填充，这样无效的棋子走位会落入这片填充区域，免去边界检查，并且可以大大简化代码。

这里，我们将使用线性数组。移动距离最长的棋子是马，移动格数为 2 格。当然，其他走直线的棋子可以移动更远的距离，但这些走位可以逐步计算，而且如果走位到达棋盘边界，就能更快结束计算。

所以，我们需要在棋盘周围添加 2 个棋格大小的填充，即创建一块 12x12 的棋盘，用一个线性数组来表示。但其实，我们只需要一块 12x10 的棋盘，因为上一行最右边的填充也可以作为下一行最左边的填充，如下所示（x 代表填充）：

用本文的符号表示的话，“a1”的位置是 9×10+1=91，而“a8”将是“2×10+1”=21。

棋盘数组中的每个格子代表一个棋子、一个空白棋格或填充。我们可以使用数字常量来保存这些值，但为了方便调试，我们使用方便人类阅读的字符：大写字母和小写字母代表棋子，空格为填充，点代表空白棋格，如下所示：

下面，我们来写代码：

type piece bytefunc (p piece) value() int { ... }func (p piece) ours() bool { ... }func (p piece) flip() piece { ... }type board piecefunc (b board) flip() board { ... }type square intfunc (s square) flip() square { ... }

每个棋子都有其价值。我们需要根据棋子的价值来评估局势，并计算哪方会获胜。一般，兵 = 100，马 = 280，象 = 320，车 = 479，后 = 929，王应该设置成一个非常大的数字，至少要大于 8 个后（兵会升变成后）+ 两个马、两个象和两个车。这样就算我们拥有所有这些棋子，只丢了王，结果依然会被判定为负。

每种类型都有一个 flip() 方法，其返回值相当于在对手行动之前翻转棋盘。对于棋子来说，该方法将改变棋子符号的大小写。对于空白棋格，该方法将返回119 - s（即从棋盘的另一端开始数）。对于整个棋盘，该方法将以逆序复制所有棋子，然后再翻转每个棋子的大小写。

走位生成器

基本模块构建好后，接下来我们考虑局势。这里的“局势”指的是棋盘上的棋子，以及一些额外的棋盘状态，例如允许吃过路兵的棋格、妨碍王车易位的棋格、是否允许王车易位等等。为了简化游戏，我们可以重用 board 类型，但此处我们来单独创建一个 position 类型，负责棋盘走位以及价值的计算。

走位是由两个棋格构成的元组，即棋子移动前所在的棋格和棋子移动后所在的棋格。而局势指的是一个棋盘、分值、每个玩家的王车易位规则以及吃过路兵的棋格、王车易位妨碍棋格等。这两种类型都有一个 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 bool // white castling possibilitiesbc 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 { ... }

下面，我们来编写一个重要的方法：有效走位生成器。我们只关心白棋，因为黑棋只需要翻转棋盘，然后当作白棋来走即可。

为了生成所有的有效走位，我们需要：

• 生成一个列表，列出每个棋子在每个方向上移动一步的结果；

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

• 对于每个白色棋子向每个有效方向移动一步；

• 如果棋子不是只能移动一步的棋子（不是兵、马或国王），则一直移动到遇到障碍物为止，如对手的棋子或棋盘填充。

这里的代码做了简化，并没有考虑吃过路兵、王车易位等。完整的实现，请参见 github 代码库（https://github.com/zserge/carnatus）。

为了方便阅读，我们使用常量 n/e/s/w 来表示方向：

const n, e, s, w = -10, 1, 10, -1var directions = mapsquare{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 {for j := i + d; ; j = j + d {q := pos.boardif 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 != .) {break}}moves = append(moves, move{from: i, to: j})if p == p || p == n || p == k || (q !=   q != . !q.ours()) {break}}}}return moves

以上就是我们需要考虑的所有国际象棋规则，根据这些规则就能有效移动棋子。下一步是根据移动后的位置生成新的局势。具体的代码如下，注意这里没有考虑吃过路兵、兵升变、王车易位等：

func (pos position) move(m move) (np position) {np = posnp.board = pos.boardnp.board = .return np.flip()}

这个方法非常简单，移动棋子，然后将之前的棋格标记为空，并翻转棋盘。完整的实现请参见 github，其中包含有关兵和王的特殊移动。

到这里，我们就可以由两个玩家来控制下棋了，或者也可以制作一个傻瓜式国际象棋引擎，随机下棋直至一方输掉。

但是，我们如何判定输赢呢？

棋盘计算

每个棋盘位置都有一个分值。最初，这个分值为零，因为两个玩家的局势完全对等。等到一方移动棋子后，棋盘的分值就会发生改变，具体取决于哪些棋子被吃，以及棋子对局势的影响。

最简单的方法是直接数一数棋盘上的棋子，并求出棋子价值的总和（减去对手的棋子），这样我们就能知道何时被将军，但这个计算太粗糙了。

一种更好且非常简单的方法是使用棋子棋格表（piece-square tables，简称 pst）。我们为每个棋子创建一个表格，大小与棋盘相同，并为每个棋格分配一个价值。这些值是经验值，所以我借用了 sunfish 引擎中的 pst 值。

事实上，更好的国际象棋引擎会在游戏的过程中修改变 pst 表，因为棋子的价值会随着时间而改变（棋子在残局中更有价值）。但是，我们的引擎还是采用较为简单的处理。

为了计算移动后的局势，我们需要：

• 取当前位置的分值；

• 减去移动棋子的 pst 值；

• 加上新的 pst 值；

• 如果吃掉了棋子，则加上相应的价值。

此外，我们需要在王车易位时调整车的 pst 值，并在吃过路兵或兵升变时调整兵的 pst 值。但本文中省略了：

var pst = mapint{p: { ... },n: { ... },b: { ... },r: { ... },q: { ... },k: { .... },}func (pos position) value(m move) int {i, j := m.from, m.top, q := piece(pos.board), piece(pos.board)// adjust pst for the moving piecescore := pst - pstif q != . q != !q.ours() {// adjsut pst for captured piecescore += pst}return score}

这样引擎的改进就完成了，它能够选择最佳走位，而不是随机走位了。实际上，真正的国际象棋引擎会更进一步，分析每一方可能的走法，并从最长远的角度找到最佳走法。

搜索算法

娱乐性质的国际象棋引擎中，最流行的搜索算法是深度优先搜索。我们从根开始，下降到一定的深度，迭代所有可能的走位，然后回溯。对于每个可能的走位，我们使用“alpha-beta 剪枝”的“极小化极大算法”计算局势的分值。

“极小化极大算法”是一种规则，可将最坏情况下的潜在损失降至最低，这里玩家需要考虑对手的所有最优走位，并选择在对手采用最佳策略的情况下得分最高的走位。

单一的“极小化极大算法”对于国际象棋引擎来说太慢了，因为它需要深入迭代太多的走位，才能找到最优解。我们可以利用“alpha-beta 剪枝”删除没必要考虑到节点，从而提高“极小化极大算法”的速度。

“alpha-beta 剪枝”的基本思路如下：假设你正在下棋，发现了很好的一步 a，而后发现 b 似乎更好。但经过深入思考后，你发现如果选择 b，对手会在几步之内将死你。所以，你根本不会考虑 b，也不会浪费时间去调查 b 的其他可能结果。

“alpha-beta 剪枝”和“极小化极大算法”对于理解国际象棋引擎的工作原理非常重要。sunfish 引擎使用的是改进后的 mdf(f) 搜索算法，这也是带有剪枝的极小极大算法的变体。

我们的引擎将逐渐增加搜索深度，并调用 mdf(f) 算法来查找最佳分值的下限和上限。mdf(f) 算法将使用带局势缓存的 a/b 修剪迭代——局势缓存是一种缓存，用于保存每个棋盘的局势，以及移动到该位置的深度、得分和走位。之后，在考虑一个新局势时，我们就可以先从局势表中查找。

这里省略了搜索算法的代码，实际上其中只包含几行递归搜索。完整的源代码请参见 githhub。

下一步

如果你对小型的国际象棋引擎感兴趣，我强烈建议你试试看 sunfish。

最后，我在这个用 go 语言编写的引擎中添加了一个 uci 协议实现，并结合了pychess ui。虽然这个引擎十分粗糙，需要改进的地方很多，但此次尝试非常有趣，我真的亲手实现了一个可以玩的国际象棋程序。