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

Re:Regex Chess: A 2-ply minimax chess engine in 84,688 regul... by karlgkk on Tuesday May 19, 2026 @12:37AM (#48189224)

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.

[ Parent | on HN ]

Re:Regex Chess: A 2-ply minimax chess engine in 84,688 regul... by Patryk27 on Tuesday May 19, 2026 @02:18AM (#48189866)

Regular expressions are not Turing-complete.

[ Parent | on HN ]

Re:Regex Chess: A 2-ply minimax chess engine in 84,688 regul... by 0xffany on Tuesday May 19, 2026 @02:45AM (#48190045)

True 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

[ Parent | on HN ]

Re:Regex Chess: A 2-ply minimax chess engine in 84,688 regul... by benchloftbrunch on Tuesday May 19, 2026 @08:20AM (#48192363)

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)

[ Parent | on HN ]