Introducing libagchess

As CBase Chess goes through some updates, I wanted to provide the community with something that might be of use – the code for the C++ backend which powers CBase Chess!  It is on Sourceforge available here.  I’ve put the project in alpha stage simply because the documentation is lacking.  However, if you’re interested in seeing what I’ve come up with, the code is free for you to browse around and is available for your own use under the GNU General Public License v3.  There are numerous comments in the code, but I will try and give a good overview of what libagchess is all about.

The low-level stuff

libagchess is a C++ bitboard-based library meant for use with chess databases (as opposed to chess engines).  There are 5 “primitive” types used extensively in the library:

• Color – for indicating the side to move and color of a piece.
• Piece – King, Queen, Rook, Bishop, Knight, Pawn, or none – used when you don’t care what color the piece is
• ColoredPiece – has information for both piece and color.
• Square – one always wants to know what pieces are on what square, and what squares are valid targets to move to, etc.
• Bitboard – a typedef for an unsigned 64-bit integral value.  The merits of using a bitboard as the basis for chess programming can be read here.

The other classes in libagchess use these “primitives” quite extensively.  A bitboard in itself has no meaning without context – is it a bitboard of squares attacked by black pieces?  Maybe it’s an occupancy bitboard for white pawns?  There are numerous uses for bitboards, though the one that really stands out is to indicate occupancy.  Occupancy bitboards indicate which squares are occupied by which pieces.  The BasicBoard class wraps occupancy bitboards for each piece of each color, and also provides a means of accessing which ColoredPiece is at a given Square.  A BasicBoard provides no state-dependent context, simply the arrangement of the pieces on the board (think about the information you would get if you walked up to a chess game and just looked at the board – you wouldn’t necessarily know whose move it was, or who had castling rights, or if there was an en-passant square).

Chess Position – because you have to represent game state somehow!

The state-aware object is a Position object.  The Position object encapsulates the data about side to move, castling rights, en passant square, piece locations on the board, and even half-move clock (for 50-move rule).  Position itself is an abstract base class that provides the basic accessors to the general information it holds.  There are two concrete subclasses of Position: SimplePosition and EditablePosition.  EditablePositions allow one to directly manipulate the position state, while SimplePosition (and its subclasses) only allow manipulation using Move objects via make (to make a move) and unmake (to undo a move).

The SimplePosition was meant to be a base class which provided the make and unmake interface, but did not enforce any chess rules, thus one could move any piece to any square and not worry about the legality of such a move.  The SimplePosition class is not actually finished because it’s usefulness in a chess database program is quite limited.  The class which actually knows and enforces the standard chess rules is StandardPosition.  The StandardPosition can only be manipulated with make and unmake and throws an exception if the Move is illegal.  The StandardPosition is meant to always stay in a consistent, legal chess state.

The EditablePosition provides the methods necessary to set up a position.  It doesn’t know any rules, but like it’s base class, keeps track of state information such as en-passant square, castling, etc.  When the EditablePosition is ready to be used, the StandardPosition can set its state to that of the EditablePosition using the member function StandardPosition.copy(EditablePosition).  This will throw an exception if the EditablePosition is not a legal chess position.

Chess Game – a collection of Positions

Wow, that was a mouthful.  Ok, so that’s the fundamental material for representing a single chess position.  What about playing through a whole game?  In libagchess, a chess game is viewed as two parts – the header information about the game, and the moves it makes, and so the classes are GameHeader and GameTree.  A StandardChessGame inherits from both of these objects and provides an interface for constructing and reviewing a chess game.

The GameHeader is fairly simple, and merely provides access to information on who the players are, when the game was played, the name of the tournament, etc.

The GameTree can be abstractly thought of as a tree of StandardPosition objects (Really should be Position objects, but I was only interested in the concrete case of having StandardPosition).  It has a root position, and child positions.  Instead of containing a StandardPosition at every node, which would be prohibitively expensive, it contains the information to reach a child position compressed in a Move.  A GameTree is most easily thought of as a container object for positions – thus an iterator class is provided.

The iterator allows for insertion of a Move into the tree, and dereferences to a StandardPosition.  I thought it was most logical to use iterators to access the moves and positions from a GameTree, so hopefully anybody reading this will find it easy to use.  I think I will make it a priority to document this class more carefully and uploaded it to Sourceforge soon, since it’s the key method of playing through and creating chess games.

Database – because sometimes you need a collection of collections of Positions, aka a collection of Games

And finally we get to the database.  libagchess was designed as a database for reading PGN files.  The PGNDatabase is actually rather simple – tell it to load a PGN database and it does a quick parse of the file to locate where each game starts and ends.  It knows how many games are in a database, and will return a StandardChessGame object using database.getGame(int index), assuming that index is less than the number of games in the database.  When a game is loaded, it is parsed and placed entirely into memory ready to review.  A StandardChessGame loaded from a PGNDatabase is guaranteed to have no illegal moves, as an exception is thrown if the database encounters any illegal moves when loading the game.  To access only the header information without loading the rest of the game, use database.headers(int index).

Final words

This post contains a lot more information than I thought it would when I first started writing it.  Hopefully it provides a small overview as to how the classes in libagchess were meant to be used (or at least how they’re used by me).  There is also a class for filtering games from a database, DatabaseFilter, which uses subclasses of SearchMask to locate games in a database that match the SearchMask.  I’m not 100% sure that the DatabaseFilter is how I want to go about searching databases, but I included it with the library since somebody might find it useful.

So It’s Been Awhile…

I know it’s been a really long time since I’ve updated this blog, but it turns out it gets a few hits every now and then.  I started graduate school in the fall and found very little time to do any coding, which was quite unfortunate.  However, I did start working on a few new things and have some good ideas for improving CBase Chess.

First of all, I’ve decided to try and make my board UI code more flexible.  As it stands in CBase Chess, the board allows replay of games but not entering moves.  The original code actually supports user interaction, but for the purposes of reviewing games, the property allowing user interaction was set to not accept touches on the iPhone.  I didn’t like the amount of work it took to use my board, and I decided it was too coupled with the backend code; therefore, I decided to start working on an open-source implementation of a graphical board interface which will hopefully prove useful for both me and anybody else interested in programming chess for the iPhone / iPod touch.  I will post code up on sourceforge sometime before school starts back up in January.

Secondly, I’m working on a rewrite of the internals of how chess positions and games are stored in memory in order to have more decoupled code.  Furthermore, the code is being developed to allow generic searching of games, so that CBase can have a more in-depth search feature than just by player.

Finally, I’m looking at using the open-source ZipArchive to unzip new PGN files from The Week In Chess (TWIC) and add them to the list of databases in CBase.

Hopefully I will have plenty of time to work on app development during our month-long winter break, and would love to be able to submit an updated version of CBase by mid-January.

On Writing Reusable Code

Taking college courses in computer science never really prepare you for the world of writing reusable code.  In the course of developing CBase Chess, I scrapped my internal board representation code 3 times.  I rewrote my UI board twice.  And yet, when it comes time to start developing a notation app, I realized that my code still isn’t quite flexible enough.

Once again I’m rewriting my code.  I’m doing my best to follow the Model-View-Controller (MVC) design pattern, so there’s a separation between the actual model and the way it’s displayed.  So for now I’m working on a UI board that doesn’t know any of the rules of chess (not even castling or en-passant) – it simply asks its delegate if moving from a square to another square is legal, and makes the move if it’s allowed by the delegate.  My intention is to subclass this class so that moves like castling and en-passant will be made without any more information from the view’s delegate (currently the delegate would have to tell the view to clear the captured piece on an en passant capture, or to move the rook itself during castling).  From there it wouldn’t be a far stretch to add logic into the subclass to enforce all the rules of chess, setting itself as its own delegate and keeping all the logic associate with the rules of chess within itself.

While this sounds like much more work, it will work out better in the long run.  I already have a Position class which knows the rules of chess, so once the board view is finished it will be relatively easy to integrate the position class with the view.  Furthermore, since I may release the board view as open-source, it would simply make more sense that one can add chess rules to a subclass, since another developer may come along and decide to use the class for suicide chess or some other variant.

I think the most important lesson I’ve learned through all this is that documentation is important.  I put off documenting a lot of code because I thought it was good enough to use, that it was solid and would not need to be changed later, and that nobody else would use it.  After just a very short time of not working on a piece of code, I have to go back and try to figure out exactly what I was doing when I was writing it.  It’s not terribly hard, of course, since I wrote it, so I can understand it once I remember the mindset I was in when I wrote it.  However, this time around I’m commenting everything so I’ll know exactly what to do if I ever want to change my code in the future (which, of course, won’t happen since it’s solid, won’t need to be changed later, and nobody else will ever use it 🙂 ).

CBase Chess 1.0 Available on the App Store!

CBase Chess 1.0 has been approved for the App Store and is available here.

I’m also in the process of making a separate help page, but some answers to quick questions about using CBase Chess are here.

CBase Chess 1.0 Submitted!

I finally submitted my first app!  Apple has an unbelievable number of certificates you have to obtain to compile, run, and then submit your application.  It took me almost 2 hours from the start of my submission process to the end to get everything down.  Anyway, it’s waiting for review, and it’s my understanding that most applications are approved within a week, so let’s hope the same goes for mine!

CBase Chess 1.0

CBase Chess is a free PGN database viewer. Cbase Chess supports PGN standards whichs makes bringing your databases from your chess software at home to your iPhone or iPod touch easy!

Features:

• *Games with variations! Supports RAV (Recursive Annotation Variations) for as many variations as your game holds.
• *Games with commentary annotations.
• *Opens PGN files from the web! Registers as a PGN reader so you can open your files from a website, or from apps which support document forwarding like Dropbox!
• *iTunes document support. Add new databases via iTunes.
• *Player search.

I definitely plan on adding more features, including improved views for the gametext/annotations, but in the mean time I felt that my product was ready to ship a 1.0 and get user feedback that I can use to guide the development process.

A Brief Update

I know it’s been forever since I’ve updated, so I just wanted to make a short note of my progress.  I’ve been out of town a lot in the last few weeks and have found it very difficult to make time to work on my project.  That being said, I’m about to have 2 weeks of nearly uninterrupted work, so my goal is to have something submitted to the app store no later than early August.

There are three critical things that I need to get done before I submit:

1. A database program is pointless without a search.  I have an extremely rudimentary search working right now (can only search for white players by exact name).  I feel that this should be expanded to include black players and give the option of searching for games between two players, and whether or not to ignore colors (so that a searched player may play either color).  Also, filtering by result would be nice.  Without this basic functionality, it becomes too difficult to work with a larger database.
2. Annotation support.  I want this database program to be more complete than other databases.  For this, one would of course expect annotation support.  I’m still searching for the best way to display annotations, as I’m not terribly keen on the idea of completely interrupting the UI by using popups for annotations.  I would also like to support NAG (Numeric Annotation Glyphs) but this support will become a priority in the update following the initial release.
3. Improved UI.  This is my first iPhone app and I want it done right.  I want to make full use of the iPhone user interface elements.  This also means making the most of the highly limited screen space on the device.  Currently there’s not enough space to display all the information I’d like to while viewing a game, so I’m looking at implementing a full-screen mode to gather more screen space.

This is my first experience developing any software project larger than those required for basic CS classes, so I’m running into challenges that I wasn’t even aware existed.  I’m still making progress, though, and I’m very excited about releasing my app soon.

Why Can’t We Have Variations???

A quick search through the App Store reveals over 300 hits for “chess.”  Granted, not all of them are actually full-fledged chess apps, but nonetheless there are a great deal of them that are.  Some are tactics, many are engines, some are two-player, even a few of them are database apps exclusively.  The biggest complaint I see on forums is that many of these Apps don’t allow you an easy way to get games on or off of the device.  What’s more, you can only rough the main lines of any games that your device may choose to load.

So that begs the question: why can’t we have variations on the iPhone?  Answer: we can.

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!

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!

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,?