Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions

This is delightfully insane! I don't think I would say it doesn't play _entirely_ terrible though ;) It's playing really bad, but it could be worse and it's already super impressive that it can even generate legal moves.

This is amazing. I'm at loss for words.

During my CS years I remember being fascinated by NFA's, as opposed to boring single universe DFA's.

For some reason I internalized that I would never see something like an NFA implemented beyond text books.

Then came Carlini.

You've mentioned that the initial version needs 30 mins for a step, but after the optimization, it decreases to seconds. I was wondering what optimization like \n could give such a huge improvement? Like what does it do?

It would be different, if somehow all those 84688 regexes were coded by hand. Then it would be a piece of art.

It would be different, if the number of regexes was maybe below 300, and it still plays acceptably. The sheer number of regexes kind of defeats the purpose.

At that code size, a much better engine can be written, or other kind of code for an engine be generated. Regexes themselves are not really something we should strive to use more either. Maybe its intentional badness kind of makes it art?

The technical write up is worth perusing but I played a game before reading and accidentally found a winning strategy immediately. I'm not sure if this is a result of the 2-ply nature of the engine or if the mentioned deficiencies account for this but the computer did not act to prevent checkmate in 1 (without any intervening check); the game I played was (in algebraic notation): 1. e4 e5 2. kf3 kf6 3. kxe5 kxe4 4. d4 kxf2 5. Kxf2 a5 6. Qf3 b5?? 7. Qxf7 1-0

This reminded me of Tom7's video where he made a bunch of ridiculous engines and pitted them against each other (and against "diluted" versions of Stockfish):

https://www.youtube.com/watch?v=DpXy041BIlA

https://tom7.org/chess/

For people who are interested, here is the solution. In standard PGN, the solution is:

1. e4 e5 2. Nf3 Nf6 3. Nxe5 Nxe4 4. Qe2 Nxd2 5. Nc6+ Ne4 6. Nxd8 Kxd8 7. Qxe4 a6 8. Bg5+ Be7 9. Qxe7#

In the Stockfish notation this engine uses, White’s moves are:

1. e2e4 2. g1f3 3. f3e5 4. d1e2 5. e5c6 6. c6d8 7. e2e4 8. c1g5 9. e4e7

Here is a Lichess analysis of this game:

https://lichess.org/WnMF3LpX

(In terms of Regexes, Javascript has a very rich Turing complete Regex library; it’s an open question whether Lua 5.1’s regexes are Turing complete, but they are good enough for the text processing I do)

This is like a fever dream.

Upon reading the title, this is one of those "I know that's possible, but I'd never bother to implement it" things, although this particular implementation isn't exactly what I had in mind.

Not sure it's completely accurate. I played a standard queen's gambit accepted, took black's queen which it immediately blundered, then tried to move my queen from c5 -> e5 and the game ended immediately showing:

  *Illegal Move*
  You Lose.
  Game over.

A little disappointed, since it's of course a valid move.

Previously posted: https://news.ycombinator.com/item?id=42619652

And now you have 84,689 problems

2025

Brilliant. The Chinese room thought experiment as a chess engine.

This is absurd. I did not realize you could do nearly this much computation in regex.

"Memory plus search is all you need"

Alternate title:

Compiling Python to a Branch-Free SIMD Virtual Machine via Extended Regular Expression String Rewriting