Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
Nicholas Carlini introduces Regex Chess, a 2-ply minimax engine impressively implemented using 84,688 regular expressions. This project, born from a desire for 'entirely no purpose' computing, demonstrates how to construct a branch-free, conditional-execution, SIMD CPU within the confines of regex. Hacker News readers will appreciate the technical ingenuity and the exploration of unconventional computational models, pushing the boundaries of what regular expressions can achieve.
The Lowdown
The author, Nicholas Carlini, embarked on a whimsical yet deeply technical project to build a 2-ply minimax chess engine, dubbed 'Regex Chess,' entirely out of regular expressions. This seemingly impossible feat involved creating a custom instruction set and a 'compiler' to translate Python-like logic into a sequence of 84,688 regex patterns, showcasing a unique approach to computation. The system represents the computer's state as a single string, manipulated by regex pattern-replacement rules.
- Regex as a CPU: The core idea involves representing the computer's state (stack and variables) as a single string and defining instructions (like
push,pop,lookup,assign_pop) as regex pattern-replacement pairs that modify this string. - Branch-Free Conditionals: Control flow is achieved without traditional branching. Conditions are evaluated, and if false, the state is 'deactivated' by modifying its start marker (
%%to%tag), preventing subsequent regexes from matching until reactivated. - Simulated Parallelism (SIMD): A crucial innovation is using regex's global matching to simulate Single-Instruction Multiple-Data (SIMD) processing. By duplicating the state (with
forkinstructions), multiple execution paths (e.g., for different pawns or board states) can be processed simultaneously. - Symbolic Execution Compiler: Instead of a traditional compiler, a 'macro-assembler' uses symbolic execution to trace Python-like code, recording operations (
lookup,push,binary_add,assign_pop) that translate into the custom regex instruction set. - Chess Engine Implementation: The chess engine leverages the SIMD capabilities to generate moves for all pieces concurrently, validate human moves, and perform a depth-2 minimax search. For example, all possible pawn moves are generated in parallel by forking states for each pawn.
- Performance Optimizations: Initial performance was slow (30 minutes per move). Optimizations included aggressive deletion of intermediate variables (reducing memory from 10GB to 300MB), fast regex matching techniques (e.g., specific anchors), and writing specialized instructions to replace composite operations.
- 'Pointless' Computing: The author emphasizes the value of undertaking 'entirely pointless things' as a fun way to learn deeply about diverse computer science concepts.
Regex Chess stands as a testament to creative problem-solving and the unexpected capabilities of programming tools when pushed to their limits, offering a compelling demonstration of how complex algorithms can be reimagined within severely restricted computational models.