The Importance of Bitboards and Efficiency.

So I’ve been thinking about the generally poor quality/selection of iPhone chess apps on the App Store.  I’ve been thinking about this for years, in fact.  From the moment I got my hands on an iPhone I knew that it would be brilliant for chess!  So much, in fact, that it could probably replace having to bring a laptop to tournaments to look up games and openings and the like.  Except nobody’s developed an application that will let me do that.

I want an app that can function as an electronic notation device.  I want an app that can function as a database, where I can load my own PGNs and have variations and annotations.  I want an app that can call by to my computer at home and analyze with Rybka – I don’t want a weak engine trying to run on the little memory I have on my phone.

Well, I’m sick of waiting.  Time to write something myself instead of waiting for some developer to build another half-assed chess app that’s like all the rest of them.  What I realized, though, is that for any of these apps to be possible, it needs to have a board representation.  Like any good programmer (though I far from consider myself a good programmer), I’m lazy.  I want to reuse code.  That means that the same board representation I’m going to use for my notation application will be used in my database application, and in an engine application if I ever get around to it.

After writing two Objective-C classes for a board representation, I finally realized that I was never going to be happy writing these in Obj-C because my code is just ugly.  It has to call a lot of conditional statements every time you make a move, which is not so bad efficiency-wise for notation, but there would be a huge overhead in trying to search a database.  That’s when I finally broke down and decided I had to learn to use bitboards.

And you know what?  I think it’s made me a better programmer!

The idea of bitboards has been around for a long time (since the 1950’s).  It’s  a simple idea: choose one attribute of the board you want to represent (such as the location of white pawns), and use 64 bits (one for each square) to determine whether or not that attribute is present on your whole chessboard.  This is amazingly cheap when it comes to memory.  64 bits is 8 bytes – at a minimum you need one bitboard for the locations of each of the 6 pieces, and one bitboard for the location of all the white and then all the black pieces, for a total of 8 bitboards.  With 8 bitboards times 8 bytes/bitboard, you only need 64 bytes to represent a position.

What’s even more impressive is that with these bitboards, you can use logical operations (AND, OR, NOT, and XOR) to combine individual bitboards to get new bitboards with other information!  Using bitboards, it’s easy to generate moves and find checks, and – with a little more code – you can even use bitboards to help easily generate Standard Algebraic Notation (SAN) moves.

I’m sure my bitboard class isn’t the most efficient, but it is far easier to work with than anything I could have come up with in Objective-C, so hopefully I’ll be able to get some decent runtimes on my iPhone as I use bitboards with a large number of positions!

Advertisements
This entry was posted in Bitboard, iPhone. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s