Lazy Loading for PGN Database Views

Ok, so it’s not much, but I figured I could post a screenshot for a database program I’m working on:

One of the issues with developing for a mobile device is memory – it’s a precious resource, even if your device doesn’t allow for true multitasking.  Cocoa Touch (the iPhone framework) likes to use lazy loading of data to reduce memory usage.

“What is lazy loading?”, you might ask.  Lazy loading only loads data into memory just before it is needed, as opposed to having it stored in memory up front for quick access.  Think about a UITableView (you know, all the lists that show up on the iPhone, like in Contacts or a list of songs in iPod).  You can only have maybe 10 UITableViewCell (each individual item!) items displayed at any given time.  So for a user with 1000 songs in their library, it doesn’t matter what the other 990 are – the phone only has to load the data for the 10 cells it’s going to show.  Basically, this is a really cheap and effective way of giving the appearance of all the data being present up front, but it’s actually not loaded into memory until the UI needs to display it somehow on screen.

OK, so what does that have to do with PGN Databases?  Let’s say we want to load a database full of games from our favorite Sicilian variation – the Bg5 Najdorf Defense!  This used to be a popular line, and so there are a lot of games – the database I downloaded (from ChessMentor) has over 12,000 games.  I want to be able to scroll through my database and pick an arbitrary game, but my iPhone is going to kill my app if I try to make a UITableView with 12,000 items all loaded into memory ahead of time, so I need to be able to process the PGN file and know how many games there are and the header information so I can display something relevant about my game in a cell.

Yes, the cells are ugly right now – it’s just a prototype.  Once I get around to it I’ll post some different UITableViewCell styles and see if anybody has an opinion.  Right now I just wanted the information available for debugging.  Anyway, so I have to keep track of the location of each individual game in the PGN file so that my table can query for header information at the indices it’s displaying.  My current implementation loads the byte offset for each game into a vector when the database is opened.  Then it generates the header information on the fly when the table queries it for the information by seeking to the offset for the queried game and processing the first few bytes for header information, which is then returned and displayed in the table.

Unfortunately for large databases just initializing the offset vector can take ungodly amounts of time.  To load the SicilianNajdorf6Bg5 database on my iPhone 3GS (running 3.1.2), it took around 70 seconds.  One of the typical things to do for long table view lists is to only load 25 or so entries at a time, which I may try out eventually.

Hopefully this provides just a quick insight into what has to go on to actually develop a PGN reader (besides actually parsing the game data and displaying it!).  These are just sort of my musings and some of the thoughts that had to go in to writing an iPhone app.  I hope the screenshots create some interest in a database app!  I’m not sure if there’s a huge demand for it, but I think there definitely is potential if the app is good enough!

Posted in iPhone | Leave a comment

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!

Posted in Bitboard, iPhone | Leave a comment

Monroi on iPhone

I wish Monroi would make an iPhone app. I can’t imagine it would be very hard. The UI would look nicer, and I’m sure it could be priced well enough to make profit on just the app and not the hardware. Anybody else think $350 for a product that does nothing but chess notation is a bit ridiculous,?

Posted in iPhone | Tagged | 2 Comments