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.

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)

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 is like a fever dream.

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

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.

"Memory plus search is all you need"

2025

And now you have 84,689 problems

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

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

Alternate title:

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