How to Build a Chess Engine and Fail
As part of my undergrad work, I used similar principles to the article (steady state genetic algorithms) to create a bot capable of playing Reversi where the fitness function was loosely defined as a set of "weights" on each square across the 8x8 board. These were used as part of the evaluation function in the classic minimax algorithm.
We trained over the course of 5-6 days, and the end generation was capable of beating an intermediate player but got completely destroyed by experts. It was a fun project!
I built a list of simple games in pygame with code and solver generated by AI.
Have implemented 2048, Minesweeper, Sudoku and chess. First three are single player games have made good progress.
I still don't understand UCI interface and have not thought through chess solving. Hope will take another try this weekend
I especially enjoyed the link to The Bitter Lesson by Rich Sutton, which I hadn't read before. Now I wonder what "discoveries" have been built into today's AI models and how they might come to be detrimental.
All this I guess comes after laying the ground work, like implementing a bitboard representation or something else, and implementing the logic for being able to tell, whether a move is valid or invalid. That in itself is already a lot of work. iiuc the idea here is "merely" writing the engine, and take everything else as a given.
This is something that's been on my bucket list for a while now, although I'd do it using "normal" programming instead of DL.
i feel like if you can bruteforce every possible board configuration for the next 3 turns and then make the move that leads to more desirable outcomes, that ought to be enough to thrash most amateurs. Probably not good enough to beat somebody who actually understands chess tactics on a deeper level, but I expect most non-masters are just "winging it" and making things up as they go along, so a machine that can think farther ahead than you would win more often than not.
But like I said, this is all just me fantasizing about a project I haven't even started yet so my hypothesis could easily be wrong.
Doesn’t look like failure to me - looks like a fun project that disproved your distillation hypothesis!
Great write up and thanks for sharing.
> To be exact every participant has a maximum of 1024 tokens at his disposal to craft the best chess bot they can.
I'd be quite tempted to try linear genetic programming with a variant of a Brainfuck-style UTM for this kind of constraint. Assuming 1024 tokens = 1024 bytes = 1024 instructions, I think there is some degree of performance that is feasible.
This is really interesting to me because hand-coding BF to do something like chess is absolutely beyond me. I wouldn't even know where to begin. A LGP-coded BF program would almost certainly outperform anything I could design with my own hands.
Why build a chess engine these days, just use an LLM?
I don't really know how to do that but I'm really putting in my effort
I am curious why the author chose a genetic algorithm rather than standard backprop to distill the evil. Logistic regression seems like a pretty reasonable choice and it’ll be a lot faster than a genetic algorithm. Add an L1 penalty for sparsity.
In the past I’ve tried distilling not just the eval function but the outcome of the search (something like depth 20) in a neural net. It kind of works, but not very well until the net is pretty big. Deepmind did something similar.