Monday, 23 February 2015

Storing a chess board in memory

Recently I started doing some programming work for ePlusChessBooks , and one of the tasks is parsing chess diagrams in document files, and turning them into something an app can use. Fortunately this kind of work intersects nicely with previous programming I had done in the field of computer chess, so the learning curve is not that steep.
In starting on the problem, I remembered an idea I had a number of years ago concerning the efficient storing of chess boards in memory. By 'chessboard' I mean both the location of each of the pieces, plus the state of the game (eg castling rights, en passant status, 50 move rule). At the time I was thinking of storing only pawn structures and using this information to build a 'chess planning system'. (NB Mark Hummel is currently working on a similar system). Unfortunately the method I was thinking about was actually less efficient than just storing a full board representation, and I let the whole project drop.
In doing some further reading I discovered that there are some quite efficient ways of storing such information. The obvious way is 1 byte per square, plus flags, so around 66 bytes of information. However there is some redundant information in there, as there are only 12 different pieces (each piece + white or black) meaning you can use 4 bits per square (halving the size). An greater refinement is the record the number of empty squares between the pieces (eg 4 bits for a piece followed by empty square count). The advantage of this method is that it uses less memory as more pieces get captured.
Of course this probably has very little practical application in the field of chess programming, as early on I learnt it is often a choice between memory and speed (ie if you want speed, you need to use lots of memory). But if you are interested in this topic, for whatever reason, there is a whole wikipedia page on it!

No comments: