中国象棋AI的核心部分总结

我写中国象棋AI其实也断断续续写两年了，感觉网上关于这方面的资料非常少

有用的资料又基本都是2011年左右的，比如象眼的那个，要么是关于国际象棋的英语wiki

2011年的C++代码风格极其诡异，整体C里C气的还有各种trick堆叠，我很难读懂，也许那才算真正的C++吧

国际象棋虽然和中象在代码实现上可以借鉴，但是你自己写就会知道，奇奇怪怪的坑非常多，许多人就此累死

可能有人会问写这个有什么用吧，我觉得应该没什么用，纯凭热爱而已

我自己项目的话在 https://github.com/StarlightChessOrg/Chess98 里面，感兴趣可以看看

我在这里稍微总结一下中国象棋AI的核心部分，供后人参考

一、局面（Position）

棋盘层决定着法生成速度、合法性代价，有bug一整个引擎基本就完蛋了

这里的bug虽然非常难解决，但几乎一定会让你的程序每时每刻runtime error

写象棋AI不怕天天runtime error，就怕 “我改了这里怎么棋风就变古怪了” “怎么感觉有的局面还不错，有的局面AI表现得跟个弱智一样” 这种情况，让你蛋疼菊紧

不过棋盘说起来好简单。。。你写一写就知道了，有各种奇奇怪怪的路径和问题

1.1 局面表示

这里就有三大主流方案给你选择，我在这里给你避坑：

9*10的二维数组：性能理论上慢些，但实际上可能还好。我思量了一下没有选这个
256的一维mailbox数组：不要信象眼的。这是远古时期的解决方案，理论上提升性能，实际上不仅 可读性差（最难绷的问题），对CPU缓存和预测可能还不怎么友好，有潜在性能损失
90的一维数组：现代综合最优选择，Pikafish在用，可读性稍微差那么一点点，性能不错

我选了最后一个。另外期盘只需要建立一个全局单例变量就行了，没必要new一个类

1.2 着法生成与合法性

这里面最麻烦的函数：将军检测，着法合法性检测，着法生成函数

伪合法->过滤：现在主流做法是生成时就过滤掉不合法着法，比如吃将之类的。以前可能还有搜索中吃将吃帅，现在基本不这样搞，似乎会有奇奇怪怪的问题
将军检测：对方攻击是否触及己将；除了车炮之外，不建议听AI的什么“维护攻击表”，那是它吃太多网上的屎了，然后给你一个四平八稳的答案，总之不要信sb
分类生成：quiet moves、capture moves、killer moves, hash moves, bad capture moves分开来，不然你每个节点都tm要吃满所有着法生成
do / undo：走子与悔棋，保存被吃子、哈希、将军历史等，保证搜索可回溯

1.3 Zobrist 哈希

为每个（棋子种类 × 格子）准备随机 64 位键，局面哈希为 XOR；换边再 XOR 一个 SIDE_KEY。用途：

置换表：索引与校验
重复局面：注意这里不要听AI的使用hash来判断重复局面，它是说国际象棋，因为国际象棋由于棋规问题，不这样做就是严重bug，但中国象棋只需要看历史着法列表即可
增量更新：走子时只 XOR 起终点相关键，避免整盘重算

1.4 走子与状态增量

非常骚的部分，我说都说不清楚，因为这部分说起来好简单，实际上你会碰到各种奇奇怪怪的问题

核心问题就是，如何避免每次都要扫描90格棋盘来获取所有存活的棋子、所有特定队伍的棋子

如果你追求这个来实现极致性能，就需要设计维护一些表之类的东西，这部分会碰到很多坑

建议直接阅读Chess98的position.hpp部分源码，我觉得我自己的实现还不错，比较完美地解决了这个问题。皮卡鱼源码不要读，那一坨东西读懂难如登天

1.5 协议与外部表示

引擎使用的协议之类的

FEN：局面读写、开局库、测试对局
UCCI / UCI：与GUI、自测脚本对接，以及各种边角料

然后写个autotest之类的东西，标准大概如下：

和Pikafish去比，Pikafish分数为5000，你的初始分数为0，然后对弈1000局

和棋加5分，输棋的话，若对局步数超过140ply，或者超过100ply且差距小于一个马的价值，加3分，否则不加分

赢棋的话符合上述规则加8分，否则加10分（同等条件下几乎不可能，你pikafish实在太恐怖了）

二、搜索（Search）

搜索层在有限时间内尽量看深、看准。现代象棋引擎几乎都建立在negamax和ab剪枝之上，再叠加启发剪枝与着法排序

不要信那些天花乱坠的无搜索象棋AI论文，尤其是tencent那边发的arXiv文章，那东西吹“超过99%的普通人”感觉非常奇怪，事实上几乎就是靠预训练数据撑场面，实战效果跟答辩一样，约等于Pikafish一层深度的棋力

真正强一点的是各种ChessZero，在2019年的时候小胜了Stockfish，不过自从NNUE被一个玩将棋的大佬给咪出来之后，这种基于MCTS的引擎就基本被传统引擎爆杀了

我认为这方面是可以研究的，不过对于机器学习基础要求非常高

2.1 Negamax

Minimax的对称写法：双方都按“最大化己方分数”搜索，对方分数取负：

value = -search(child, depth - 1, -β, -α)

评估函数约定为当前行棋方视角的分值，与Negamax一致

用Negamax可以简化你的代码，不至于写出一坨搜索出来

2.2 Alpha-Beta

维护窗口[alpha, beta]：

分值 ≤ alpha：不够好（fail-low），可剪
分值 ≥ beta：太好，对方不会让你走到（fail-high / beta cutoff），可剪

剪枝效率几乎完全取决于着法顺序：好着法先搜，beta剪得越狠。这也是搜索效率的提升核心

2.3 PVS（Principal Variation Search）

对第一个着法用全窗口搜索，其余着法先用空窗（[alpha, alpha+1]）探测

若探测值落入窗口再重新全窗搜索。常与“是否在 PV 节点”模板参数配合（如 CUT / PV）

我采用is_cut参数判断

2.4 迭代加深（Iterative Deepening）

由浅到深逐层搜索：depth = 1, 2, …，比你傻傻地直接搜depth = 8快很多

没错，n + n^2 + n^3 + n^4 < n^4，你可能觉得反直觉，但历史启发和置换表组合拳会颠覆你的直觉

浅层结果给深层提供 TT 着法、Killer、History
易做时间控制：时间到可立即返回当前最佳着
可配合 aspiration window（围绕上次分数开窄窗，失败再扩窗）

2.5 置换表（TT / Transposition Table）

按 Zobrist 存：深度、分数、边界类型（EXACT / ALPHA / BETA）、最佳着法

命中且深度足够：可直接截断或收紧窗口
即使得不到截断，TT move 也是着法排序的第一优先

替换策略常见：始终替换、深度优先、两槽（深度槽 + 始终槽）等

2.6 着法排序（Move Ordering）

这部分的话，主流做法是交给一个叫MovePicker的东西，不然容易写成屎山

典型优先级的话：

TT
Good Captures
Killer
Quiet Moves
Bad Captures

SEE（Static Exchange Evaluation）：静态估算吃子链条是否亏子，用于过滤烂兑、静搜剪枝、LMR 条件等

2.7 静态搜索（Quiescence Search, QS）

深度到0时不立刻评估，而是继续搜索吃子（及必要时的将军着法），直到局面“安静”，减轻水平线效应

被将军时通常要扩展所有解将着法，而不是只搜吃子
可对 SEE 为负的吃子剪掉
限制静搜最大延伸，防止爆炸（不然搜索深度爆减就完蛋了）

2.8 空着剪枝（NMP, Null Move Pruning）

一个高风险高回报的策略

假设弃一手仍明显优于beta，则可剪枝。做法：换边但不走子，以depth - R - 1做空着探测

象棋注意（这些地方出问题的话一整个引擎棋力大降）：

被将军时禁用
子力过少（接近纯将帅残局）时空步不可靠，应禁用或减弱
缩减量R可随深度自适应

2.9 延迟着法缩减（LMR, Late Move Reduction）

高风险高回报，把排序靠后、看起来平淡的着法先以缩减深度搜索；若结果出人意料地好，再以全速research

常见限制条件（满足才缩减）：

非 PV 节点
非将军中 / 非将军着法
非 TT 着法、非 Killer
SEE 不佳或安静着法
深度与着法序号超过阈值

2.10 其他常见剪枝与扩展

一些高风险的算法，对棋力的影响犹如抛橡皮

名称	思路
FP / Razoring	静搜或浅搜分数远低于alpha时剪掉
Reverse Futility / Static Null Move	评估分远高于beta时直接返回
ProbCut	用浅层搜索验证“是否真能超过某阈值”
Check Extension	将军着法额外加深度
Singular Extension	某着法明显优于其余着法时延伸
IID / IIR	无 TT 着法时先浅搜找一个好着法再正式搜
Multicut	多个着法都能beta剪枝则整节点剪掉（较少用或需谨慎）

2.11 时间控制与停止

固定深度 / 固定时间 / 按剩余时间分配
软停止与硬停止；主循环检查标志，避免长手中间无法返回
根节点可对候选着法做额外时间倾斜（stable PV 少花时间等）

2.12 象棋规则相关剪枝

在完整实现规则时还需：

重复局面：长将禁手、长捉等（引擎自对弈可简化为三次重复和棋或按协议处理）
将死 / 困毙：无合法着法时返回 mate 分，并按距离根节点加权（更快将死更好）

Mate 分通常写成 ±(MATE - ply)，便于置换表与着法选择

三、评估（evaluate）

这里讲中国象棋的评估策略吧，分为HCE和NNUE两个东西

1. 传统手写评估（HCE）

这个东西实际上棋力不咋地，不过还是要讲一下，因为NNUE训练可能会依赖这个做bootstrap

HCE就是传统的矩阵+定式去评估，什么空头炮减分，却士怕马缺相怕炮之类的

问题就是这种定式是纯人类经验的，而局面数量太大了，很多局面用HCE不可能得到准确评估，导致棋力一坨

不过NNUE的启动依赖一个不错的HCE，这样可以不断自我对弈然后更快地拟合出来

2. 高效可更新神经网络（NNUE）

NNUE脱离了HCE的短板，可以看到更多HCE看不到的东西。而且它是增量更新的，性能可观

NNUE是有监督的训练，依赖一个标准来判断局面好不好，然后拟合这个标准，意味着它的first run离不开HCE

当然，现在我们也可以通过蒸馏皮卡鱼来训练，我认为这是更高效的方法

我们可以通过让它多学胜方的评估，少学败方的评估，来让它evolve起来，当然这是最最最简单的策略之一

具体我还要研究一下

最后

纯兴趣项目，坚持那么久，也有不少收获，还结识了挚友。也算是玩最久的一件事吧

参考：