Chess in Haskell
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!