alt.hn

5/14/2026 at 3:30:36 PM

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

 https://nicholas.carlini.com/writing/2025/regex-chess.html

by surprisetalk

5/19/2026 at 9:34:03 AM

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.

by LukaD

5/19/2026 at 2:57:20 AM

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.

by Kaliboy

5/19/2026 at 3:59:57 AM

But... they are equivalent?

by bigdict

5/19/2026 at 5:02:21 PM

Yeah I know, but I thought I was doing purely theoretical excercises.

And we always changed the regex NFA to an equivalent DFA and that was the implementation.

So somehow I managed to internalize the idea that an NFA is purely theoretical and can't be built.

by Kaliboy

5/19/2026 at 4:49:59 AM

Modulo an exponential blowup! That’s like saying P is equivalent to NP.

by xpon

5/19/2026 at 6:49:57 AM

Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.

by tgv

5/19/2026 at 8:01:11 AM

Running NFA is O(nm) not NP.

by DmitryOlshansky

5/19/2026 at 10:23:35 AM

Sorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.

by tgv

5/19/2026 at 12:15:06 PM

So it is NP (in fact P)

by benchloftbrunch

5/19/2026 at 5:53:24 AM

The blow up is exponential for carefully crafted academical regular expressions.

im practice is a good idea to build a DFA from your regex, up front (re2) or lazily (ripgrep)

by froh

5/19/2026 at 6:26:20 AM

No, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization

by pkal

5/19/2026 at 7:31:24 AM

And there are language families where minimal DFA is still exponentially large compared to NFA.

by IsTom

5/21/2026 at 3:18:01 AM

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?

by isaisabella

5/19/2026 at 10:14:35 AM

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?

by zelphirkalt

5/19/2026 at 11:45:33 AM

This is a quintessential, crazy idea that used to be adored on HN. The author, obviously, didn't intend this to be a serious engine.

I wish more submissions began with, “This might be a bit wild, but I wanted to see if it could actually work.”

by LatencyKills

5/19/2026 at 4:16:37 PM

> “This might be a bit wild, but I wanted to see if it could actually work.”

That is how esoteric programming languages start.

by Timwi

5/19/2026 at 11:57:44 AM

Out of curiosity, why wouldn't it work?

by BretonForearm

5/19/2026 at 12:23:55 PM

Oh, I didn't mean that this specific project wouldn't work. I just wish HN were a little friendlier towards projects that are primarily thought experiments.

Some of the best things I've ever created started from, "I wonder what would happen if I tried this crazy approach..."

by LatencyKills

5/19/2026 at 3:00:05 PM

I think it’s because of agent involvement. It takes away the coolness.

by solumunus

5/19/2026 at 4:26:09 PM

What a depressing way to view the world. Sorry this great project wasn't to your taste, but there's no reason to be a dick about it.

by colonCapitalDee

5/19/2026 at 1:00:47 PM

> Maybe its intentional badness kind of makes it art?

I guess it's the whole point of such type of blog posts. Similarly, some people write complicated interactive web pages without using JS, like this https://benjaminaster.com/css-minecraft/. But if you look at the HTML / CSS code size, it's usually huge, but still requires creativity to do that because of constraints. Obviously, it's not something practical or even optimal.

by senfiaj

5/19/2026 at 1:56:12 PM

> Similarly, some people write complicated interactive web pages without using JS (…) Obviously, it's not something practical or even optimal.

There are people who navigate the web with JavaScript turned off, so those experiments do have practical applications.

There are entire projects around not using JavaScript.

https://theosoti.com/you-dont-need-js/

https://github.com/you-dont-need/You-Dont-Need-JavaScript

by latexr

5/19/2026 at 2:15:31 PM

> There are people who navigate the web with JavaScript turned off, so those experiments do have practical applications.

This is practical (and necessary) for relatively basic stuff, such as text content, navigation, basic form / input validation, and things like that. But when people write more complicated things (requiring state management, logical branches, etc), like games, 3d programs, etc, it's much more challenging (also can be sub-optimal) and requires more creativity. I mean they are more of a demo art rather than some strong necessity.

by senfiaj

5/19/2026 at 11:38:22 AM

I was also thinking along the same lines. Interesting, but I'm not sure in which aspect it is an achievement, considering the loop isn't a regex.

Meanwhile, 1K ZX Chess takes fewer bytes of memory than the first four paragraphs from the post.

by matja

5/21/2026 at 3:07:07 AM

You completely missed the point of the article. It's the equivalent of compiling C++ to a Turing machine. Not practical, not optimum, but freaking amazing. Maybe think about it as an art project.

by deterministic

5/19/2026 at 2:54:32 AM

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

by evilsnoopi3

5/19/2026 at 2:48:35 PM

Yep, the scoring function is just piece value difference, so it can only detect checkmate in 0 (i.e., when king capture is available).

by EvgeniyZh

5/19/2026 at 10:17:56 AM

Nitpick: In chess usually "N" is used to mean "knight", because "K" is already taken by "King".

by zelphirkalt

5/19/2026 at 11:00:51 AM

Hey! I had a very similar game

by FergusArgyll

5/19/2026 at 5:06:26 AM

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)

by strenholme

5/19/2026 at 7:43:20 PM

I won with 1. e4 e5 2. Qh5 a6 3.Bc4 a5 4. Qxf7#. I wonder if you could implement a stronger engine in regex (stockfish classic at O(1) nodes is plenty strong already)

by zzazzdsa

5/19/2026 at 2:34:55 PM

I won faster than that:

1.d4 d5 2.c4 dxc4 3.Nc3 Qxd4 4.Qxd4 a6 5.Bf4 a5 6.Bxc7 a4 7.Qd8#

by wavemode

5/19/2026 at 2:51:59 AM

This is like a fever dream.

by VladVladikoff

5/19/2026 at 4:18:22 AM

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.

by userbinator

5/19/2026 at 11:22:18 AM

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.

by deviation

5/19/2026 at 1:42:41 PM

“then tried to move my queen from c5 -> e5”

Are you sure you typed “c5e5”?

It’s very picky about how you specify a move. “e2e4” is fine as a first move, for example, but auto-capitalized “E2e4” is losing immediately. Quite weird, given that there are guardrails against “e2-e4” and “E2-E4” (an alert pops up telling you how to write moves)

by Someone

5/19/2026 at 12:30:46 PM

Yeesh, one illegal move attempt means you just lose? That's harsh...

by benchloftbrunch

5/19/2026 at 2:54:00 AM

2025

by explodes

5/19/2026 at 4:54:38 AM

And now you have 84,689 problems

by asplake

5/19/2026 at 7:04:25 AM

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

by dtj1123

5/19/2026 at 4:36:30 AM

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

by devanshp

5/19/2026 at 7:01:56 AM

It's not just regex. The regular expressions are used to select and perform an action. There's a loop around it with controls the stack. That has more power than the regex.

by tgv

5/19/2026 at 4:37:45 AM

It’s turing complete so you could compile almost any language to regex. You might have to build a vm for some languages, also in regex. The point is, it’s regex all the way down.

by karlgkk

5/19/2026 at 6:18:38 AM

Regular expressions are not Turing-complete.

by Patryk27

5/19/2026 at 12:20:52 PM

Javascript/PCRE/etc regexes have additional features (like backreferences) that give them strictly more computational power than a regular DFA/NFA. (Still not Turing complete though without external control flow to support arbitrary iteration/recursion, like is done here)

by benchloftbrunch

5/20/2026 at 12:18:47 PM

This is an odd comment because it's a famously (imo) over known fact due to cs textbooks and how academia organizes knowledge, optimizing for pushing papers over genuine discovery.

by casey2

5/19/2026 at 8:22:30 AM

"Memory plus search is all you need"

by carlsborg

5/19/2026 at 7:41:11 AM

Alternate title:

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

by casey2

5/19/2026 at 11:09:20 AM

[flagged]

by mashijian

5/19/2026 at 11:00:25 AM

[dead]

by kudesnikz

5/19/2026 at 3:35:58 PM

[flagged]

by CurryH1BSupport