84,688 条正则表达式构成的棋局评估函数：从物质计数到 SIMD 并行评分

当 Nicholas Carlini 在 2025 年初发布 Regex Chess 项目时，整个技术社区都被这个疯狂的想法震撼了：一个完全由 84,688 条正则表达式构成的国际象棋引擎，能够在 1 到 10 秒内完成一次 2-ply 的 minimax 搜索并给出合理的走法。这个项目的核心挑战不在于棋艺本身，而在于如何将棋局评估函数 —— 包括物质计数（material counting）、位置评分（position scoring）和终局检测（endgame detection）—— 全部编码为正则表达式的替换操作。

正则表达式 CPU 的架构设计

Regex Chess 的本质是一个模拟的 "正则表达式计算机"。Carlini 设计了一套分支无关、条件执行的指令集架构，类似于 GPU 的 SIMD 模型。整个计算状态被编码为单个字符串，格式如下：

%% #stack: top_item second_item ... #variable1: value1 #variable2: value2 ...

其中 %% 标记表示当前线程处于激活状态。每条指令都是一个正则替换操作，通过匹配模式并执行替换来修改状态字符串。例如，push(const) 指令的实现如下：

def push(const):
    return [(r"(%%\\n#stack:\\n)", r"\\g<1>"+const+r"\\n")]

这个正则表达式匹配栈头部，然后在保留头部的同时插入常量值和换行符，实现栈顶压入操作。类似地，pop() 指令通过捕获栈顶元素并在替换中丢弃它来实现出栈。

变量操作稍微复杂。lookup(variable) 需要扫描整个状态字符串找到目标变量，将其值复制到栈顶：

def lookup(variable):
    return [(r"(%%\\n#stack:)([^%]*\\n#"+variable+r": )([^\\n]*)\\n",
             r"\\1\\n\\3\\2\\3\\n")]

这里的关键洞察是正则表达式的全局匹配特性 —— 如果状态字符串中包含多个 %% 标记，一次替换操作会同时在所有激活线程上执行，天然实现 SIMD 并行。

棋局评估函数的正则化实现

物质计数的字符串编码

在国际象棋引擎中，material counting 是最基础的评估组件。传统实现遍历棋盘数组，按棋子类型累加分数（兵 = 1，马 / 象 = 3，车 = 5，后 = 9）。在 Regex Chess 中，棋盘以 FEN 字符串表示，如 rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR。评估函数需要将这个字符串转换为数值分数。

Carlini 的解决方案是展开棋盘为 64 个独立变量，每个变量存储对应格子的棋子。然后通过一系列正则替换将棋子字符转换为数值表示，再利用字符串操作实现累加。虽然这看起来效率低下，但得益于 SIMD 并行，所有格子的处理可以同时进行。

位置评分的并行计算

位置评分（position scoring）通常依赖 piece-square tables（PST），即为每种棋子在每个格子预设一个奖励或惩罚值。在 Regex Chess 中，这需要为每个棋子 - 位置组合创建查找表变量。

当评估一个位置时，引擎会 fork 出多个并行线程，每个线程负责评估一种棋子类型。通过 fork_bool 和 fork_inactive 指令，引擎可以同时评估白方的所有兵、马、象、车、后，以及黑方对应的棋子。每个线程独立计算自己负责的部分分数，最后通过合并操作汇总总分。

这种并行策略的关键在于正则引擎的全局替换语义。当状态字符串包含多个 %% 标记的线程时，形如 (%%[^%]*#score: )([^\\n]*) 的模式会匹配所有线程中的 score 变量，实现真正的 SIMD 并行更新。

终局检测的条件编码

终局检测通常基于剩余棋子数量，如 "双方都没有后" 或 "非兵物质总和小于阈值"。在 Regex Chess 中，这被编码为一系列条件正则表达式：

def cond(tag):
    return [(r"%(%\\n#stack:\\nTrue)", r"%\\1\\`"),
            (r"%(\\n#stack:\\nFalse)", tag+r"\\1\\`"),
            (r"\\n(True|False)\\`\\n", "\\n")]

当栈顶为 False 时，第一个正则匹配失败，第二个正则将状态前缀从 %% 改为 %tag，使后续指令对该线程失效，实现条件分支的 "假分支"。当需要重新激活时，reactivate(tag) 指令将所有标记为 %tag 的线程改回 %%。

SIMD 并行评估的工程实现

Regex Chess 最精妙的设计是其 SIMD 并行机制。传统 chess engine 需要显式遍历所有合法走法，评估每个结果位置，然后选择最佳走法。Carlini 利用正则表达式的全局匹配特性，将这一顺序过程转化为并行计算。

当引擎需要评估多个候选位置时，它会执行 fork_on_list 操作。假设当前有 20 个合法走法，该操作会创建 20 个并行线程，每个线程包含一个不同的候选棋盘状态：

%% #stack: #board: position1 ...
%% #stack: #board: position2 ...
%% #stack: #board: position3 ...
...

随后的评估指令会同时在所有 20 个线程上执行。当计算 material score 时，所有位置的分数计算并行完成；当应用 piece-square bonuses 时，所有位置的奖励值同时更新。这种并行度不依赖于 CPU 核心数，而是由正则引擎的匹配机制保证。

在 minimax 搜索中，这种并行性尤为重要。2-ply 搜索需要评估对手的回应，Carlini 的引擎会 fork 出所有可能的对手走法，并行计算每个回应的分数，然后通过 keep_best_scoring_board 操作保留最优结果。

性能优化与工程权衡

最初的实现需要约 30 分钟才能生成一个走法。通过一系列优化，Carlini 将性能提升了约 100 倍：

删除中间变量：每个变量查找都是 O (n) 的字符串扫描操作。通过及时删除不再需要的变量并复用变量名，状态字符串大小从 10GB 降至 300MB。

精确的正则锚定：在条件判断中，使用 \\n#stack:\\n(True|False) 而非简单的 (True|False) 可以将匹配效率提升一倍。这是因为前者要求匹配必须出现在栈顶，允许正则引擎快速跳过变量值中的大量布尔字符串。

专用指令融合：对于热点代码路径（如扫描棋盘寻找特定棋子），Carlini 将原本需要多个指令的循环体融合为单个复杂的正则表达式，减少状态转换开销。

局限与边界

Regex Chess 并非完整的 chess engine。由于正则表达式无法表达真正的循环（只能通过循环展开处理有界计算），引擎的搜索深度被硬编码为 2-ply。此外，非法移动检测存在缺陷：在验证对手回应时，引擎假设对手的回应也是合法的，这可能导致评估误差。

然而，这些局限恰恰揭示了正则表达式的计算边界。正如 Carlini 所言，这个项目 "教会了你比预期更多的计算机科学知识"。

结语

Regex Chess 的评估函数实现展示了状态机编码的极限可能性。通过将计算状态编码为字符串、将操作编码为正则替换、将并行性编码为多线程状态标记，Carlini 证明了正则表达式 —— 这个看似简单的文本处理工具 —— 可以承载完整的算法逻辑。对于编译器和语言设计者而言，这个项目提供了一个独特的视角：当计算模型被极度简化时，如何通过架构创新（SIMD 并行、条件执行、状态编码）恢复表达能力。

参考来源

• Nicholas Carlini, "A 2-ply minimax chess engine in 84,688 regular expressions", 2025. https://nicholas.carlini.com/writing/2025/regex-chess.html
• GitHub 仓库: https://github.com/carlini/regex-chess

compilers