Chess Engine in 84,688 Regexes
2025-01-07
Nicholas Carlini built a 2-ply minimax chess engine using a mind-bending 84,688 regular expressions as a holiday project. He designed a regex-based virtual machine with a branch-free, conditional-execution, SIMD instruction set. A symbolic execution compiler translates Python code into regex sequences, enabling parallel computation. The engine leverages SIMD to calculate moves for multiple pieces simultaneously, with clever regex optimizations for speed. While limited in depth, it showcases the surprising computational power of regular expressions.