[Nicholas Carlini] found some extra time on his hands over the holiday, so he decide to do something with “entirely no purpose.” The result: 84,688 regular expressions that can play chess using a 2-ply minmax strategy. No kidding. We think we can do some heavy-duty regular expressions, but this is a whole other level.
As you might expect, the code to play is extremely simple as it just runs the board through series of regular expressions that implement the game logic. Of course, that doesn’t count the thousands of strings containing the regular expressions.
How does this work? Luckily, [Nicholas] explains it in some detail. The trick isn’t making a chess engine. Instead, he creates a “branch-free, conditional-execution, single-instruction multiple-data CPU.” Once you have a CPU, of course it is easy to play chess. Well, relatively easy, anyway.
The computer’s stack and registers are all in a long string, perfect for evaluation by a regular expression. From there, the rest is pretty easy. Sure, you can’t have loops and conditionals can’t branch. You can, however, fork a thread into two parts. Pretty amazing.
Programming the machine must be pretty hard, right? Well, no. There’s also a sort-of language that looks a lot like Python that can compile code for the CPU. For example:
def fib(): a = 1 b = 2 for _ in range(10): next = a + b a = b b = next
Then you “only” have to write the chess engine. It isn’t fast, but that really isn’t the point.
Of course, chess doesn’t have to be that hard. The “assembler” reminds us a bit of our universal cross assembler.
This is so creative wow. Making a cpu using regex is not something I’d thought I would ever see.
Can AI do it today?
“AI” is just a fancy search engine.
“It” doesn’t ever do anything new.
So yes, if you “train” it on a bunch of chess engines, it can spit out something that probably looks like a chess engine.
It might even work.
But it will still just be stealing the work of others.
This is a common but untrue take.
LLMs clearly can do novel things specific behaviour we’ve seen is: applying generalizations it’s never seen, or generalize in ways we haven’t explicitly shown it.
We robustly train OUT those novel ideas because they make for bad toys and tools.
The classic example is that you can analyse the vector space language models use, you can use this to find a transformation that moves an input in a conceptual direction.
You can then have it apply this transformation to any object.
You mostly get gibberish (take the transformation that in general takes the word for male things to female and then apply it to octogons what is the outcome?) but that is precisely what we mostly come up with. We can spend hours, days or years filtering that gibberish to come up with good ideas.
Frankly should an LLM make a valuable novel idea we wouldn’t give it credit. It’d just be a silly line in some kids essay.
Wow, as someone who finds even regex patterns I’ve written can become gibberish after about a week I’m both in awe of and slightly terrified by the kind of mind that could concieve this.
Human mind as a giant Regex.
makes me think of an article i once saw (possibly in scientific american) describing a machine built out of tinker toys that could play tic-tac-toe. it was essentially a mechanical rom lookup table.