Draw By Repetition

A couple of weeks ago a member of the site known as "Student" pointed out to me that he had a game where the same position was repeated 3 times but it wasn't a forced as a draw. I wasn't surprised by this because there's no code in the site to cater for this situation, but I've known about the shortcoming since the site started but chose to disregard it for the time being. It wasn't through neglect that I'd ignored this, but due to something fundamentally very difficult with the site's current setup.

Consider any given chess position - there are many dfferent combinations of legal moves which can lead to that position. When a player currently makes a move the site stores the coordinates of that move, as well as other things such as the availability of an enpassant capture on the opponent's next move, if the player castled, and so on. Now, if we need to work out if a given move leads to a position that previously occurred then the site needs to look at every move so far and work out what the position was after that move was made, and then compare that with the current position. We'd keep a track of how many times the current position had occurred before and then act appropriately once the move was made.

This is all very complicated and not very efficient.

Now that Student had asked for this feature to be incorporated into the site I could no longer overlook it, but I was not willing to implement the procedure I just described. Something new was needed, something that could match board positions quickly and efficiently.

The solution was to store the entire board position on the same database record for the move that created it. this might strike you as being a bit obvious, and I had pondered this for a long while but was put off because of the size of the data structure needed to store a chess board. Multiplied by half a million moves this would be an enormous amount of data. I managed to use a clever solution to this that I read about somewhere 6 months ago when I was learning about chess AIs. If we store an encrypted, compressed version of the board then the volume of data can be dramatically reduced. I say encrypted because then it can be made smaller, and for reasons I'll explain later we don't need to worry about decrypting it.

To encrypt a board position I first create a series of binary 64 character strings, with one string for white pawns, one for black pawns, white knights, black knights, and so on. When building one of these strings, I examine every square and if there is a piece I'm interested in on the nth square then the nth character in the string is set to 1, otherwise it is set to 0. In all we end up with 12 strings, which are then concatenated to make one big 768 byte string. Now for the clever part - I use the encryption functions MD5 and SHA1 to provide two encrypted versions of this string, 32 and 40 bytes long resectively. These functions are non-reversible, but the same input string will always give the same output string. The chances of two different input strings giving the same output are extremely low. In fact, you are more likely to win the lottery every week for the rest of your life than you are to randomly find two input strings with the same encrypted output on both the MD5 AND SHA1 encryptions.

So, when a move is made we store the encrypted board position, and now we can look at all other move records in the game and see which ones had the same encryption values. Same values = same position. That's why we don't need to be able to reverse the encryption because we only ever compare the encrypted positions, and there's no need to have to extrapolate what that position actually was.

However, there was still a big problem. In the moves database there were 450000 moves that never had any encrypted positions stored on them, and for this to work properly they had to. I wrote a script which looked at all of the moves in a game and worked out the encrypted positions and stored them against that move record. The script took an hour and a half to run, but early tests show that it worked!

Now all I need to do is work out the actual chess rules for forcing a draw, but that's not going to be easy - there is a debate raging on the forums as I type!

More to come...