Chess programming: a personal history


My first experience with computer chess programming dates back to the late 1990s (around 1996 or 1997 or so). Over summer holidays I wrote a chess playing program, supposedly in Turbo Pascal, but most of the code was actually written in assembly. With hindsight, probably not the best thing to do, since I'm not sure now that I did a better job back then than the compiler would have done (I might have though).

The program was able to reach a depth of about 5-6 ply in a reasonable amount of time on my 66MHz 486 computer back in the day, but it didn't do any quiescence search and as can be imagined it played quite horribly. I think I understood the importance of transposition tables, but didn't really understand how to implement them properly, so I don't think the program ever used them. Of course, being a real-mode DOS application meant it couldn't have big tables anyway.

The program used an 8x8 (64) byte array to represent the board and registered everything it needed to know about castling rights and en-passant captures in the board array itself. This scheme was based on the scheme in the book Computerschaak by Jaap van den Herik, my main source of information at the time.


Time passed and it become 2003. Computer-wise my world had changed: I'd just bought a new computer (actually, the third since our old 486), a 64 bit AMD Athlon, I now used C as my main programming language of choice and I'd said farewell to the world of DOS and Windows and had switched over completely to Linux/UNIX. Naturally, there was absolutely no way that my old chess program was going to make that kind of transition.

What got me interested in computer chess again was the 64 bit nature of the machine: 64 bits in a machine word and 64 squares on a chessboard. Of course, people had been thinking about bitboards for decades, but I'd like to claim that I reinvented them on my own. It didn't take me long to learn about the work others had done with them, but by then I'd already decided how I wanted to write my code and decided to mostly stick with my own ideas.

The program, called Isildur, used a hybrid approach: it had bitboards, but it also had the 64 bit byte array that my first chess program had used (I obviously wasn't comfortable enough with bitboards to get rid of it completely). Move generation was mainly done by bitboards, although in a much more clumsy way that it needed to be.

Around the same time, I became interested in Chinese chess, and I converted Isildur to play this game too. Due to some clever encapsulation and abstractions, I was able to leave most of the engine untouched: only the move generation and evaluation functions were changed. Interestingly enough, despite the fact that a Chinese chess board does not fit in a 64 bit computer word (it needs at least 90 bits), this version made much better use of bitboards than the original chess version did. I finally did manage to get the transposition tables working, although my replacement scheme is rather unfortunate and quiescence search was still mostly something other people did.


Then it became 2009. Again, my situation had changed slightly: no longer a student but a postdoc on a temporary position far from home, I was looking for something to do when I was at home to take my mind of research (it pays to keep your mind fresh) and my thoughts kept turning back to computer chess. The fact that I was travelling around a lot meant that I no longer had a desktop computer at home and my main machine for the past year or so had been my MacBook - easily as powerful as my once new and nifty 64 bit AMD machine was and still running a UNIX-like operating system, and still 64 bit of course.

So I sat down one evening and dug out the source code to my 2003 chess program, which I'd brought with me on an external hard drive. It compiled and ran fine, but a quick look at the code revealed that there were many things I would do differently now. So I created a new directory, fired up vim and started working on a new chess program, tentitatively called Jazz. This time, however, I decided to prepare myself a little and reread some of the online papers and references about bitboard techniques.

There were a few nifty things from the 2003 program that I liked to keep. One of these had to do with the move generator, which could accept two bitboard masks as input: a source mask and a destination mask. An extremely simple idea that makes it trivial to generate only a subset of all possible moves in the position (captures or non-captures are obvious, but there are more examples). Although I hadn't actually used this idea much in the original program, I wanted to keep it in the new program.

The 1997 and 2003 programs used essentially the same encoding for moves, which was rather compact and contained everything one needed to know to reverse the move, but which was also slightly cumbersome. After thinking about it a little, I decided to do things differently in my new program. Rather than make the move encoding as compact as possible, I added extra information there to eliminate some special case code that I had needed before to handle promotions, captures, castling and en-passant captures. This meant it was a bit more complicated to reverse a move, but with all the different bitboards I now had to keep track of (the regular ones as well as the rotated occupancy bitboards) that was always going to be the case, so I decided to take the easy way out: I store the state of the board after each move in a list. Making a move is now slighly slower becouse of this because I need to make a copy of the board when making a move, but reversing a move is now trivial: I simply decrease the reference for the current position by one array element. The reduced complexity here makes up for the extra time I have to spend when making a move - as long as available cache space is not a limiting factor.


Time passes, and it's become 2011. Not much has changed since 2009, in terms of living conditions and computer hardware. I decided to try my hand at writing a general program for playing chess-like games, tentatively called Sjaak (which sounds similar to schaak, chaturanga, shatranj, shogi and xiangqi, which is appropriate for a chess variant program, even if the only variants in that list it plays are normal chess and shatranj).

The main motivation was to write a program that could play Spartan Chess, following a challenge by H. G. Müller.

Sjaak is not a derivative of Jazz in the sense that I started with Jazz and modified it to get Sjaak: I rewrote the board structure, move generation, search and evaluation from scratch, but the design is deliberately very similar to Jazz. I changed a couple of things either because they don't work so well for a variant engine, or because they were simply too cumbersome. The two programs are, however, similar enough that I can copy code from one to the other with little or no change. Sjaak's xboard interface code is derived from Jazz, as are the transposition table and time-managelement code. The major difference is that the board structure is simply too large and cumbersome to copy at every move, so I reverse the move instead.