Can chess, with regular expressions? Yes. Can chess, with regular expressions.

Over the holidays I decided it's been too long since I did something with entirely no purpose. So without further ado, I present to you ... Regex Chess: sequence of 84,688 regular expressions that, when executed in order, will play a (valid; not entirely terrible) move given a chess board as input. Here, I'll show you.

Specifically, this is the entirety of the program that is playing a move against you (no really, I'm not kidding, it really is this short):

By the end of this post you'll (hopefully) understand why this sequence of regular Now some snobby people when they see this are going to say something like "yoU SaiD yoU'Re GoIng to uSe rEGUlar EXPresSIONs buT thESE ArE nOT ReGULaR !!" I do not care. expressions is possible, and also what the specific regular expressions do.

(If you're someone who subscribed to this blog in the last six months or so, and have gotten accustom to me writing about "serious" and "important" things, please treat this as your fair warning that this is MY WEBSITE and I MAKE THE RULES HERE and so today you're learning about RegexChess whether you like it or not.)

As always, code for this project is available on GitHub.

Getting Started: A Regular Expression CPU

So how are we going to get regular expressions to play chess? Well, by making a regular expression computer, of course! More specifically, we're going to design a Branch-Free, Conditional-Execution, Single-Instruction Multiple-Data instruction set. And then make a sequence of regular expressions that interpret these instructions. (Kind of like a GPU instruction set. And a bit of ARM. But a lot slower.) And then from there we can program our new computer to play chess. So let's get started.

(Some people may say I have an unhealthy obsession with building weird computers, c.f. my game of life computer or my printf computer. Those people are wrong, and just have an unhealthy obsession with the banal and ordinary.)

Computer Design

Let me get started by explaining how I'm going to organize the data that the computer is going to operate over. Because we're working with regular expressions, the current state of the computer is going to be represented as a single string containing both the program "stack", and all variables in the following format:

%% #stack: top item on stack second item on stack .... #variable1: value 1 #variable2: value 2 ... #variablek: value k

Each instruction will either manipulate some variables on the stack, or will read or write to a given variable. Let's look at some basic instructions.

Basic Stack Operations

The Push Instruction

Here's the implementation of the push command that adds a value to the top of the stack:

You should read the return type of these functions as a list of tuples. Each tuple represents a regex transformation to apply, where the left element is the pattern to match, and the right element is the replacement.

As a brief regular expression refresher. Each tuple in this list has two parts: the regular expression, and the replacement. A regular expression will match a string if it can find a substring of whatever it's being applied against (the state, in our case). Most characters in a regular expression match themselves, but parentheses create a "match group" that can be referenced later.

The second argument is the replacement string. Again, most characters mean "Replace with this character", but special sequences like \g<1> are back-references that refer to previously captured groups. In this case, \g<1> references the first captured group (anything matched within the first set of parentheses)---which in this case is the "%%\n#stack:\n" header.

So, as a result of this operation executing on the stack, we find the occurrence of "%%\n#stack:\n" in the state, and insert the constant value below that (to the top of the stack).

Let's see this in practice. Say we start with an empty stack:

%% #stack:

If we execute push("hello"), the regular expression will:

• Match the pattern %%\n#stack:\n at the start of our state
• Capture this header into group 1 (the parentheses in the pattern create this capture group)
• Replace it with the captured group (\g<1>) followed by our constant "hello" and a newline

This gives us:

%% #stack: hello

If we then execute push("world"), the same process repeats and we get:

%% #stack: world hello

The regular expression always matches at the top of the stack area, so new items get pushed on top while preserving the existing stack contents below them.

The Pop Instruction

The pop instruction removes the top element from the stack:

Here we start to see a few of the special operators that make regular expressions powerful. The [^\n] block means "match any character that isn't a newline" and the * means "match zero or more of these." So taken together we're looking for a line that starts with "%%\n#stack:\n", and then on the next line, zero or more characters that aren't a newline (so, the entire line). The replacement is just the first line, which has the effect of removing the second line, popping the top of the stack.

Let's see how this works in practice. Say we start with this stack:

%% #stack: world hello

When we execute pop(), the regular expression will:

• Match the pattern beginning with %%\n#stack:\n (captured in group 1)
• Match any characters until the next newline (captured in group 2 - the "world")
• Replace everything matched with just group 1 (the header), effectively removing the top element

This gives us:

%% #stack: hello

Each pop operation removes exactly one element from the top of the stack, preserving any remaining elements below it.

Variable <-> Stack Instructions

Variable Lookup

To load the contents of a variable onto the top of the stack:

This regular expression is a bit more complex than our previous ones. Let's break down what it does:

• The [^%]* matches basically any character (% only appears at the start of the program) and so lets us find any variable anywhere in the program.
• The [^\n]* matches the variable's value by capturing everything until the end of the line
• The replacement creates a copy of the value and places it on top of the stack

Let's see how this works in practice. Say we start with this state:

%% #stack: #foo: hello #bar: world #baz: 42

If we execute lookup("bar"), the regular expression will:

• Match the stack header in group 1
• Match everything up to and including "#bar: " in group 2
• Match "world" in group 3
• Use these groups to reconstruct the state with the value copied to the top of the stack

And so running the replacement will result in the following state:

%% #stack: world #foo: hello #bar: world #baz: 42

The lookup operation preserved the original variable and its value while also placing a copy of the value on top of the stack. This allows us to read variable values without modifying them.

Variable Assignment

Assigning to a variable presents an interesting challenge: we don't know if the variable already exists. We need to handle both cases: updating an existing variable or creating a new one.

Let me show you the implementation and then I'll walk you through it case by case.

To begin let's assume the variable already exists. That is, the stack starts off looking like this, and assume we're calling assign_pop("bar"):

%% #stack: world #foo: hello #bar: something #othervar: othervalue

When we run this regular expression list, we create the following capture groups:

%% #stack: world #foo: hello #bar: something #othervar: othervalue

After the replacement operation, we get this output:

%%` #stack: #foo: hello #bar: world #othervar: othervalue

Now we proceed on to the next instruction, and we don't match it because the second regex fails if there's a back-tick after the program start %%. So nothing happens. And then finally, the third regex cleans things up for us.

Handling Non-Existent Variables: Let's consider what happens if the variable doesn't already exist. Again, assume we're calling assign_pop("bar"):

%% #stack: world #foo: hello #othervar: othervalue

The first regex tries to match but fails because there is no "#bar" anywhere. So it doesn't do anything. But now the second regex tries to match and succeeds. It creates the following capture groups:

%% #stack: world #foo: hello #othervar: othervalue

From here, we perform the rewrite and get the following output:

%% #stack: #foo: hello #othervar: othervalue #bar: world

And then the third regex is applied and does nothing.

There are lots of instructions that use this trick to make sure we don't apply things in the order we don't want. For example, as an exercise for yourself, try to understand how the "is equal" instruction works:

(Branch-Free) Conditionals

Programming languages, in order to be interesting, usually need to have some kind of control flow. It's very hard to write some program without ever having an if statement. So let's now show how we're going to do this. (And I hope you did your homework, because we're going to use the same conditional execution trick again!) Here's the implementation of a conditional instruction:

Let's walk through how this is going to work, starting with the case where the top of the stack is False.

%% #stack: False #variable: value

Initially, the first regex will fail to match, because the top element on the stack isn't True. So we go to the next regex, and see if it applies. This one does match, and makes the corresponding match groups.

%% #stack: False #variable: value

After we apply the replacement, we get the following stack.

%tag #stack: False` #variable: value

(And finally, using the same cleanup trick, we'll remove the used marker.)

Now see what happened here? The program no longer begins with %%. This means that EVERY instruction will fail to match, because they always make sure that the program begins with %%. So nothing else will happen.... until we reactivate it later with the following simple instruction:

Let's now return to the True case for the conditional. This is the easy case: we basically don't do anything at all. We replace the stack with True` on the second regex, and then delete this line on the third. Easy.

Notice that this means our code is actually branch-free, because every instruction is a conditional instruction. (Kind of like ARM's predicated execution, where most instructions can be conditionally executed based on status flags rather than using explicit branch instructions.)

Loops (are impossible)

Because our program just consists of a sequence of regular expressions, you can't loop at all! That, technically, means we can't actually perform Turing Complete But we can do any bounded computation by just unrolling any loops we may have. And fortunately computing the next move in a chess position is a bounded computation, so we can do just that.

Single-Instruction Multiple-Data

And now for my absolute favorite part of the language we've developed. By the magic of regular expressions (and the fact that they perform substitution globally over the entire string), we can run multiple threads simultaneously!

That is, if we just write our state string as:

%% #stack: int0000101010 int0001011100 %% #stack: int0000001101 int0110000000

When we call binary_add(), both additions happen simultaneously! After execution:

%% #stack: int0010001110 %% #stack: int0110001101

The reason this happens is because the regular expression matches work globally. When we match the "begin thread" operator (%%) twice, we get to perform operations on both threads simultaneously.

So how do we actually make use of this feature? Let's look at some instructions that help us create and manage threads.

The Fork Instructions

Here's a simple fork instruction that splits every currently running thread into two, with the second one starting off inactive with a given tag:

We can also, for example, fork() on a boolean, giving one thread the True case and another the False case. (This is something like McCarthy's Amb operator reference)

Let's see what happens when we apply multiple forks. Starting with a simple state:

%% #stack: somevalue #x: 10

After calling fork_bool("condition"), we get:

%% #stack: somevalue #x: 10 #condition: True %% #stack: somevalue #x: 10 #condition: False

If we then call fork_bool("c2"), each existing thread splits into two:

%% #stack: somevalue #x: 10 #condition: True #c2: True %% #stack: somevalue #x: 10 #condition: True #c2: False %% #stack: somevalue #x: 10 #condition: False #c2: True %% #stack: somevalue #x: 10 #condition: False #c2: False

Now we have four simultaneous execution paths, exploring every possible combination of our boolean conditions at the same time. This is exceptionally useful for chess, when we might frequently want to consider multiple possible board states at the same time, and (for example) score them to see which is best. Instead of having to loop over every possible board state, we can just pretend we were doing it once but have them all happen at the same time.

Compiling to our little language

Now that we have our CPU emulator, we can build a compiler to target our new assembly language.

"But wait I'm not reading this post for a lesson in compilers!" you say?? Fair point. Also I didn't go into this project trying to build a compiler, so instead what I have is more of a macro-assembler. It turns python-ish programs like this:

Into a sequence of instructions like this:

push(1) assign_pop('a') push(2) assign_pop('b') lookup('a') lookup('b') binary_add() assign_pop('next') lookup('b') assign_pop('a') lookup('next') assign_pop('b') [... repeated 8 more times ...]

Compiling Through Symbolic Execution

Rather than writing a traditional compiler with parsing and code generation phases, I took an unusual approach: symbolic execution. The key insight is that we can "execute" the Python code in a special way that records what operations would happen rather than actually performing them.

Here's how it works: the variables argument isn't actually a dictionary---it's a special object that records every operation performed on it. It creates what we call a "trace" of the execution. When you write:

a = b + 1

The tracer object records four operations:

1. A lookup of variable 'b'
2. A push of the constant 1
3. A binary_add operation
4. An assign_pop to variable 'a'

Handling Control Flow

The trickiest part of this approach is handling branching control flow---if statements, specifically. (What about loops? We don't have those, so I never use them. Loops can only have constants.) We need to make sure we capture all possible execution paths. Here's how we do it:

When we hit a conditional, we create two separate paths in our trace---one for when the condition is true, and one for when it's false. Each path records its own sequence of operations. Later, we merge these paths back together.

For example, this Python code:

Generates something like this trace structure:

lookup('x') # Get x's value push(0) # Push 0 greater_than() # Compare cond('tag1') # Branch on result # True path: push(1) assign_pop('y') pause('tag2') reactivate('tag1') # False path: push(2) assign_pop('y') reactivate('tag2')

The magic of the compiler lies in how it handles control flow through branching. Let me explain this in a little bit more detail.

When our compiler first starts processing code, it maintains a single linear path of instructions in the CallTree. Each instruction gets appended one after another as we go. This list of instructions looks entirely linear. When we reach a conditional statement, though, things get interesting.

Consider what happens when we hit a conditional statement like the x > 0 conditional above. When this happens, I detect it, and create a branch in the call tree representing the two paths simultaneously. Then, I just pretend this conditional was true, and fill out the true case of the tree. When we reach the end of the program we've done some of our compilation, but not all of it.

Now comes the clever part. When compiling, we don't just trace the program once. We trace many times. And each time we trace, we arrange for the conditionals to go through whichever branch has been taken least often. In this way, the second time around, we record the instructions for the false branch.

Finally, once the conditional is over, we detect this and merge the two branches back together. This branching and merging mechanism is more than just a clever trick---it's essential to how our regex-based CPU actually works. When we convert this tree into instructions, each branch gets translated into a conditional regex operation (using our cond instruction) that can selectively activate and deactivate different parts of our program state. The merge points become reactivate instructions that ensure we continue execution on the correct path.

Writing a Chess Engine

Okay, so we're finally to the part of this post where we can actually start writing a chess engine. (And at the part where some of the emulator design decisions will make sense.)

For the most part, this is entirely straightforward and mirrors how you would write a chess engine in any other programming language. But this branching thing with SIMD is what gives us the power to make things go fast.

Let's consider the following (simplified) program that calculates all the valid pawn moves.

Step 1: Finding the Pawns

The find_all_pawns() function scans through our board representation, looking for white pawns (represented as 'P' in the FEN string). It returns a list of the position of each of these pawns. As an example, if we run our program on the following position with three pawns on d2, e2, and f2, this creates a semicolon-separated list in the pawnpos_lst variable as follows

%% #stack: #board: 4k3/8/8/8/8/8/3PPP2/4K3 #pawnpos_lst: d2;e2;f2;

Step 2: State Creation

Now comes the clever part. The fork_inactive instruction, as described above, duplicates our entire program state. Each time it runs, it creates an exact copy of the currently running thread, but marks the new copy with %waiting instead of %%. (Recall this means instructions won't apply to this thread.) At the same time, it takes one position from our pawnpos_lst and assigns it to a new variable pawnpos in the copied state.

When our loop runs three times, each fork_inactive operation splits off a new parallel universe where we'll process a different pawn. The regex operation that does this copying preserves all existing variables but adds the new pawnpos variable with the specific position for that copy to process.

%% #stack: #board: 4k3/8/8/8/8/8/3PPP2/4K3 #pawnpos_lst: %waiting #stack: #board: 4k3/8/8/8/8/8/3PPP2/4K3 #pawnpos: d2 %waiting #stack: #board: 4k3/8/8/8/8/3PPP2/4K3 #pawnpos: e2 %waiting #stack: #board: 4k3/8/8/8/8/3PPP2/4K3 #pawnpos: f2

Step 3: Activation Switch

Recall that the pause and reactivate operations work by manipulating the %% markers that indicate which states are active. The pause("main") operation changes our original %% to %main, effectively deactivating it. Then reactivate("inactive") finds all states marked with %waiting and changes them to %%, making them the new active states.

Step 4: Parallel Move Generation

Here's where the SIMD magic happens. Each check for a possible move---forward one square, forward two squares, or diagonal captures---executes across all active states simultaneously. When we check if the square ahead is empty, we're actually checking d3, e3, and f3 all in one operation. For each valid move, we add this to the candidate_moves list.

(I've significantly simplified the program for visual purposes here. In reality I don't work directly over the FEN strings but expand them to 64 independent variables for each of the 64 squares and read and write to these squares directly. This makes processing the board state much easier. But for the purpose of this blog post it's easier to show visually as if it worked on FEN strings alone.)

%main #stack: #board: 4k3/8/8/8/8/8/3PPP2/4K3 #pawnpos_lst: %% #stack: #board: 4k3/8/8/8/8/8/3PPP2/4K3 #pawnpos: d2 #candidate_moves: d3;d4 %% #stack: #board: 4k3/8/8/8/8/8/3PPP2/4K3 #pawnpos: e2 #candidate_moves: e3;e4 %% #stack: #board: 4k3/8/8/8/8/8/3PPP2/4K3 #pawnpos: f2 #candidate_moves: f3;f4

Step 5: Merging Results

The final merge operation combines all the candidate_moves lists from our parallel states. It first switches activation back to the main state using pause and reactivate. Then merge_variables_from_threads (again, a pseudo-op I've made up for visual clarity, in practice this requires like 10 different instructions on my real machine) match all the candidate_moves lists across our inactive states and concatenates them together.

What this means is that while the code we wrote code looks like it processes one pawn at a time, our regex engine's ability to process multiple states means we're actually handling all pawns simultaneously. Every operation, from checking empty squares to building move lists, happens in parallel across all our active states.

And this is how every piece operation works. Because this post is already getting quite long, I won't walk through each piece one by one, but if you're interested definitely go look at the chess-engine.py for the details.

Playing a Turn

Now let's walk through the overall game loop that handles everything.

Say we're at the start of a game, and the human enters "e2e4" (the king's pawn opening). Here's how our code processes this:

Step 1: Reading the Move

Initially, the function from_pretty_utf8_to_fen() converts our pretty-printed board with Unicode chess pieces back into FEN notation. It also extracts the source and destination squares from the input:

%% #stack: #board: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR #src: e2 #dst: e4

Step 2: Move Validation

Now we need to check if this is a valid move. Rather than writing entirely new code that explicitly checks if a move is legal, we use our parallel processing power again. The process works in three stages:

First, make_move applies the human's move to create a new board state:

%% #stack: #board: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR #after_move: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR

Then compute_legal_boards generates all possible legal moves from the starting position, creating a list like:

%% #stack: #next_boards: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR; rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR; rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR; ...

Finally, fork_on_list creates parallel states for each legal board position:

%% #stack: #board: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR %% #stack: #board: rnbqkbnr/pppppppp/8/8/8/3P4/PPP1PPPP/RNBQKBNR %% #stack: #board: rnbqkbnr/pppppppp/8/8/8/4P3/PPPP1PPP/RNBQKBNR

The destroy_active_thread() call removes any thread where the board doesn't match after_move. In our case, only the e2-e4 position survives, confirming it's a legal move. (If no legal move is made, I have a special regex that will replace the entire output with just the hard-coded text "Illegal Move.")

Step 3: Computer's Reply

Now we repeat a similar process to find the best reply. First, compute_and_score_legal_boards generates all possible black responses. This function does a little bit of magic, and when it returns the next possible boards, it returns with each board the score of that board after whites next best move I'll explain how this works below. But suffice to know that what this function returns for now the possible positions as compute_legal_boards does, but also the score of the position. (This is where the MiniMax happens. The score here is how good each position is from the player's perspective, after they have made their best reply move.)