Regex Chess: A 2-Ply Minimax Engine Built From 84,688 Regular Expressions

Nicholas Carlini built a working chess engine using nothing but a sequential list of 84,688 regex substitutions applied to a string holding the board state. The runtime is essentially a three-line JavaScript loop that walks the regex list and rewrites the board on each pass. To make this tractable, Carlini designed a tiny virtual machine on top of regex: a branch-free, conditional-execution, SIMD-style instruction set whose entire memory is a single formatted string containing a stack and named variables. Each ‘instruction’ is one regex pattern-and-replacement pair that manipulates that string — push, pop, lookup, and friends — and higher-level control flow is achieved through symbolic execution and fork instructions rather than real branching or loops.

On top of that machine he compiles a 2-ply minimax search: locating pawns, generating moves in parallel, validating user input, computing a reply, and merging results, all expressed as regex transformations. The post also catalogs performance tricks such as deleting intermediate variables, optimizing regex matching paths, and emitting special-purpose composite instructions to keep the program from blowing up further.

The project is deliberately impractical — Carlini frames it as a holiday exercise in the spirit of his prior Game-of-Life and printf computers — but it is a clean demonstration that regex engines with backreferences are far more than pattern matchers. Pedants who object that backreferences make these ‘not regular’ are explicitly waved off; the artifact is the point.