Regex Chess: 一个使用84,688个正则表达式的2层minimax国际象棋引擎

# 一个由84,688个正则表达式实现的2层极小化极大象棋引擎 来源：https://nicholas.carlini.com/writing/2025/regex-chess.html *能下棋吗？用正则表达式？能。能下棋吗？用正则表达式。* 假期里我意识到，我已经很久没做完全没意义的事了。所以闲话少说，我向您隆重推出……**Regex Chess**：一组由84,688个正则表达式组成的序列，按顺序执行后，会根据输入的棋盘走出一招（合法且不算*太烂*的）棋。来，我给您演示一下。 当前正在执行的正则表达式将显示在此处…… 具体来说，这就是和你对弈的整个程序（真的，我没开玩笑 (https://github.com/carlini/regex-chess/blob/main/main.py)，它就这么短）： let regex_list = [/* 非常长的正则表达式列表 */] let board = "rnbqkbnr / pppppppp / 8 / 8 / 8 / 8 / PPPPPPPP / RNBQKBNR w KQkq - 0 1"; for (regex of regex_list) { board = re.replace(regex.pattern, regex.target) } display(board) 读完这篇文章，你（希望）能明白为什么这组正则[\[a\]](https://nicholas.carlini.com/writing/2025/regex-chess.html#footnote1) 注：有些学究看到这个会说：“你说要用正则表达式，但这些根本不是*正则的* (https://en.wikipedia.org/wiki/Regular_language)！！” 我不在乎。表达式是可行的，以及每个具体的正则表达式是做什么的。 （如果你是在过去半年左右订阅本博客，并且习惯了我写“严肃”、“重要”的内容，请把这作为善意的警告：这是我的网站，我定规矩，所以今天你无论如何都得学习 RegexChess。） 一如既往，项目代码可在 GitHub (https://github.com/carlini/regex-chess) 上找到。 ## 入门：一个正则表达式 CPU 那么，我们如何让正则表达式下棋呢？当然是造一台正则表达式计算机！更具体地说，我们要设计一个无分支、条件执行、单指令多数据流的指令集。然后生成一组正则表达式来解释这些指令。（有点像 GPU 指令集，又有点 ARM 的风格，但慢得多。）然后就可以用我们的新计算机来下棋了。开始吧。 （有些人可能会说我对造奇怪计算机有变态的执着，参考我的生命游戏计算机 (https://nicholas.carlini.com/writing/2021/unlimited-register-machine-game-of-life.html) 或我的 printf 计算机 (https://github.com/carlini/printf-tac-toe)。那些人错了，他们只是对平庸和普通有变态的执着。） ## 计算机设计 我先解释一下计算机要操作的数据是如何组织的。因为我们在用正则表达式，计算机的当前`状态`会用一个字符串表示，其中包含程序的“栈”以及所有变量，格式如下： %% \#stack: 栈顶元素 栈中第二个元素 …… \#变量1: 值1 \#变量2: 值2 …… \#变量k: 值k 每个`指令`要么操作栈上的某些变量，要么读写某个变量。我们来看几个基本指令。 ### 基本栈操作 #### `Push`指令 这是实现`push`命令的代码，它把一个值加到栈顶： def push(const): return [(r"(%%\\n\#stack:\\n)", r"\g<1>" + const + r"\\n")] 你应该把这些函数的返回类型理解为一个元组列表。每个元组代表一个要应用的正则变换，左边是匹配模式，右边是替换字符串。 简单回顾一下正则表达式。列表中的每个元组有两部分：正则表达式和替换字符串。正则表达式会*匹配*字符串，如果它能在被作用的对象（这里就是*状态*字符串）中找到子串。大多数正则字符匹配自身，但括号会创建一个“匹配组”，之后可以引用。 第二个参数是替换字符串。同样，大多数字符表示“替换为此字符”，但像 \g<1> 这样的特殊序列是反向引用，指向之前捕获的组。在这个例子中，\g<1> 引用第一个捕获组（第一个括号内匹配的内容）——这里就是 "%%\\n\#stack:\\n" 头部。 因此，这个操作在栈上执行时，会在状态中找到 "%%\\n\#stack:\\n" 的出现位置，并在其下方（即栈顶）插入常量值。 来看个实际例子。假设我们从空栈开始： %% \#stack: 如果执行 `push("hello")`，正则表达式会： - 在状态开头匹配模式 `%%\\n\#stack:\\n` - 将这个头部捕获到组 1（模式中的括号创建了这个捕获组） - 用捕获的组（\g<1>）后跟常量 "hello" 和换行符替换它 结果得到： %% \#stack:hello 如果再执行 `push("world")`，同样的过程重复，得到： %% \#stack:world hello 正则表达式总是在栈区域顶部匹配，所以新项被推到顶部，同时保留下面已有的栈内容。 #### `Pop`指令 `pop` 指令从栈顶移除元素： def pop(): return [(r"(%%\\n\#stack:\\n)([^\\n]*)\\n", r"\\1")] 这里开始看到一些使正则表达式强大的特殊操作符。`[^\\n]` 表示“匹配任何不是换行符的字符”，`*` 表示“匹配零个或多个”。所以整体来看，我们在找一行以 "%%\\n\#stack:\\n" 开头，然后下一行有零个或多个不是换行符的字符（即一整行）。替换字符串只有第一行，因此效果是移除第二行，即弹出栈顶。 看实际效果。假设我们从这样的栈开始： %% \#stack:world hello 执行 `pop()` 时，正则表达式会： - 匹配以 `%%\\n\#stack:\\n` 开头的模式（捕获到组 1） - 匹配直到下一个换行符的所有字符（捕获到组 2 —— 即 "world"） - 将匹配到的所有内容替换为组 1（头部），从而移除顶部的元素 结果得到： %% \#stack:hello 每次 pop 操作从栈顶移除恰好一个元素，保留下面剩余的元素。 ### 变量 <-> 栈指令 #### 变量`查找` 将变量内容加载到栈顶： def lookup(variable): # 找到变量的值并压入栈顶 return [(r"(%%\\n\#stack:)([^%]*\\n\#" + variable + ": )([^\\n]*)\\n", r"\\1\\n\\3\\2\\3\\n")] 这个正则比之前的复杂一些。我们来分解一下： - `[^%]*` 基本上匹配任何字符（% 只出现在程序开头），因此可以找到程序中任何地方的变量。 - `[^\\n]*` 通过捕获直到行末的所有内容来匹配变量的值 - 替换会创建该值的一个副本，并放在栈顶 看实际效果。假设我们从这样的状态开始： %% \#stack: \#foo: hello \#bar: world \#baz: 42 如果执行 `lookup("bar")`，正则表达式会： - 在组 1 中匹配栈头部 - 在组 2 中匹配直到并包括 "\#bar: " 的所有内容 - 在组 3 中匹配 "world" - 使用这些组重建状态，并将值复制到栈顶 执行替换后得到如下状态： %% \#stack: world \#foo: hello \#bar: world \#baz: 42 查找操作保留了原始变量及其值，同时将值的副本放到栈顶。这样我们就可以在不修改变量的情况下读取变量值。 #### 变量`赋值` 给变量赋值是一个有趣的挑战：我们不知道变量是否已经存在。需要处理两种情况：更新已有变量或创建新变量。 下面给出实现，然后逐一解释。 def assign_pop(varname): return [ (r"(%%)\n\#stack:\n([^\n]*)\n" + r"([^%]*\#" + varname + r": )[^\n]*", r"\\1\`\n\#stack:\n\\3\\2"), (r"(%%)([^\`]\n?\#stack:\n)([^\n%]*)\n([^%]*)", r"\\1\`\\2\\4\#" + varname + r": \\3\n"), (r"%%\`", r"%%") ] 首先假设变量已经存在。即栈初始状态如下，假设调用 `assign_pop("bar")`： %% \#stack: world \#foo: hello \#bar: something \#othervar: othervalue 运行这组正则表达式时，我们创建以下捕获组： %% \#stack: world \#foo: hello \#bar: something \#othervar: othervalue 经过替换操作后，得到这样的输出： %% \` \#stack: \#foo: hello \#bar: world \#othervar: othervalue 然后继续执行下一条指令，但*它不会匹配*，因为第二个正则表达式在程序开头 %% 之后有反引号时会失败。所以什么也不发生。最后，第三个正则表达式清理现场。 **处理不存在的变量：** 考虑变量不存在的情况。同样，假设调用 `assign_pop("bar")`： %% \#stack: world \#foo: hello \#othervar: othervalue 第一个正则表达式尝试匹配，但失败了，因为找不到 "\#bar"。所以它什么也不做。但第二个正则表达式尝试匹配并成功。它创建以下捕获组： %% \#stack: world \#foo: hello \#othervar: othervalue 然后执行重写，得到如下输出： %% \#stack: \#foo: hello \#othervar: othervalue \#bar: world 第三个正则表达式执行后什么也不做。 许多指令都使用这种技巧来确保不会以我们不希望的顺序应用。例如，作为练习，尝试理解“相等”指令的工作原理： def eq(): return [ (r"(%%\\n\#stack:\\n)([^\\n]*)\\n\\2\\n", r"\\1\`True\\n"), (r"(%%\\n\#stack:\\n)([^\`][^\\n]*)\\n([^\\n]*)\\n", r"\\1False\\n"), ] ## （无分支）条件语句 为了让编程语言有趣，通常需要某种控制流。没有 if 语句很难写出有意义的程序。所以现在展示我们如何实现这一点。（希望你做了家庭作业，因为我们将再次使用相同的条件执行技巧！）以下是条件指令的实现： def cond(tag): return [(r"%(%%\n\#stack:\nTrue)", r"%\\1\`"), (r"%(\\n\#stack:\nFalse)", tag + r"\\1\`"), (r"\\n(True|False)\`\\n", "\\n")] 我们来走一遍过程，从栈顶为 False 的情况开始。 %% \#stack: False \#variable: value 首先，第一个正则会匹配失败，因为栈顶元素不是 True。于是转到下一个正则，检查它是否适用。这个能匹配，并生成相应的匹配组。 %% \#stack: False \#variable: value 应用替换后，得到如下栈。 %tag \#stack: False\` \#variable: value （最后，使用同样的清理技巧，移除使用过的标记。） 现在发生了什么？程序*不再以 `%%` 开头*。这意味着所有指令都无法匹配，因为它们总是确保程序以 %% 开头。所以其他任何事都不会发生……直到后来用下面这条简单指令*重新激活*它： def reactivate(tag): return [(r"%" + tag + r"\n([^%]*)", r"%%\n\\1")] 现在回到条件语句的 True 情况。这是简单情况：基本上什么也不做。我们在第二个正则中将栈替换为 True\`，然后在第三个正则中删掉这一行。简单。 注意，我们的代码实际上是*无分支*的，因为每条指令都是条件指令。（有点像 ARM 的预测执行，大多数指令可以根据状态标志有条件地执行，而不用显式的分支指令。） ### 循环（不可能） 因为我们的程序只是一组正则表达式序列，所以根本无法循环！这意味着，严格来说，我们无法实现图灵完备 (https://en.wikipedia.org/wiki/Turing_completeness) 注：但我们可以通过*展开*任何可能用到的循环来执行任何有界计算。幸运的是，计算一盘棋的下一步是一个有界计算，所以我们完全可以做到。 ## 单指令多数据流 接下来是我最爱的部分，我们这门语言的特性。借助正则表达式的魔力（以及它们对整个字符串进行全局替换的事实），我们可以同时运行多个“线程”！ 也就是说，如果我们将状态字符串写成： %% \#stack:int0000101010int0001011100 %% \#stack:int0000001101int0110000000 当我们调用`binary_add()`时，两个加法同时完成！执行后： %% \#stack: int0010001110 %% \#stack: int0110001101 出现这种情况是因为正则表达式匹配是全局的。当我们两次匹配到“线程开始”操作符（`%%`）时，我们就能够同时对两个线程进行操作。 那么，如何实际利用这个特性呢？来看一些帮助我们创建和管理线程的指令。 ### Fork 指令 这里是一个简单的 fork 指令，它将当前运行的每个线程分成两个，第二个线程初始为不活跃状态并带有一个给定标签： def fork_inactive(tag): return [(r"%%\n([^%]*)", r"%%\n\\1" + "%" + tag + r"\n\\1")] 我们也可以对布尔值执行 `fork()`，给一个线程 True 情况，另一个 False 情况。（这有点像 McCarthy 的 Amb 操作符 参考 (https://linkinghub.elsevier.com/retrieve/pii/S0049237X08720184)） def fork_bool(variable): return [(r"%%\n([^%]*)", r"%%\n\\1\#" + variable + r": True\n%%\n\\1\#" + variable + r": False\n")] 看看多次 fork 会发生什么。从一个简单的状态开始： %% \#stack: somevalue \#x: 10 调用`fork_bool("condition")`后，得到： %% \#stack: somevalue \#x: 10 \#condition: True %% \#stack: somevalue \#x: 10 \#condition: False 如果再调用`fork_bool("c2")`，每个现有线程会再分成两个： %% \#stack: somevalue \#x: 10 \#condition: True \#c2: True %% \#stack: somevalue \#x: 10 \#condition: True \#c2: False %% \#stack: somevalue \#x: 10 \#condition: False \#c2: True %% \#stack: somevalue \#x: 10 \#condition: False \#c2: False 现在我们同时有四个执行路径，探索所有布尔条件组合。这对国际象棋非常有用，因为经常需要同时考虑多种可能的棋盘状态，并（例如）给它们评分以找出最好的。不需要循环遍历每种可能的棋盘状态，我们只需假装只做一次，但让所有状态同时发生。 ## 编译到我们的小语言 现在我们有了 CPU 模拟器，就可以构建一个编译器，目标是我们新的汇编语言。 *“等等，我读这篇文章可不是为了学编译器！”* 你说？有道理。而且我一开始也没打算在这个项目里构建编译器，所以我实际上只是……