Chess in F#

Recently I decided to implement a chess engine as a way to explore building a rules engine in F#

GitHub link: https://github.com/simon-reynolds/FsChess

F# was my choice of language as it has a number of advantages. For instance, defining the pieces is a lot simpler thanks to Discriminated Unions.

type Colour = | White | Black

type Rank =
    | Pawn
    | Rook
    | Knight
    | Bishop
    | Queen
    | King

type Piece = { Player : Colour; Rank : Rank }

Sometimes it can be a struggle to figure out how to conceptualise a real world object in a program. My initial attempt to define the board was as a two-dimensional array, mirroring it's real life structure.

But this lead to an issue trying to map the array indices to the expected rank-and-file notation. For example, the bottom left square of a chess board is A,1. There's an extra conceptual overhead having to continuously translate the array index [0,0] back and forth to the expected A,1.

Instead we can define Row and Column types and simply represent a Square as a tuple of those...

type Column = | A | B | C | D | E | F | G | H
type Row = | One | Two | Three | Four | Five | Six | Seven | Eight

type Square = (Column * Row)

This means that instead of mucking about with array indexes we can easily define a Board as a Map type listing the squares of the board and the Pieces that may occupy them

type Board = Map<Square, Piece option>

Suddenly it becomes a lot easier to query the board to see what piece may be on a particular square. We don't have to map indexes, the Square is constrained by the values of Column and Row. This means that it cannot contain illegal values, so an IndexOutOfRangeException is impossible.

We can use another strength of F#, pattern matching, to query the board in a safe manner and wave goodbye to any NullReferenceException as well.

let square = (A, One)
let maybePiece = board.[square]

let message =
    match maybePiece with
    | None -> "No piece here"
    | Some piece -> sprintf "There's a %A %A here" piece.Player piece.Rank

At the start of a game the message above would be

There's a White Rook here

Movement Rules

The next step is to define the rules that describe how pieces can move. If you've never played chess the movement rules are:

Pawns can move forward one square only, except they must move forward diagonally to capture. On their first move they can move two squares. A pawn has two special moves, promotion and en passant that will be described in another blog post when I implement them.

A Rook can forward in a straight line any number of open spaces. It is involved in a move the King can make called "castling".

A Knight can move in an L shape, two squares horizontally and one vertically, or one horizontally and two vertically. It is the only piece that can jump over other pieces that block its way.

A Bishop can move in a diagonal line in any direction for any number of open spaces.

A Queen combines the movement rules for a Rook and Bishop, moving any number of open squares in a straight or diagonal line.

The King can move one square in any direction, except during the castling move that will be described along with the special moves for a pawn.

Now, we need to translate all that into code...

Movement Rules in Code

When we specify a move the first thing we have to do is check if the move is valid.

There are a number of reasons why a move may not be valid and we need a way to represent that. F# 4.1 introduced the Result<'T,'TError> type which will do perfectly.

A Result will either be an Ok of 'T or an Error of 'TError, we can use this to chain together results in Railway Oriented Programming. An excellent introduction to the concept is available on Scott Wlaschin's amazing site F# for Fun and Profit

Rather than repeat all the code, the implementation can be found on the GitHub repo for this project, https://github.com/simon-reynolds/FsChess

We can use a custom ResultBuilder so that we can check multiple criteria at once and return early on the first failure. This allows us to chain together calls so that the end result for the validateMove function is as simple as

let validateMove (gameState : GameState) (move : ProposedMove) =

        result {
            return!
                // Check we have a piece
                validatePieceSelected gameState.Board move
                // Check the piece is our own
                >>= validatePieceIsGood gameState.CurrentPlayer
                // Check we're not trying to capture one of our pieces
                >>= validateNoFriendlyFire gameState.Board gameState.CurrentPlayer
                // Check the piece is allowed move to the square
                >>= validateMoveForPiece gameState.Board gameState.CurrentPlayer
                // Check nothing is blocking it's path
                >>= validateNoCollision gameState.Board
                // If we've gotten this far then the move is valid, mark it as such
                >>= markMoveAsValidated gameState.Board
        }

Still to do...

Any good chess engine will support the full range of moves, currently I still have to decide on how I'm going to implement promotion, en passant and castling.

Another longer-term goal in this project is to provide an AI to play against and various front-ends that can be used, everything from console to web and phone apps.

Expect follow up posts on them soon.