Sometimes it feels like every project idea I have has already been done. I have a cool idea for a program, and then when I google it, not only has it already been made, there’s already a web app for it. In my internship with with web development stuff, I learned that web development has come a long way from 90s era static html, or even simple php generated code like you might find on a website like this. You need to know half a dozen languages and ten frameworks to work on these modern apps with full native functionality that just happen to be contained in a browser tab. Well, that is something I should try to learn better, but that’s an issue for a different day.

However just because something has already been done, isn’t a good reason not to try implementing it myself anyway. Hello world has been implemented in thousands of languages, and yet millions of beginner programmers across the world implement it again over and over. It’s a good learning exercise, and maybe I’ll get lucky and come up with an improvement that nobody has thought of. So I’ve decided to try my own spin on a project that has not only been implemented before, it’s been implemented over and over again and is perhaps one of the most famous types of software in the world - a chess engine.

I recently overheard some people discussing playing chess, and that reminded me of how bad I am at chess. One approach would be to try to get better at chess, but that’s a lot of work for limited payoff - I’m likely never going to be a chess grandmaster, and it’s always frustrating to practice something you’re terrible at (don’t get me wrong - I’m well aware of the mental benefits of things like chess or playing instruments, and I probably should be doing more for my brain, considering how much I train my body).

But I had the thought that in less time than it would take me to significantly improve my chess ability, I could sipmly program a chess bot that is better than me. Not a very high standard to aim for, with systems like Deep Blue (allegedly) beating grandmasters as far back as 20 years ago already, but Rome wasn’t built in a day. I figured that with that low of a standard and with modern hardware performance on my side, I wouldn’t have to worry about state of the art efficient algorithms, supercomputing, complicated expert-knowledge-based heuristics, or anything like that. The plan was just to exhaustively tree search the move space for maybe 3 turns ahead, score each move according to the traditional piece values (1, 3, 3, 5, and 9 for pawn, knight, bishop, rook, and queen respectively - as well as some high score penalty for danger to the king), and then let it rip. The ability of a computer program to see every potential piece loss should already be enough to beat me, seeing as I lose so many pieces and games to across the board attacks that I don’t even see coming.

So I hacked together a quick move generator in python, using an 8x8 array to store the board and a whole lot of for-loops and if-checks. As much as I love python, I know that it’s not the most performant language unless you’re using external computational libraries like numpy, but I didn’t think that would become an issue here. Boy was I wrong. Exploring a tree is of course exponential complexity with regard to the depth, which wouldn’t be too bad in a binary tree. But the very first half-move of a chess game already has 20 legal moves, and the average branching factor of a game is somewhere around 30 - this means that my indended three moves (six half-moves) even in the start case explode to around 20^6 or about 10^8 nodes! For my python hack, this wound up being a runtime of around 22 hours - not really acceptable runtime for the decision process in each turn. And that’s at the beginning of the game with most of the powerful pieces still trapped - runtime should be around 10 times that mid-game assuming the average branching factor.

Since I’m taking a high performance computing class currently, I realized that most of these computations are completely independent of each other, so they should lend themselves to parallelization. As my laptop has intel graphics and my old desktop computer has an AMD video card, CUDA was right out the window, and I decided I should look into learning OpenCL. Caught in my ways (as a lazy duck-typing Python user) as I am, I googled if there was any way to integrate that into Python, and found the wonderful OpenCL package by Andreas Klöckner. As it turns out, OpenCL is pretty easy to learn, since it shares its syntax with C, the first language I learned that I can still remember. Well, remember in theory, in practice I forget so many semicolons, it’s frustrating. After re-writing it in OpenCL, even just running on my CPU, the same three move deep exhaustive search takes about 30 seconds instead of 22 hours - that’s a good start. I had always heard Python was a slow language, but I never knew how slow. It’s not quite as simple as that, but I think this is enough writing for one post. I’ll expand on it more in the future - I’m pretty sure this chess engine will be a many part series.