一个 84,688 个正则表达式组成的双层极小极大值象棋引擎

Regex Chess: A sequence of 84,688 regular expressions that can play a valid (not entirely terrible) move given a chess board as input. It's a simple program consisting mainly of a list of regular expressions that operate on a stack-based data structure representing the computer state.
- Computer Design: Organizes data as a single string with the program "stack" and variables. Basic instructions include Push (adds a value to the top of the stack), Pop (removes the top element from the stack), variable Lookup (loads a variable's value onto the stack), and variable Assignment (handles variable creation and update).
- (Branch-Free) Conditionals: Uses a conditional instruction cond to handle control flow. The program's state is marked with True or False, and instructions are conditionally executed based on these marks. There's also a reactivate instruction to reactivate inactive parts of the program.
- Loops (are impossible): Since the program consists of a sequence of regular expressions, loops are not directly supported. Bounded computations can be achieved by unrolling loops.
- Single-Instruction Multiple-Data: Regular expressions can perform substitution globally over the entire string, allowing multiple "threads" to run simultaneously. Fork instructions (fork_inactive and fork_bool) create parallel execution paths.
Compiling to our little language: Uses symbolic execution to compile Python-like code into a sequence of instructions. Handles branching control flow by creating separate trace paths for true and false cases and merging them later.
Writing a Chess Engine: Applies the above concepts to write a chess engine. Forking is used to handle parallel pawn moves, and other operations like move generation and validation are performed simultaneously across multiple states.
Playing a Turn: The overall game loop includes reading the human's move, validating it using parallel processing, generating the computer's reply with scoring, and keeping the best scoring board.
MiniMax Search (for free): Implements a depth-2 minimax search by generating pseudo-legal moves and deleting those that leave the king in check. This is not a full depth-2 minimax search but gives a reasonable approximation.
Some Performance Tricks: Deletes intermediate variables to reduce computation time and memory usage. Optimizes regex matching by adding a newline prefix to ensure the regex engine skips over most True/False strings. Writes specialized instructions for specific tasks to improve performance. Maximizes parallelism by generating multiple moves or evaluations simultaneously.
Conclusion: Encourages others to do pointless projects like this as it's fun, teaches a lot about various areas of computer science, and there will be more such projects in the future. Mentioned other related articles like playing tic-tac-toe with C's printf and a Doom clone in 13kB of JavaScript.