# Chess in F#

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

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 `Piece`s 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.