Regex Chess：用 84688 条正则表达式实现 Minimax 搜索的计算边界探索

当大多数人还在纠结如何用正则表达式匹配邮箱地址时，Google DeepMind 的研究员 Nicholas Carlini 却完成了一项看似荒谬的工程：用 84,688 条正则表达式 构建了一个完整的国际象棋引擎，能够执行 2-ply 的 Minimax 博弈树搜索。这个项目不仅是对正则表达式表达能力极限的一次 stress test，更揭示了一种独特的计算模型设计哲学。

核心架构：Regex CPU 的设计哲学

Regex Chess 的核心创新在于将正则表达式重新定位为一种通用计算指令集的执行载体。Carlini 设计了一个「无分支、条件执行、单指令多数据」（Branch-Free, Conditional-Execution, SIMD）的虚拟指令集，然后用正则表达式序列来模拟这些指令的执行。

整个程序状态被编码为一个字符串，格式如下：

%% #stack: top_item second_item ... #var1: value1 #var2: value2 ...

其中 %% 标记表示当前线程处于激活状态。每条正则表达式本质上是一个模式 - 替换对，通过匹配和重写这个状态字符串来实现计算。

这种设计的精妙之处在于条件执行的实现。传统的分支指令被转化为「激活标记」操作：当条件为 False 时，将 %% 替换为 %tag，使后续所有正则表达式都无法匹配（因为它们都以 %% 开头）；当需要恢复执行时，再用 reactivate(tag) 指令将标记改回 %%。这种机制类似于 ARM 架构中的条件执行，但完全通过字符串操作实现。

关键机制：从栈操作到并行分裂

Regex CPU 实现了一套完整的指令集，包括栈操作（push/pop）、变量读写（lookup/assign）和条件分支（cond）。但真正让这个引擎具备实用价值的是其 SIMD 并行能力。

利用正则表达式的全局匹配特性，单个模式可以同时在多个线程状态上执行操作。当状态字符串包含多个 %% 标记时，例如：

%% #stack: state1 %% #stack: state2 %% #stack: state3

一条正则表达式替换可以同时作用于所有三个线程，实现真正的并行计算。

fork_inactive(tag) 指令是并行化的关键。它通过简单的模式匹配将当前状态复制一份，并将副本的激活标记改为 %waiting，同时在两个状态中分别设置不同的变量值。这种机制被用来实现 Minimax 搜索中的并行状态探索—— 每个线程代表棋盘的一个可能状态，所有线程同时评估各自的走法。

Minimax 搜索的实现：并行博弈树遍历

在传统 chess engine 中，Minimax 搜索通过递归函数调用遍历博弈树。而在 Regex Chess 中，这个过程被转化为状态分裂与合并的字符串操作。

当引擎需要评估一步棋时，它会：

1. 使用 fork_on_list 为每个合法走法创建一个并行线程
2. 在每个线程中模拟该走法后的棋盘状态
3. 同时评估所有线程的棋局得分（通过正则表达式计算子力价值）
4. 使用 keep_best_scoring_board 合并结果，仅保留得分最优的状态

这种「无显式循环、全展开并行」的计算模式，让 Regex Chess 能够在不编写传统搜索算法的情况下实现 2-ply Minimax。作者巧妙地利用了「检查伪合法走法是否将己方王置于被吃状态」这一需求 —— 这本身就需要生成对手的所有回应，因此深度 - 2 的搜索几乎是「免费」获得的。

不过，这种实现存在一个边界限制：引擎只检查到深度 - 2，对手的回应如果也将自己的王暴露给攻击（即非法走法），引擎不会进一步验证。这意味着在某些复杂局面下，引擎可能会基于对手非法走法的假设做出次优决策。

性能优化：从 30 分钟到 10 秒的 100 倍加速

初始版本的 Regex Chess 生成一步棋需要约 30 分钟 —— 仅适合「邮件对弈」。通过一系列针对性优化，Carlini 将其缩短至 1-10 秒，实现了约 100 倍的性能提升。

关键优化策略包括：

1. 积极删除中间变量

每次变量查找都需要扫描整个状态字符串（O (n) 操作），而状态分裂时需要复制所有变量。通过及时删除不再需要的变量并复用变量名，单步评估的内存占用从 10GB 降至 300MB。

2. 精确的模式前缀匹配

在条件指令的实现中，Carlini 发现将模式从 (True|False)\\n改为\n(True|False)`\n（添加换行前缀）可以提升 2 倍效率。原因是状态字符串中包含大量 True/False值（作为变量内容），通过要求前导换行和#stack:` 前缀，正则引擎可以快速跳过这些非目标匹配，显著减少尝试匹配的次数。

3. 专用指令替代指令组合

某些频繁操作（如扫描棋盘查找特定棋子）原本由多个条件指令和栈操作组合实现。通过将这些逻辑「内联」为单条复杂的正则表达式，消除了大量中间步骤的开销。

4. 最大化并行度

对于滑动棋子（车、象、后）的走法生成，引擎同时 fork 出 8 个线程，每个线程负责一个方向。这种并行化策略将原本需要循环遍历的操作转化为单次并行执行。

工程启示：正则表达式的计算边界

Regex Chess 项目虽然被作者自嘲为「entirely no purpose」，但它深刻揭示了正则表达式作为计算模型的几个重要特性：

表达能力边界：正则表达式（即使是扩展正则）本身不是图灵完备的，因为无法表达无界循环。但对于任何有界计算（如固定深度的博弈树搜索），通过循环展开和状态编码，正则表达式足以胜任。

并行计算潜力：全局匹配语义赋予了正则表达式天然的 SIMD 能力。这种「单指令多数据」特性在文本处理领域很少被充分利用，但在状态空间搜索等场景中展现出独特价值。

性能权衡的艺术：项目展示了在极端受限的计算模型下，通过算法重构（并行替代串行）和实现细节优化（模式前缀精确化）可以获得数量级的性能提升。

对于编译器设计和 esolang（深奥编程语言）研究者而言，Regex Chess 提供了一个鲜活的案例：如何将高级语言（Python 风格的伪代码）编译到底层受限指令集（正则替换），并通过符号执行和路径探索实现控制流的分支与合并。

结语

Regex Chess 提醒我们，技术的边界往往比我们想象的更富有弹性。当 84,688 条正则表达式在字符串上执行替换操作时，它们不仅仅是在处理文本 —— 而是在模拟一个完整的虚拟 CPU，执行分支、循环、并行计算和博弈树搜索。这种将「不可能」转化为「可能」的工程创造力，或许正是计算机科学最迷人的一面。

参考来源

• Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions — Nicholas Carlini
• GitHub - carlini/regex-chess

compilers