A minimax chess engine in regular expressions(nicholas.carlini.com) |
A minimax chess engine in regular expressions(nicholas.carlini.com) |
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 :)
> Because our program just consists of a sequence of regular expressions, you can't loop at all! That, technically, means we can't actually perform Turing Complete But we can do any bounded computation by just unrolling any loops we may have.
Although some (most?) implementations may be. Though by the above quote, the author didn't make use of that.
> Any algorithm that can be implemented by a Turing Machine such that its runtime is bounded by some primitive recursive function of input can also be implemented by a primitive recursive function!
Also, "The Little Typer" book explores a language based on "primitive recursive functions" and shows what can be done in it and how.
[1] https://matklad.github.io/2024/08/01/primitive-recursive-fun...
</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 << " " << 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...
Not gonna lie, I thought that sentence would end with the FPS being done in printf.
There was one month time to complete the competition. But it seems you were allowed to reuse any existing other code.
Looks like this was quite fun to work on.
(I feel a bit sad that I would never be able to get one month of free time to work on this now, due to family and job...)
I was somewhat disappointed to realize they used WebGL for rendering the graphics.
> Once I actually got that working doing all of the math by hand in JavaScript I decided that using WebGL would probably be worth it, and actually probably wasn't cheating all that much. WebGL exposes access to the GPU-enabled rendering engine through JavaScript. While it does abstract away some of the rendering, it's less than I thought---it just supports the ability to do the necessary math efficiently---so I decided this wouldn't be cheating. And fortunately, it didn't take long to reproduce the initial renderer, but this time supporting much better (and more efficient) graphics.
From: https://nicholas.carlini.com/writing/2019/3d-renderer-javasc...
> 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.
For me what I take out of it is the power to sit down, focus your mind on something then who knows the lengths of what is possible. That, and the author is clearly very talented/skilled and creative.
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
But this is a bug as these are legal moves.
help, I'm being nerd-sniped
right away I see backreferences as a potential problem
it would be a VERY long regex, but you're basically encoding a chess engine, so...
Just breathe
Close your eyes
Picture an algebraic representation of the higher order function that represents your real life utility and minimizes the use of resources including your cognitive energy.
Focus on optimizing that function.
Ohmmmmm
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.
I encountered similar bug in the a-column via e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3
In any case, if you know how the regex is constructed, it's not surprising. But I found it fun to actually do the construction, instead of just being theoretically aware of the possibility.
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
I guess playing 'good' chess is not the point, the point is that you can play at all using regexp. (The 'move a2a3 and lose as not considered legal' is more serious then it not actually playing well).
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?!
Try: c4, Qa4, Qxa5, Qc7, Qxc8# lol
What about directly encoding the rules of the game plus some basic strategy?
In chess the word "strategy" is used for something different than "tactics". My tester can decide to sacrifice a knight to get pawns the way he wants (strategy), my chess program on the other hand is better at tactics (looking ahead a few moves and setting up a fork https://en.wikipedia.org/wiki/Fork_(chess)
Lasker's famous quote is "better a bad plan than no plan at all" but chess engines play superhuman chess with superior tactics and no strategy. There's nothing like the "basic strategy" in blackjack, rather you can make a very strong chess program by the exhaustive search he's using, but you have to optimize it a lot.
Bad news if you're almost done with a game and enter a move with the wrong case.
And just in time when the novelty of playing chess in Postscript (https://seriot.ch/projects/pschess.html) has worn off :)
(%%)([^`]\n?#stack:\n)
(%%)(\n#stack:\n)
I got the signs wrong and it managed to fool's mate itself!
I struggled with testing for a while because when it makes bad moves you don't know if you correctly coded a bad chess engine or incorrectly coded a bad chess engine. Eventually I started using chess puzzles
https://www.chessprogramming.org/Test-Positions
which are not unit tests because they take seconds to run, but unlike a real game where there is no right move, there really is a right solution. BK.01 from
https://www.chessprogramming.org/Bratko-Kopec_Test
is a particularly nice one because it runs quickly!
I know what you're describing well, I've dabbled quite a bit in chess engine dev myself, and I'm planning to get back into it soon; I've got some interesting new ideas recently I wanna try out(once they're fleshed out enough to actually be implemented, right now they're just fanciful ideas I'm kicking around my head).
Testing is a bitch though, for sure. I know that stockfish is constantly being playtasted against itself, with a new instance spawned for every pull request etc, and then given an elo rating. That way they can tell if a potential change makes it weaker or stronger.
Debugging isn't easy either. Forget about stepping over code in the debugger. You have no idea whether the bug is only triggered after billions of nodes. That's a lot of stack frames to step through. And forget about debug prints too, for the most part, because putting an unconditional debug print in your search() , qsearch() or eval() will quickly lead to gigabytes and gigabytes of output...
Only helpful thing I found was to use asserts. Find invariants, and in your debug version check them every node, die if they don't hold and barf out your stack frame or a core dump. If you're lucky the bug is somewhere near where the assert failed in the call tree. Even that isn't guaranteed though.
You could argue that rasterization itself is being taken care by the implementation, though.
Still, impressive for "a pile of regexen".
It's like the problem of solving the Rubik's cube. If you look at it in terms of geometry and spatial intuition it's intractable. If you treat it as an abstract algebra problem and break it down into "solve the top of the cube, solve the middle row of the cube, solve the bottom of the cube" and then develop a set of operators that will let you permute certain parts of the cube it takes a moderate amount of skill, persistence and concentration.
CS students do exercises such as writing moderately complex programs for a Turing machine and it's an exercise like what he did.
====
Funny my project last month was a chess engine. For a long time I'd wondered if I could make a decent MCTS chess engine but someone close to me has been getting serious about chess (usually wins against the random person, usually loses at the chess club, is fighting hard to get up the bracket) so writing a program that was a match for him seemed like a fun and meaningful project and I decided to try the conventional route of alpha-beta search.
If you tried to write a chess engine from zero you'd probably struggle, but the lifetime value you get out of education (CS or otherwise) is looking things up the literature, learning from other people's experiences, and putting it to work. So this has been my guide
https://www.chessprogramming.org/Main_Page
I started out with Python with the goal of making something tiny and stylish and started out with a move generator from
https://python-chess.readthedocs.io/en/latest/
and once I got the signs right in alpha-beta negamax (when I had them wrong it discovered https://en.wikipedia.org/wiki/Fool%27s_mate) it beat my tester several times before he regrouped, traded a knight for a good pawn structure, and got his first win.
The next goal is to take it to the chess club which means it has to respect time control. I switched to Java because its faster and because it is easy to have a comms thread interrupt a think thread. The first try wasn't faster because my move ordering was terrible. I was much faster implementing it though because I could cut and paste the test cases I had in Python and if I knew anything at this point it was the signs in negamax.
https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... is not only good for time control but gets better move ordering and I'm in the middle of implementing that. It would take me years to find out that Iterative Deepening works a lot better than you might expect, the Killer Heuristic, etc. Reading is my superpower.
Though I've never seen people accomplish stuff like a) understand regex; and b) write a compiler for it without "persistence and concentration.". Perhaps some get it delivered through divine apparition of some kind.
What is it that really triggered your lengthy response and the narrative..., I really fail to understand, sorry.
A quick way to verify this is to download the repo, remove everything other than main.py and regex-chess.json, and the programme will still work.
All the other python files are building up to regex-chess.json, see e.g. the imports and output to write_regex_json.py.
There is only a single printf written in the source code.
``` function printg(arg) { printf(arg); } ```
Also, those regexes are directly translated from the equivalent and much smaller FSM. Regexes are necessarily complex only because they have Kleene stars and nothing else; it's like representing every Boolean circuits with NAND, which is of course possible and a little fun fact but the process itself isn't exactly fun to me.
Regular languages admit words of arbitrary length. Eg a regular language can tell you whether 461523850177206879302813461556288524354486376376930935555512181511680646984669431923718933249775297346246192616509695718413981019441670321942082230577379960485875768935619924872490629853314107285524330300421382702242540015152210668552218484465230532702298574921915359545891160565971424053668201732275877291369 is divisible by 7. But a human would have a harder time with this than with the paren example given by the grandfather comment.
You don't need to have every state in an FSM be explicitly constructed up-front.
The pdf you mention is great, btw.