摘要:2016 年,AlphaGo 一连战胜多位人类职业围棋选
手,从此一炮而红,各种下棋机器人近几年也层出不穷。那么,你是否想过要自己做一个呢?
链
接:https://zserge.com/posts/carnatus/
声明:本文为 CSDN 翻译,未经允许禁止转载。
作者 | Serge Zaitsev
译者 | 弯月 责编 | 郑丽媛
出品 | CSDN(ID:CSDNnews)
在这篇文章中,我们来尝试将国际象棋引擎Sunfish(https://github.com/thomasahle/sunfish)移植到 Go 语言,从而了解国际象棋引擎的工作原理。Sunfish 是一个简单而又小巧的库,但下棋水平还不错。而 Go 是一种简单且可读性很强的编程语言,所以我打算将二者强强联合。
构建国际象棋引擎必须考虑以下三个主要方面:
-
如何表示棋盘(棋格、棋子、走位)。
如何判断输赢。
如何搜索最佳走位。
本文中的代码片段经过了简化,仅包含核心部分,完整代码请参见:https://GitHub.com/zserge/carnatus。
棋格与棋子的画法
首先,我们需要找到一种方便且内存使用效率很高的方法来表示棋盘,因为在搜索最优走位期间,我们需要将数千个棋盘保存在内存中。
棋盘通常表示为格子的阵列。我们会在传统的 8×8 棋盘周围添加一些额外的填充,这样无效的棋子走位会落入这片填充区域,免去边界检查,并且可以大大简化代码。
这里,我们将使用线性数组。移动距离最长的棋子是马,移动格数为 2 格。当然,其他走直线的棋子可以移动更远的距离,但这些走位可以逐步计算,而且如果走位到达棋盘边界,就能更快结束计算。
所以,我们需要在棋盘周围添加 2 个棋格大小的填充,即创建一块 12×12 的棋盘,用一个线性数组来表示。但其实,我们只需要一块 12×10 的棋盘,因为上一行最右边的填充也可以作为下一行最左边的填充,如下所示(x 代表填充):
用本文的符号表示的话,“a1”的位置是 9×10 1=91,而“a8”将是“2×10 1”=21。
棋盘数组中的每个格子代表一个棋子、一个空白棋格或填充。我们可以使用数字常量来保存这些值,但为了方便调试,我们使用方便人类阅读的字符:大写字母和小写字母代表棋子,空格为填充,点代表空白棋格,如下所示:
下面,我们来写代码:
type Piece byte
func (p Piece) Value int { ... }
func (p Piece) Ours bool { ... }
func (p Piece) Flip Piece { ... }
type Board [120]piece
func (b Board) Flip Board { ... }
type Square int
func (s Square) Flip Square { ... }
每个棋子都有其价值。我们需要根据棋子的价值来评估局势,并计算哪方会获胜。一般,兵 = 100,马 = 280,象 = 320,车 = 479,后 = 929,王应该设置成一个非常大的数字,至少要大于 8 个后(兵会升变成后) 两个马、两个象和两个车。这样就算我们拥有所有这些棋子,只丢了王,结果依然会被判定为负。
每种类型都有一个 Flip 方法,其返回值相当于在对手行动之前翻转棋盘。对于棋子来说,该方法将改变棋子符号的大小写。对于空白棋格,该方法将返回119 – s(即从棋盘的另一端开始数)。对于整个棋盘,该方法将以逆序复制所有棋子,然后再翻转每个棋子的大小写。
走位生成器
基本模块构建好后,接下来我们考虑局势。这里的“局势”指的是棋盘上的棋子,以及一些额外的棋盘状态,例如允许吃过路兵的棋格、妨碍王车易位的棋格、是否允许王车易位等等。为了简化游戏,我们可以重用 Board 类型,但此处我们来单独创建一个 Position 类型,负责棋盘走位以及价值的计算。
走位是由两个棋格构成的元组,即棋子移动前所在的棋格和棋子移动后所在的棋格。而局势指的是一个棋盘、分值、每个玩家的王车易位规则以及吃过路兵的棋格、王车易位妨碍棋格等。这两种类型都有一个 Flip 方法。
type Move struct {
from Square
to Square
}
func (m Move) Flip Move { ... }
type Position struct {
board Board // current board
score int // board score, the higher the better
wc [2]bool // white castling possibilities
bc [2]bool // black castling possibilities
ep Square // en-passant square where pawn can be captured
kp 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, -1
var 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
以上就是我们需要考虑的所有国际象棋规则,根据这些规则就能有效移动棋子。下一步是根据移动后的位置生成新的局势。具体的代码如下,注意这里没有考虑吃过路兵、兵升变、王车易位等:
func (pos Position) Move(m Move) (np Position) {
np = pos
np.board[m.to] = pos.board[m.from]
np.board[m.from] = \'.\'
return np.Flip
}
这个方法非常简单,移动棋子,然后将之前的棋格标记为空,并翻转棋盘。完整的实现请参见 GitHub,其中包含有关兵和王的特殊移动。
到这里,我们就可以由两个玩家来控制下棋了,或者也可以制作一个傻瓜式国际象棋引擎,随机下棋直至一方输掉。
但是,我们如何判定输赢呢?
棋盘计算
每个棋盘位置都有一个分值。最初,这个分值为零,因为两个玩家的局势完全对等。等到一方移动棋子后,棋盘的分值就会发生改变,具体取决于哪些棋子被吃,以及棋子对局势的影响。
最简单的方法是直接数一数棋盘上的棋子,并求出棋子价值的总和(减去对手的棋子),这样我们就能知道何时被将军,但这个计算太粗糙了。
一种更好且非常简单的方法是使用棋子棋格表(Piece-Square Tables,简称 PST)。我们为每个棋子创建一个表格,大小与棋盘相同,并为每个棋格分配一个价值。这些值是经验值,所以我借用了 Sunfish 引擎中的 PST 值。
事实上,更好的国际象棋引擎会在游戏的过程中修改变 PST 表,因为棋子的价值会随着时间而改变(棋子在残局中更有价值)。但是,我们的引擎还是采用较为简单的处理。
为了计算移动后的局势,我们需要:
-
取当前位置的分值;
减去移动棋子的 PST 值;
加上新的 PST 值;
如果吃掉了棋子,则加上相应的价值。
此外,我们需要在王车易位时调整车的 PST 值,并在吃过路兵或兵升变时调整兵的 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.to
p, q := Piece(pos.board[i]), Piece(pos.board[j])
// Adjust PST for the moving piece
score := pst[p][j] - pst[p][i]
if q != \'.\' && q != \' \' && !q.ours {
// Adjsut PST for captured piece
score = pst[q.Flip()][j.Flip()]
}
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。虽然这个引擎十分粗糙,需要改进的地方很多,但此次尝试非常有趣,我真的亲手实现了一个可以玩的国际象棋程序。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。