完全由正则表达式驱动的国际象棋引擎

Nicholas Carlini 这篇文章介绍了自己如何使用 84,688 个正则表达式构建了一个双层 MiniMax 国际象棋引擎。

具体而言，作者是先用正则表达式写了个 CPU 模拟器，然后在这个 cpu 模拟器上写了个编译器，然后用编译器写了个国际象棋引擎。引擎名为 "Regex Chess"，可以根据输入的棋盘状态走出一手合理（且不完全糟糕）的棋步。

https://nicholas.carlini.com/writing/2025/regex-chess.html

一些技术细节：
1. 基于正则表达式的 CPU 模拟器：
*作者首先设计了一个基于正则表达式的 CPU，它是一种无分支、条件执行、单指令多数据（SIMD）的架构。
*该 CPU 的状态由一个字符串表示，包含程序“栈”和所有变量。
*基本指令包括 push（入栈）、pop（出栈）、lookup（变量查找）和 assign_pop（变量赋值）等。
*条件执行通过修改状态字符串的开头（%%）来实现，从而控制哪些指令生效。
*SIMD 特性通过正则表达式的全局替换功能实现，可以同时处理多个棋盘状态。

2. 编译器（宏汇编器）：
*作者没有构建传统的编译器，而是采用了一种基于符号执行的方法，将 Python 风格的代码转换为正则表达式指令序列。
*符号执行通过跟踪变量操作来记录执行轨迹，而不是实际执行它们。
*条件语句通过创建分支并在后续合并来实现，每个分支对应一个条件路径。

3. 国际象棋引擎的实现：
*引擎使用 FEN 字符串表示棋盘状态。
*通过并行处理，可以同时生成所有棋子的合法走法。例如，pawn_moves 函数可以并行计算所有兵的可能走法。
*利用并行处理，引擎可以模拟 MiniMax 算法，通过生成所有可能的走法并评估其分数来实现。
*引擎通过生成伪合法走法（可能会导致王被将军）然后排除这些走法来实现，这本质上是一种双层 MiniMax 搜索。

- 微博 蚁工厂