124 行 Python 代码写一个中国象棋引擎

前几天在和别人聊天的时候谈到 sunfish 这个开源项目,这是一个只用了 111 行 python 代码写成的国际象棋引擎，这个 111 行引擎本身还不弱。聊天结束后，我几乎立刻有了兴趣在中国象棋上复刻一版 sunfish,于是我也这么做了。实际上代码工作顺利地难以置信，短短两天的部分业余时间就已经完成了算法的移植工作，产出了一个只用 124 行代码就实现的中国象棋引擎elephantfish (github 地址 https://github.com/bupticybee/elephantfish)。

至于棋力嘛，对于如此精简的中国象棋引擎我本来也没有什么期望，我自己和 elephantfish 下了两盘棋，由于太久没有下象棋，我两盘都不小心被抓住了漏洞输了，我也将 elephantfish 和象棋小巫师的傻瓜难度做了对弈，结果是思考时间为 1 秒的 elephantfish 不敌象棋小巫师，当思考时间扩展到 5 秒时终于可以下过了（但此时象棋小巫师思考深度为 2，elephantfish 思考深度为 7~9，所以在局面评估函数上实际进步空间还非常大）。

实际上能够这么短时间完成elephantfish归功于几个原因：

1. sunfish 本身写得非常通用，很多数据结构几乎不需要怎么更改就可以和中国象棋通用，一些只需要少量更改，其中值得一提的是，关键模块 Searcher 的代码用在移植到中国象棋的时候更是一行未改。
2. 中国象棋领域已经有一些开源的优秀的算法存在，比如说 象眼 ，其提供的子力价值表非常具有参考价值，事实上我直接在程序中使用了部分象眼的子力价值表。
3. xqbase 提供了一系列常见算法的解释和翻译，正是这些翻译放我在理解 sunfish 的逻辑时可以非常顺利。

这个项目的目的是提供一个类似 sunfish 的象棋引擎 codebase，让即使不研究这个领域的同学也可以方便快速地上手做一些实验，或者至少让对这方面感兴趣的同学只需要花一点点的时间就可以完全理解一个简单的中国象棋引擎需要运用的数据结构和算法是什么样的。

为了说明 elephantfish 到底有多么简单，我们稍微来看一下 elephantfish 所用的数据结构和算法。

中国象棋棋盘表示

在 elephantfish 中，中国象棋的棋盘被表示为一个大字符串：

initial = (
    '               \n' 
    '               \n' 
    '               \n' 
    '   rnbqkqbnr   \n' 
    '   .........   \n' 
    '   .c.....c.   \n' 
    '   p.p.p.p.p   \n' 
    '   .........   \n' 
    '   .........   \n' 
    '   P.P.P.P.P   \n' 
    '   .C.....C.   \n' 
    '   .........   \n' 
    '   RNBQKQBNR   \n' 
    '               \n' 
    '               \n' 
    '               \n'
)

这是一个长度为 16 * 16 = 256 的字符串，每个位置的元素都对应棋子或棋盘上的空的地方：

P -> 兵
C -> 炮
R -> 车
N -> 马
B -> 象
Q -> 士
K -> 帅
. -> 空
  -> 棋盘外

在这样的一个大字符串描述的棋盘上进行走子也非常简单，比如我们需要走炮二平五这一步棋，那么我们只需要将二路跑的位置的字符串元素置为'.'，然后将炮的落子点位置的元素用炮替代即可.

着法产生器

着法产生器是用来生成一个局面下的所有“我方”可能的动作，比如在开局的情况下，红方可以走炮二平五，马二进三，...等等其他步子，由于我们需要使用一个搜索算法去遍历这些可能的动作，着法生成器就是必须的，同时也是很关键的一个组件，如果着法生成器所生成的着法有问题，整个搜索过程就是错误的。

实际如果不考虑效率，一个着法生成器比我们大多数人想的简单，虽然中国象棋中有一些比较特殊的规则需要特殊处理（比如马腿，炮架，将军照面），其他子力的活动规则都是非常简单的，我们的着法生成器整体代码只有 30 多行(去掉注释)：

class Position(namedtuple('Position', 'board score')):
    """ A state of a chess game
    board -- a 256 char representation of the board
    score -- the board evaluation
    """
    def gen_moves(self):
        # For each of our pieces, iterate through each possible 'ray' of moves,
        # as defined in the 'directions' map. The rays are broken e.g. by
        # captures or immediately in case of pieces such as knights.
        for i, p in enumerate(self.board):
            if not p.isupper(): continue
            if p == 'K':
                # 将军照面的判断
                for scanpos in range(i - 16,A9,-16):
                    if self.board[scanpos] == 'k':
                        yield (i,scanpos)
                    elif self.board[scanpos] != '.':
                        break
            if p == 'C':
                # 炮的走法比较特殊，拿到前面判断
                for d in directions[p]:
                    cfoot = 0
                    for j in count(i+d, d):
                        q = self.board[j]
                        if q.isspace():break
                        if cfoot == 0 and q == '.':yield (i,j)
                        elif cfoot == 0 and q != '.':cfoot += 1
                        elif cfoot == 1 and q.islower(): yield (i,j);break
                        elif cfoot == 1 and q.isupper(): break;
                continue
            for d in directions[p]:
                for j in count(i+d, d):
                    q = self.board[j]
                    # Stay inside the board, and off friendly pieces
                    if q.isspace() or q.isupper(): break
                    # 过河的卒 /兵才能横着走
                    if p == 'P' and d in (E, W) and i > 128: break
                    # j & 15 等价于 j % 16 但是更快,这行代码的含义是士和帅都只能在九宫格内部活动
                    elif p in ('Q','K') and (j < 160 or j & 15 > 8 or j & 15 < 6): break
                    # 象不能过河
                    elif p == 'B' and j < 128: break
                    elif p == 'N':
                        n_diff_x = (j - i) & 15
                        if n_diff_x == 14 or n_diff_x == 2:
                            # NEE,SEE,NWW,SWW 这四种马的走法会进入这个分支判断马腿
                            if self.board[i + (1 if n_diff_x == 2 else -1)] != '.': break
                        else:
                            # NNE,SSE,NNW,SSW 这四种马的走法会进入这个分支判断马腿
                            if j > i and self.board[i + 16] != '.': break
                            elif j < i and self.board[i - 16] != '.': break
                    # 象眼不能有子
                    elif p == 'B' and self.board[i + d / 2] != '.':break
                    # Move it
                    yield (i, j)
                    # Stop crawlers from sliding, and sliding after captures
                    if p in 'PNBQK' or q.islower(): break

突然贴上来一段代码可能会显得有点唐突，但是这里把着法生成器的代码贴出来的目的是为了让大家明白，其实只需要很短的一小段代码就可以完成着法生成的工作，而着法生成的代码几乎占了这 124 行代码的将近一半。

搜索策略

搜索策略的代码虽然也非常短（仅有不到 100 行），但是相较于着法生成器，并不是那么容易可以读懂的，在 elephantfish 中使用了MTD(f) 算法进行搜索，想要读懂这个算法的话建议还是花额外的一两个小时看一下《对弈程序基本技术》 下的几篇文章，掌握下面几个知识点就可以看懂了，你会发现 sunfish/elephantfish 中的策略搜索代码几乎就和这几篇文章中的伪代码完全一样。

推荐先后阅读下面几篇文章，掌握搜索策略的一些知识：

1. 基本搜索方法——“最小-最大”搜索(B.Moreland)
2. 基本搜索方法——Alpha-Beta 搜索(B.Moreland)
3. 基本搜索方法——迭代加深(B.Moreland)
4. 基本搜索方法——换位表(B.Moreland)
5. 高级搜索方法——简介(一)(D.Eppstein)
6. 高级搜索方法——简介(二)(D.Eppstein)
7. 高级搜索方法——静态搜索(B.Moreland)
8. 高级搜索方法——空着裁剪(B.Moreland)
9. 高级搜索方法——主要变例搜索(B.Moreland)

后记

总的来说，elephantfish 的实现非常简单，使用了很多棋类 ai 的 trick，棋力不算太强，但是也可以战胜一些比较弱的人类（比如我）。我认为，或者说我希望 elephantfish 可以成为一个“基准代码”，希望能够有一些人能够因为这个项目对象棋引擎感兴趣，甚至在 elephantfish 上进行一些自己的实验，后续我将会提供一些能够让不同 ai 见进行对弈的脚本，让大家能够方便的做一些实验并且很快看到效果。