Revisiting board-building in chess

Submitted by chessguy on Sat, 08/18/2007 - 12:42pm.

So, in my last blog, we looked at the beginnings of a chess engine. That was nearly 2 months ago. I've been kicking around some possibilities for the last few months, trying to come up with a somewhat elegant solution. Ultimately, I've wound up completely refactoring what I started with. I'll be posting more on that here within the next few weeks, but I'm really excited by how one piece came out, so I'd like to show that part at least.

Last time, I mentioned FEN notation for the state of a chess game. Let's look at that in a bit more detail. Here's the FEN notation for the start of a game:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

You can see, there are 6 space-separated fields in this string. What I want to write is this function:

loadFEN :: String -> GameState

...which constructs the state of the game from the FEN. Now, this is notoriously tedious in most languages, but the solution in haskell looks quite elegant to me.

So, let's see. Each field in the FEN is going to tell us something about how to construct the GameState. The first field tells us where the pieces are, the second tells us whose turn it is, the third deals with castling statuses, etc. So we can start with an empty state, and apply multiple functions to it, based on the fields, to build up a new state. That sounds like a fold pattern to me!

However, this seems to be a bit tricky at first. We'll want to apply a different function for each field. That is, the first function will look at that first field and build up the actual squares on the board with pieces. The second function will parse the indicator of whose turn it is, and make that change to the state, etc. So let's start by zipping these functions up with the fields they correspond with:

loadFEN fen = foldl apply emptyGameState (zip funcs fields)
    where fields = words fen
          funcs = [parseBoard, parseCastleStatus]

Here, I've just listed the functions for the first 2 fields, to give us an idea. The only mystery that's left is this apply function. Let's look at its type:

apply :: GameState -> (String -> GameState -> GameState, String) -> GameState

That is, it takes a current state, and a pair, consisting of a function and a field to apply it to, and a field, and returns a new state. Well, that's not so bad:

apply state (function, field) = function field state

Running this through the @pl formatter on lambdabot in #haskell gives us an ugly mess:

apply = (`ap` snd) . flip (flip . fst)

Hmm, this is interesting though, look at the flipping going on. What if we took the input in a different order? Suppose we wrote this:

apply (function, field) state = function field state

Running this through @pl gives the very elegant:

apply = ap fst snd

Thus, the final code winds up being:

loadFEN :: String -> GameState
loadFEN fen = foldl apply emptyGameState (zip funcs fields)
    where fields = words fen
          apply = flip (ap fst snd)
          funcs = [parseBoard, parseCastleStatus]

Very nifty! Now all the real work gets moved off to smaller functions, which just have to worry about the particular field they're designed to work with. Not only that, but if I only want to deal with the first few fields for now, they're the only ones I have to parse, and I'll still wind up with a valid GameState.