Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
6 days ago
- #esoteric-programming
- #chess-engine
- #regex
- Nicholas Carlini created Regex Chess, a project that plays chess using a sequence of 84,688 regular expressions executed in order.
- The system uses a branch-free, conditional-execution, SIMD instruction set emulated through regex substitutions on a string representing the board state and program stack.
- Instructions like push, pop, lookup, and assignment manipulate variables and the stack via regex patterns and replacements.
- Control flow is handled through conditional execution and reactivation mechanisms, allowing for simulated branching without loops.
- Parallel processing (SIMD) is achieved by forking execution threads, enabling simultaneous evaluation of multiple board states or moves.
- A symbolic execution compiler translates Python-like code into regex instructions, handling conditionals by tracing multiple execution paths.
- The chess engine generates moves by parallelizing operations, such as evaluating all pawn moves simultaneously across forked threads.
- Move validation and computer responses use depth-2 minimax search, leveraging parallel states to score positions and select the best move.
- Performance optimizations included aggressive variable cleanup, specialized regex patterns, and maximizing parallel operations to reduce execution time from 30 minutes to 1-10 seconds per move.
- The project is presented as a fun, pointless exercise that explores regex capabilities, computer architecture emulation, and chess programming.