A distraction of sorts
You might think that while a software developer is on Christmas vacation the last thing he might want to do is sit in front of a computer and noodle around with code — and you would be wrong. I think I probably speak for most software developers in saying that we don’t set out on our path in the same way that others might in law, accountancy, or similar careers. We genuinely love programming. Perhaps it’s built into us — in the same way that great teachers are born, maybe good software developers are wired a certain way?
Anyway. Given this Christmas will be like no other — we’re in COVID lockdown for the duration — I thought it might be fun to pick a programming project to tinker with — a distraction of sorts from the endless stream of Hallmark Christmas movies.
The Game of Kings
I’ve always wanted to write a Chess engine, but never quite got around to it. Since before computers existed, people have written chess engines — Alan Turing famously designed one on paper and ran it on paper before the first machines were constructed at Manchester that might run such a program.
I’ve written half a chess program several times in the past — each time falling down a variety of rabbit holes while exploring the various data structures needed, and the methods of manipulating them at speed. The wonderful thing about programming a chess engine is how well documented past projects tend to be — from academic research papers through to open source projects such as Robert Hyatt’s “Crafty”.
The existence of so much existing research and development is both a blessing and a curse — because a great part of the interest for me has always been the reinvention of the wheel. While it may sound crazy to re-trace the same path as countless previous developers, there is an academic fascination in the mental exercise of breaking a problem down — of solving each facet of a much larger problem, and seeing the jigsaw pieces slowly connect with one another.
Missing the point
I’m wondering if I might be missing the point in building a chess engine from the ground up. Surely the real fun in teaching a machine to play a game is in playing against your creation? With that in mind, I’ve begun looking at pre-built source code libraries that essentially “solve” a great many of the lower-level concerns in a chess program — such as “given this position on the board, what are the valid moves?”.
The real fun — the inventive bit — is figuring out how to make a dumb machine appear clever. Most turn-based games do this through a recursive combination of search and evaluation. If search becomes a simple task of asking a library function “what moves are available?”, then we only have one thing to solve — evaluation — and it’s the biggest rabbit hole of all.
It comes as no surprise that most of the work around tree data structures stems from game theory — modelling trees of “if this then that” decisions — with various methods of walking up and down the tree to extend hopeful looking branches.
I think perhaps one of the most interesting observations — to me — in recent years has been the emergence of artificial intelligence in the realm of evaluation. After the Deep Mind “Alpha Zero” project destroyed Stockfish in a series of demonstration games, the academic exercise turned not from “how to make a machine think?”, to “how do we work out how the machine came up with the answers?”.
Douglas Adams wrote about this
We’ve been here before — in “The Hitchhikers Guide to the Galaxy”, Deep Thought was created to work out the answer to “Life, the Universe, and Everything”. It famously came up with the answer “42”. The question then became “if 42 is the answer, what is the question?” — which needed a much bigger computer to calculate. It was called “Earth”, and was unfortunately destroyed in the first chapter of the book to make way for an interstellar bypass.
Where to start?
After doing a little research, I’m going to stand on the shoulders of those that came before — borrowing the Python “ Chess” library, and looking at previous papers by the likes of Andreas Stockl — who set out the basic building blocks of a search and evaluation implementation. I’ll probably go back and pick apart Crafty too — it implements just about every well-known trick in pursuit of playing a “human” game.
If have no idea how successful my efforts might prove — obviously nowhere near Alpha Zero and it’s terrifyingly accurate perception of the world around it. That’s not the point though — the point is to have some fun.
Originally published at https://jonbeckett.com on December 24, 2020.