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.
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.
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.
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.
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.
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:
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 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.
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.
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.
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;
A minimax chess engine in regular expressions
(nicholas.carlini.com)557 points by ilya_m 7 January 2025 | 97 comments
Comments
https://github.com/HexHive/printbf
https://github.com/carlini/js13k2019-yet-another-doom-clone
> 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.
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
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.
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
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.
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.
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?!
What about directly encoding the rules of the game plus some basic strategy?
And just in time when the novelty of playing chess in Postscript (https://seriot.ch/projects/pschess.html) has worn off :)
d2d4 d7d5 c2c4 d5d4 e2e4 d8d4 !? d1d4
I think my priorities are out of line
God bless our soldiers who see that regex is turing complete and choose to implement fun programs. Yall are truly a different breed :)
</Joke>
This is seriously brilliant.
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 << 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...