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.
I thought that since chess AI is (or, at least, has been) a hobby of mine, it would be fun and educational to write one in Haskell. And if I'm going to do that, I figure I may as well blog about it!
A few preliminary matters before I dive into the code. First, I make no promises as to how often I will add to this blog. A chess AI is a long project, and I don't currently have a ton of time to devote to it. Second, I intend to start very simply, and inefficiently, with data structures that I know can be improved on. Part of the fun will be refactoring it later. Finally, I fully admit to being a novice Haskeller. I've been studying it for a year or so now, but still struggle with things I should have mastered long ago. Suggestions are highly desirable.
Ok, let's do this! First, a few definitions:
type Board = Array Int Piece
data Piece = Piece Color PieceType
data Color = White | Black
data PieceType = Pawn | Knight | Bishop | Rook | Queen | King
We represent a board as a simple array, indexed by Ints. This gives us O(1) access to any square. This is one area that I guarantee I will come back to, but it's simple enough to start with. Board representation is a HUGE issue with chess AI, and there are many, many things we can try with it. Anyway, we'll use a standard convention, which is to number square A1 (the square closest to white, on his left) as square 0, and H8 (on black's left) as 63. That is, the board will look like this (leading 0's added for spacing only):
56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
08 09 10 11 12 13 14 15
00 01 02 03 04 05 06 07
Now a few useful little things:
emptyBoard :: Board
emptyBoard = array (0,63) 
piece :: Char -> Piece
piece c = Piece color pType
where color = if (isUpper c) then White else Black
pType = case (toUpper c) of
'P' -> Pawn
'N' -> Knight
'B' -> Bishop
'R' -> Rook
'Q' -> Queen
'K' -> King
addToBoard :: Piece -> Int -> Board -> Board
addToBoard piece loc board = board // [(loc, piece)]
An empty board is trivially defined as an integer within the proper range, and with no associations. I'll note here that I've never really dealt with arrays in haskell, so this will be a learning process. I already like the fact that creating an empty array is so intuitive. The piece function is a simple constructor for Piece. It follows a typical chess convention for denoting pieces: uppercase means white, lowercase means black. More on chess notation in a moment. addToBoard adds a piece to the board. Again, it's very simple and elegant-feeling.
Now comes the fun part for this entry:
loadFEN :: String -> Board
loadFEN = loadFEN' 56 emptyBoard
loadFEN' :: Int -> Board -> String -> Board
loadFEN' _ b (' ':xs) = b
loadFEN' _ b "" = b
loadFEN' n b ('/':xs) = loadFEN' (n-16) b xs
loadFEN' n b (x:xs) | x `elem` ['1'..'9'] = loadFEN' (n + (digitToInt x)) b xs
loadFEN' n b (x:xs) = loadFEN' (n+1) b' xs
where b' = addBoard (piece x) n b
Chess has this awful thing about notation. There are a few different ones (particularly for move representation), and they tend to be pretty awful. This function is to convert a string, in a notation called FEN, to an instance of our board data structure. a description of FEN can be found here . Suffice it to say, this is a tedious process to do in any language. In fact, the above function is very elegant compared to many languages. Essentially, we're simply looping through the string, while keeping a reference to the next square on the board that we're going to put a piece on. Since FEN starts with the square on black's right, we start on square 56 (see above diagram). We'll assume for now that the FEN is well-formed.
If you notice from the Wikipedia article, there are several fields to FEN notation. For now, we'll just deal with the first, and longest field, which tells where the pieces are. We'll come back to the other fields later. Thus, if the first character of the string is a space, or if the string is empty, then we're done, and we can simply return the board. If it's a slash, we've reached the end of a row, and we need to move the board reference to the beginning of the next row, then process the rest of the string. If the first character is a digit, it indicates some empty squares, so we'll simply adjust the board reference again. Finally, the only option left, is that we're looking at an actual piece, in which case we need to construct the piece, add it to the board, and process the rest of the string.
I think that's enough for this entry. Next time: move generation!