In recent months I haven’t had much time to do a lot of programming, what with the demands of my work. One thing I’d been meaning to do, whether it factors into my research directly or not, was to re-acquaint myself with the C programming language. I used it way back in the day, but then as time went on I fell in love with Python, which despite being ridiculously slow in comparison, is extremely fun to use. But the fact remains that it’s very useful to be able to write compact, speedy code from time to time, either for writing simulations for work or for passion projects.
So, I decided to find myself just such a passion project to rediscover the joy of programming in C, and given that I’ve been playing and studying a hell of a lot of chess and shogi in my spare time of late, I decided to learn how to program a fast and relatively powerful chess engine in C. A traditional chess engine uses brute force to search a very large number of possible moves on its turn, evaluating each one in turn until it chooses what it thinks is the best move for the situation. Given how much computing power is available these days, even a half-decent smartphone can now play chess at a level greater than any human, including Grandmaster-level professionals.
In order to do this I followed a great series of videos on YouTube called ‘Programming a Chess Engine in C’, which is 95 videos long (!), but covers a ton of stuff, helping you build a fully-functional chess engine in C which uses the standard techniques in chess programming — alpha-beta search with null-move pruning and some other optimisations. The engine is capable of playing a game of chess via text commands with the user, or by communicating with graphical chess software using the UCI or WinBoard/CECP protocols to let you play a game with mouse control and lovely graphics for the pieces.
After watching all that and feeling my way around C again, I’ve now produced a chess engine of my own, which I’ve named SpaceDog, in honour of my dog who is from space. At the moment it’s basically the same as the VICE engine which comes from the videos above, but has a few small additions in the evaluation function to make it a little stronger (hopefully), as well as a few quality-of-life improvements here and there. It works great, and plays a mean game of chess already — which perhaps isn’t surprising since it searches and evaluates about 3.5 million chess positions per second! In comparison a master-level human player might evaluate perhaps 3 or 4 positions per second.
Here’s a screenshot of SpaceDog playing in text mode:
As you can see, it prints out a nice little text-based board for you (white pieces are capital letters, black pieces are lowercase). Moves are entered in long algebraic notation — so to move white’s queen at the bottom of the board to the square above white’s king, you’d enter d1e2. SpaceDog also prints out its search results and position evaluations on each move, so here you can see at the bottom that it searched nine moves ahead (depth:9) and spent 2.9 seconds evaluating 11.9 million moves before choosing the move e7e4 (taking my pawn with its queen) based on what it thinks of the resulting position and its future prospects.
Every searched position is evaluated quite simply, with a score calculated on the basis of material balance, the position of the pieces, and things like whether there are isolated pawns and other key features. Right now I’m adding some additional evaluation terms that better capture how the relative value of certain pieces, and their ideal placement on the board, changes as you proceed from the opening to the endgame. Hopefully this will make SpaceDog a bit more shrewd at finding checkmate!
The engine can also use opening books — these are files generated by processing millions of opening moves from many hundreds of thousands of professional chess games, choosing a repertoire of openings based on what moves proved to be most successful. This means SpaceDog essentially has a huge file of opening moves already catalogued in the book, with an enormous selection of replies and counter-replies for all the best possible responses from the opponent. These moves then don’t need to be searched, meaning that SpaceDog saves tons of time for searching much deeper in difficult middlegame and endgame positions.
At this point SpaceDog probably plays well enough to beat anyone I know, but would likely still lose to players above Master level. That would probably change at fast time controls — i.e., quick game setups like blitz (5 or 10 minute time limit for each player) or bullet (1 minute each!). At these time controls, humans simply can’t make much use out of our superior long-term strategic planning abilities, so even SpaceDog’s rudimentary but tactically sound play should be tough to beat when us human meat-bags are sweating over the clock and feeling the pressure.
Anyway, it’s been a lot of fun so I plan to keep it going! Next steps are to continue to enhance the evaluation function to better account for things like keeping the king safe and setting up outposts for bishops and knights. I’ll also work on some more technical enhancements like multi-PV search (searching multiple lines of play on multiple CPU cores simultaneously) and adding support for endgame tablebases to allow SpaceDog to achieve perfect endgame play.
Most importantly though, I want to add a mode so SpaceDog can play Crazyhouse and Chessgi, variants of chess in which captured pieces become yours and can be dropped back onto the board as part of your army. This is a feature taken directly from shogi which is a game I also love, so I’m looking forward to implementing these. Eventually I may try to build on that foundation and add a shogi mode as well.
‘What’s the point of all this?’ you’re probably asking at this point — after all, SpaceDog will never be as good as current strongest engine Stockfish, and plenty of other engines play Crazyhouse and lots of other variants besides (such as this version of the mighty Stockfish). There are even innovative neural-network-based engines coming out now like LCZero that are challenging for the throne of toughest computer opponent. But nevertheless writing SpaceDog has been satisfying and fun, and it’s given me another way to learn more about chess and enjoy the game from a different angle. I’d also forgotten how satisfying coding in C can be — the final SpaceDog program takes up only 74KB (!), yet it effortlessly plays chess better than I can.
Anyway, I thought I’d post this up just on the off chance anyone else might get something out of learning a bit about chess programming. I highly recommend the tutorial videos I linked above from Bluefever Software — they’re really easy to follow and provide excellent explanations of the key concepts you’ll need to know to write a chess engine.
Someday I’ll post up the code for SpaceDog too, once I add a few more additional features in!
Dr Eric Silverman 