A minimax chess engine in regular expressions (opens in new tab)

This is from the same gentleman who (among other things) demonstrated that printf() is Turing complete and wrote a first person shooter in 13kB of Javascript.

https://github.com/HexHive/printbf

https://github.com/carlini/js13k2019-yet-another-doom-clone

This point was where this changed from crazy/fun to absolutely extraordinary, where calculations of multiple possible positions all occurred in parallel, running a regex over an increasing series of state & variable sets, aka threads:

> And now for my absolute favorite part of the language we've developed. By the magic of regular expressions (and the fact that they perform substitution globally over the entire string), we can run multiple threads simultaneously!

Also:

> What do you want out of a conclusion to a blog post like this? I don't really have much to conclude. I guess I'll just say that I think more people should do entirely pointless things like this. It's a lot of fun, no one cares how long it takes you to finish, no one cares if it works or not, and incidentally, it teaches you more than you wanted to know about dozens of areas of computer science outside your field.

What a wonderful ethos.

There's a bug somewhere it seems like, as it ends the following game with "Illegal move, you lose", even though it's not an illegal move:

1. e2e4, e7e5 2. d2d4, e5d4 3. d1d4, a7a5 4. g1f3, b7b5 5. b1c3, a5a4 6. c3b5, a4a3 7. b5a3, a8a3 8. b2a3 --> Illegal Move You Lose. Game over.

FEN of game above: 1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8

I fear not the man who plays chess with 84,688 regular expressions, but I fear the man who plays chess with one regular expression.

When I see this sort of thing I just I want to take my hat off and stand in solemn appreciation for the true heroes among men.

The bug with a-file moves has been fixed: https://github.com/carlini/regex-chess/issues/1.

Previously: Chess written in sed https://news.ycombinator.com/item?id=6261314

Of course, the sed version does make use of control flow commands in sed and only probes 1ply (I think) so this version is significantly different in that regard.

This is not only a chess engine, it's a computer and an assembly language, built in only using Regexp

I normally don’t lose so quickly opening with a2a4 !

Compare also https://codegolf.stackexchange.com/q/3503/32575

The idea of doing something without a defined "productive" goal might help to do things differently, discover new ways, and in the end stumble on an innovation?

Tried it, 2 comments:

1) Engine gives a piece early with: 1. b3 b6 2. Bb2 Bb7 3. e4 ??Bxg2

2) when you enter an uppercase letter it says illegal move

Edit: and here I am trying to "stumble" on an innovation and be productive again. Erh... Humans

As it's already been reported in this comment section, at a seemingly random stage of the game when it's the player to move, an error caused by an illegal move is triggered. Happened to me twice already in the opening. Once for a King's knight move to f3 and once for a simple pawn move as follows: 1.Nc3(b1c3) Nc6(b8c6) 2.g3(g2g3) g6(g7g6) 3.Bg2(f1g2) Bg7(f8g7) 4.e3(e2e3) Bxc3(g7c3) 5.bxc3(b2c3) a6(a7a6) 6.c4(c3c4) a5(a6a5) 7.Ne2(g1e2) a4(a5a4) 5.a3(a2a3) saying a2a3 is illegal.

Creative approach. Very impressive if it'd work, but you cannot finish the game, because it doesn't recognize the moves properly. The program understanding and strength is poor, but it was to be expected and it's beyond the point of this intellectual exercise, I guess.

This is truly impressive, I'm in complete awe.

I do think there are some bugs based on playing a game against it. It has a tendency to give up its queen and other pieces. and it blundered mate in 1 at the end of the game when it had moves that led to mate in 2 or 3.

Usually even a 2-ply engine should avoid these mistakes unless the evaluation function is completely silly, which may be the case here, I don't know. I tried looking at the code but it didn't make much sense to me, I'm not smart enough to understand this regex "runtime" based code. Could also be a bug of using < instead of > somewhere, or vice versa, making it choose the worst move instead of the best one.

How long does one single move take to calculate for you folks on a normal phone? On mine (running an i.MX 8M quad-core on Firefox), the first move took several minutes.

It does seem to play worse than it should, by game went: 1. d4 d5 2. c4 dxc4 3. e4 Qxd4 4. Qxd4 5. Bc4 6. Nf3 7. O-O 8. Rd1 9. Qd8#

That's some impressive code wizardry! I thought the 2-ply search would make it respond to a mate-in-1 threat, but the following game demonstrates otherwise:

1. e4 e5 2. Nf3 Nf6 3. Nxe5 Nxe4 4. Qe2 Nxd2 5. Nc6+ Ne4 6. Qxe4+ Qe7 7. Nxe7 Bxe7 8. Nc3 a5 9. Nd5 a4 10. Qxe7#

9. .., Nc6/O-O/Kf8 would have avoided mate in 1. Maybe this is related to the a2-a4 bug noticed by others?!

I love the author's philosophy of doing 'entirely pointless things' for the joy of learning. This project reminds me why I got into programming in the first place - not just to solve practical problems, but to explore the weird and wonderful possibilities of code. The fact that this works at all is just mind-blowing!

Kudoa for this, but it feels like there should be a more direct way? I mean, he first invented basically a general-purpose execution platform. That in itself is cool, but the fact that it then can execute a chess program is not actually that surprising.

What about directly encoding the rules of the game plus some basic strategy?

This is totally what jwz needed for xmas...

a2a3 gives me illegal move game over. What am I missing here?

This is fantastic, but of course strictly speaking the use of back references means these aren't true regular language expressions but the "enhanced" kind that give security headaches for all the big tech firms.

Amazing!

And just in time when the novelty of playing chess in Postscript (https://seriot.ch/projects/pschess.html) has worn off :)

I'd be really helpful if you added some faded square outlines in the background. I think maybe I made an illegal move with a bishop because of misreading the diagonal.

assign_pop() is implemented a bit oddly. In particular, the second regex starts off with

  (%%)([^`]\n?#stack:\n)

This should have just been written like the following (which in fact eq() does do, though eq() is itself missing the %%` -> %% regex):

  (%%)(\n#stack:\n)

As it is the [^`] matches the newline, which is why the \n has to be marked as optional and in practice will always be skipped.

It doesn't seem to know how to handle pawn promotion. It told me it was an illegal move and that I'd lost the game.

It has an interesting response to the queens gambit accepted. Immediate queen sac

d2d4 d7d5 c2c4 d5d4 e2e4 d8d4 !? d1d4

I read 'cheese engine' and excitedly clicked.

I think my priorities are out of line

Tried the queens gambit and the computer hung the queen on move three :)

“Now comes the clever part.”

God bless our soldiers who see that regex is turing complete and choose to implement fun programs. Yall are truly a different breed :)

Sure, but it really should be done using PEG.

</Joke>

This is seriously brilliant.

anyone that can read and understand regex i have concerns for

That's awesome!

I love this.

Playing chess with strings to build datasets for text generation.

I want to share this quick win.

The other day I was asking myself some theoretical chess questions, and wanted to answer them programmatically and needed to build some custom chess datasets for that.

I needed the chess basic routines, like getting the next legal moves, displaying the board, and some rudimentary position scores. I contemplated writing from scratch. I contemplated using some library. But instead I settled for a higher level choice : interfacing with Stockfish game engine over a text interface.

There is something called UCI, which stands for Universal Chess Interface, ( https://official-stockfish.github.io/docs/stockfish-wiki/UCI... ), to use it you start a new stockfish process and write and read from the standard inputs.

So instead of writing bug prone routines to check the validity of board positions, it turn the basic routines into a simple wrapper of parsing task to read and write UCI protocol to use a battle tested engine.

A chess position state is simply defined as a vector<string> representing the sequence of moves. Moves are string in long algebraic notation.

This architectural decision allows for very quick (LLM-powered development) prototyping.

namespace bp = boost::process; bp::ipstream is; bp::opstream os;

bp::child c("../Stockfish/src/stockfish", bp::std_in < os, bp::std_out > is);

void displayBoard( const vector<string> & moveSeq, bp::ipstream& is, bp::opstream& os );

void getLegalMoves( const vector<string> & moveSeq, vector<string>& legalMoves, bp::ipstream& is, bp::opstream& os );

void getTopKMoveAndScoreAtDepthFromPosition(const vector<string> & moveSeq,int K, int D, vector<pair<string,int> >& topkmoves, bp::ipstream& is, bp::opstream& os , bool debug = false);

void displayBoard( const vector<string> & moveSeq, bp::ipstream& is, bp::opstream& os ) {

os << "position startpos moves";

for( int i = 0 ; i < moveSeq.size() ; i++)

{

  os << " " << moveSeq[i];

}

os << endl;

os << "d" << endl;

os << "isready" << endl;

string line;

while (getline(is, line)) { if (!line.compare(0, 7, "readyok")) break; cout << line << endl; }

}

You get the gist...

c4, Qa4, Qxa5, Qc7, Qxc8# lol

I wonder if this is inspired by LLMs which similarly do tons of repetitive processing most of which is unrelated to the final answer.