Representing a chessboard in Haskell

user_13507034 0
Viewed 786

I'm trying to implement a function in Haskell that returns a list containing all possible moves for the player who's up. The function's only argument is a String composed of an actual state of the board (in Forsyth-Edwards Notation ) followed by the moving player(b/w).

Notation example : rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w (starting board state)

A move is transmitted as a string of the form [origin]-[destination]. The destination is always a position of the form [column][row], where the lower left square is called a1 and the upper right square is called h8. A move would be for example the move "b3-c4". (no castling/En-passant).

In Java I would use a 2d Array for the Board, but in Haskell I can't find a similar solution (I'm new to functional programming).

What would be a good way/data structure to represent the chess board in?

chess haskell
2 Answers

There are two primary options for storing a board state. The first is a 2D list of Maybe, where a piece would be represented as, e.g. Just $ Piece Black King and a blank square would be represented as Nothing. This optimizes determining if a square is occupied over listing where pieces are (which might be important if you plan to add rendering later):

type Board = Vector (Vector (Maybe Piece))

data Piece = Piece { color :: Color
                   , type  :: PieceType }

The second option is to store a list of pieces and their locations. This implementation is faster to enumerate the locations of all pieces, but slower to check if there is a piece on a particular square:

type Pieces = [Placement]

type Placement = { position :: Position
                 , piece    :: Piece }

data Position = 
    Pos { rank :: Int
        , file :: Int }
    deriving (Show, Eq)

data Piece = 
    Piece { color :: Color
          , ptype :: PieceType }
    deriving Show

EDIT: It's worth noting that with an 8x8 grid and a maximum of 32 pieces on the board, the performance hit either way is going to be minimal unless you're doing a lot of calculations.

user_58862380

Data.Vector, has constant time lookup by index.

A chessboard can be represented as a Vector (Vector (Maybe Piece)). To define Piece, see ADTs

user_65226800
Related