4 ms·
Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
- VladVladikoff 6mo agoThis is like a fever dream.
- explodes 6mo ago2025
- evilsnoopi3 6mo agoThe 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
- zelphirkalt 5mo agoNitpick: In chess usually "N" is used to mean "knight", because "K" is already taken by "King".
- FergusArgyll 5mo agoHey! I had a very similar game
- EvgeniyZh 5mo agoYep, the scoring function is just piece value difference, so it can only detect checkmate in 0 (i.e., when king capture is available).
- Kaliboy 6mo agoThis 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.
- bigdict 6mo agoBut... they are equivalent?
- xpon 6mo agoModulo an exponential blowup! That’s like saying P is equivalent to NP.
- froh 5mo agoThe 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)
- pkal 5mo agoNo, 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 https://en.wikipedia.org/wiki/DFA_minimization
- IsTom 5mo agoAnd there are language families where minimal DFA is still exponentially large compared to NFA.
- tgv 5mo agoDepends 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.
- DmitryOlshansky 5mo agoRunning NFA is O(nm) not NP.
- userbinator 6mo agoUpon 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.
- deleted 6mo ago[deleted]
- devanshp 6mo agoThis is absurd. I did not realize you could do nearly this much computation in regex.
- karlgkk 6mo agoIt’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.
- Patryk27 5mo agoRegular expressions are not Turing-complete.
- 0xffany 5mo agoTrue in the CS Theory space, but most modern regex engines implement a few niceties which make their "regex" turing complete. https://blog.poisson.chat/posts/2024-06-18-turing-regex.html https://blog.poisson.chat/posts/2024-06-18-turing-regex.html
- benchloftbrunch 5mo agoJavascript/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)
- tgv 5mo agoIt'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.
- casey2 5mo agoThis 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.
- asplake 6mo agoAnd now you have 84,689 problems
- strenholme 6mo agoFor 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 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)
- neuroelectron 5mo agoPreviously posted: https://news.ycombinator.com/item?id=42619652 https://news.ycombinator.com/item?id=42619652
- dtj1123 5mo agoBrilliant. The Chinese room thought experiment as a chess engine.
- casey2 5mo agoAlternate title: Compiling Python to a Branch-Free SIMD Virtual Machine via Extended Regular Expression String Rewriting
- carlsborg 5mo ago"Memory plus search is all you need"
- LukaD 5mo agoThis 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.
- zelphirkalt 5mo agoIt 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?
- matja 5mo agoI 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.
- LatencyKills 5mo agoThis 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.”
- BretonForearm 5mo agoOut of curiosity, why wouldn't it work?
- LatencyKills 5mo agoOh, 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..."
- solumunus 5mo agoI think it’s because of agent involvement. It takes away the coolness.
- kudesnikz 5mo ago[dead]
- mashijian 5mo ago[flagged]
- deviation 5mo agoNot 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.
- benchloftbrunch 5mo agoYeesh, one illegal move attempt means you just lose? That's harsh...
- Someone 5mo ago“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)
- CurryH1BSupport 5mo ago[flagged]
- Rendello 5mo agoThis 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://www.youtube.com/watch?v=DpXy041BIlA https://tom7.org/chess/ https://tom7.org/chess/
- isaisabella 5mo agoYou'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?