Tag Archives: Chess

Chess Engine Update: Endgame Tablebases

In the background, while tons of work stuff has been happening, I’ve been continuing my mission to write a fully-featured computer chess engine in the C programming language.  My engine is named SpaceDog, in honour of my dog Laika, who is from space.

Work on SpaceDog has been proceeding well, with lots of additions to its evaluation function, convenience features like outputting fully-diagrammed logs of each game you play against it, outputting games in PGN format, etc.  Now I’m diving into adding more substantive features, in this case support for Syzygy endgame tablebases.

Endgames have always been a prominent feature of chess study, and over the centuries millions of players have stared uncomprehendingly at difficult endgame studies, mate-in-3 puzzles, and similar things.  For the improving player, endgame study is interesting but also very challenging, in that there are innumerable situations where a seemingly simple or natural move can lead to disaster, or conversely the failure to find a very specific and unintuitive move can lead to a missed win.

Naturally this is just as much of an issue for computer chess engines as it is for humans.  Many engines over the years have been programmed with specific rules for winning typical endgames like KPvsK (King and pawn versus a lone king) and some of the particularly long-winded and tedious ones like KRvsK (King and Rook versus King) or the dreaded KBNvsK (King, Bishop and Knight vs King — you get it now, abbreviations only from now on!).  Some of these endgames require remembering rules particular to each endgame, or even memorising long strings of winning moves in order to not mess up and give your opponent a stalemate.

Before we go any further, a quick reminder of the basic rules of ending a chess game:

  • Checkmate: opponent’s King is in check (attacked) and unable to escape to safety
  • Stalemate: opponent’s King is not in check, but your opponent has no legal moves, (remember it’s illegal to move into check)
  • Draw: declared when players repeat an identical board position 3 times in a row, OR when 50 moves have elapsed without a pawn move or capture taking place

These rules and the complicated nature of some endgames make things difficult for humans to succeed in their endgame play, and chess engines struggle too, even when looking ahead many more moves.  Let’s see, for example, how SpaceDog copes with the tricky KBNvsK ending:

KBNvsK no TBs 2

Here’s a snippet of SpaceDog’s attempt (before my recent additions) to play KBNvsK (the full PDF record is available here).  I actually stopped the engine after 26 moves as it was clearly making no progress!  If you check the full game log out, you’ll see that SpaceDog manoeuvres bravely, but is unable to work out the correct plan to trap the enemy King, even though it was looking ahead 25 moves at this point.  SpaceDog needed to trap the enemy King against the side or corner of the board to make it easier to deliver checkmate, but couldn’t coordinate its pieces correctly, and so the ending barrelled irretrievably toward a draw by the 50-move rule.

It’s worth saying that SpaceDog, even armed with only its core evaluation function and search, is more than capable of winning many endgames.  But even in those cases, it can make the occasional mistake that can allow a clever opponent to salvage a draw or stalemate, or can be simply inefficient and take longer than it should to mate the opponent.  Let’s take this KPPvsKP ending as an example:

KPPvsKP no TBs 2 This endgame looks simple, but the black King is in the way of White’s protected passed pawn on c4, so getting that pawn to promote and become a Queen requires some finesse.  SpaceDog manages this quite well without any additional help, mating the opponent in 24 moves.  However, with clever play it should be possible to checkmate Black quicker and with a greater material advantage.

And that clever play is what endgame tablebases are all about.  Endgame tablebases in chess came about thanks to Richard Bellman, who in 1965 proposed analysing chess endgames using retrograde analysis — starting from checkmate positions, and working backward from there to find the optimal moves to reach that position.  The end result of this would be a massive database containing every possible configuration of pieces on both sides of an endgame with small numbers of pieces, with complete information on how to reach the best possible ending from that position.  In 1977 computer science legend Ken Thompson used the first endgame tablebase in an engine against a human opponent, and from there chess engine programmers were off to the races.

Today thanks to widely available supercomputer power we have access to tablebases that enumerate all the optimal moves for both players from every possible endgame position containing seven or fewer total pieces.  This is a truly staggering number of positions — 423,836,835,667,331 to be exact!  Yes that’s 423 trillion positions.  There are 512 billion KRBNvsKBN endgames alone!  For every single one of these positions, we know: the game-theoretic value of the position (Win, Lose or Draw, or WDL for short); the distance-to-zero (moves before a pawn move or capture that zeroes out the 50-move drawing rule, or DTZ); and the distance-to-mate (number of moves for the winning side to mate, or DTM).  You can explore any and all of these positions and view the winning moves and various stats about endgames at Syzygy-Tables.info; the front page also has handy links for downloading all the tablebases for yourself.

I should note that of course given the size of these databases, the actual files are very large.  The best available compression algorithm for full WDL and DTZ tables is Syzygy, which is what I’ve added to SpaceDog.  The 3, 4 and 5-piece endgames will take about 1GB of storage, but you’ll need 149GB for the 6-piece endgames, and a staggering 18.4TB for the 7-piece endgames!  To use them most efficiently, make sure the WDL tables are on very fast storage like a solid-state drive (SSD), as these are accessed by engines very frequently to guide the engines toward favourable endgame positions, whereas the DTZ tables are only accessed once the engine actually enters an endgame position and needs to know the best moves.

So, after a weekend of work, SpaceDog can now use the Syzygy endgame tablebases, and thus plays endgames perfectly.  This makes it far better for practicing endgame play, for learning difficult endgame and mating sequences, and for analysing games.  To see how dramatic the change is, let’s go back to that KBNvsK endgame from earlier, where SpaceDog stumbled about uselessly for 26 moves heading for a draw, despite having a massive advantage in material.  Once we add Syzygy tablebases, SpaceDog obliterates its opponent in only 7 moves:

KBNvsK TBs 2

Look at that lovely short move listing!  This time, SpaceDog uses all of its pieces in concert, confining the enemy King to the corner by occupying the short f1-h3 diagonal with its bishop.  Shortly afterward, we end up with an effectively and efficiently checkmated opponent:

KBNvsK TBs mate 2

Even when we revisit endgames that SpaceDog can win easily, the Syzygy tablebases provide significant improvements.  Going back to the KPPvsKP endgame from earlier, SpaceDog checkmates five moves faster:

KPPvsKP TBs 2

SpaceDog not only wins faster, but it ends up with two queens instead of just one!  The opponent doesn’t stand a chance:

KPPvsKP TBs mate 2

Of course these are far from the most complicated endgames available.  SpaceDog can now win endgames that take potentially hundreds of moves, without making a single mistake.  The Syzygy tablebases are built with the 50-move rule in mind, so in some longer endgames you’ll see clever trickery as SpaceDog just manages to make or allow a pawn move or capture before the deadline, to reset the clock and deliver checkmate later on.  Take for example this KBBvsKQ endgame, in which SpaceDog achieves mate in 52 moves:

KBBvsKQ TBs

Here SpaceDog methodically manoeuvres the Queen to neutralise both of White’s bishops, until it captures one of those bishops at the last possible moment (the last half-move of move 50):

KBBvsKQ move 50

That gives SpaceDog the time to finally deliver forced checkmate two moves later:

KBBvsKQ mate

As you might imagine, remembering forced sequences of so many moves and using them with such impeccable timing is impossible even for the top Grandmasters — there are simply too many endgame possibilities to make rote memorisation worth the trouble.  Even if it were worth it, remembering sequences like that over the board under time pressure against live opponents would be a very tall order!

During my testing I found a particularly cruel example of this kind of brutal efficiency in this KNNvsKP endgame, where White delivers a tricky checkmate with two knights after 52 moves:

KNNvsKP TBs

Note that the first move, Na2, immediately immobilises Black’s passed pawn, where it stays frozen until move 50, when White lets it run free.  ‘Yay!’ says Black, ‘I’m making a Queen!  I’m back in this!’

KNNvsKP move 50

Black does make a Queen, as it happens, but it’s ultimately pointless as they get checkmated immediately:

KNNvsKP mate

SpaceDog, that’s just harsh!

Anyway, these are just some fun examples from 5-piece endgames — there’s some amazing endgames in the 6- and 7-piece databases of course, with forced checkmate sequences lasting hundreds of moves, totally bizarre-looking moves that turn out to be the only path to win or draw, and intricate piece play that has done wonders for our understanding of endgames.  I highly recommend taking a look at some cool endgames using an engine, or just browsing them via the web interface linked above — you’re bound to find something fascinating.  Assuming you care about chess, obviously.

So what’s next for SpaceDog?  Well first, my Syzygy tablebase support is only half-finished — endgame play is now perfect, but I have yet to implement searching of the WDL tables during midgame play to guide SpaceDog toward the best possible endgame positions.  That’s a relatively straightforward addition and will take much less time than adding the DTZ support, thankfully!

After that, I’m aiming to beef up SpaceDog’s search, making it more efficient to allow searching to greater depths, and making it much faster by using multi-threading (multiple CPU cores).  At that point, SpaceDog will have all the main features of a modern alpha-beta chess engine, and will make a worthy opponent for its eventual successor: SpaceDogNeuro.

You can download the latest SpaceDog executables for Windows and MacOS (Linux forthcoming, when I remember) at the Github repository, by the way, but bear in mind it’s a messy hobby project, and a major work-in-progress with bugs lurking everywhere!  If I were you I’d wait for version 1.0.  In the meantime, for serious chess analysis, Stockfish is the superior choice (and it’s free and open-source too).

Advertisements
Tagged , ,

(Re-)Learning C Via Computer Chess

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:

Screen Shot 2018-10-14 at 03.23.34As 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!

Tagged , , ,
Advertisements