Chess in F#
Tags: fsharp
Published: 2020-06-16 20:40:51

---
title: Chess in F#
published: true
date: 2019-07-17 20:59:30 UTC
tags: fsharp
canonical_url: https://SimonReynolds.ie/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](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.

<!--kg-card-begin: markdown-->
```fsharp
type Colour = | White | Black

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

type Piece = { Player : Colour; Rank : Rank }
```
<!--kg-card-end: markdown-->

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...

<!--kg-card-begin: markdown-->
```fsharp
type Column = | A | B | C | D | E | F | G | H
type Row = | One | Two | Three | Four | Five | Six | Seven | Eight

type Square = (Column * Row)
```
<!--kg-card-end: markdown-->

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

<!--kg-card-begin: markdown-->
```fsharp
type Board = Map<Square, Piece option>
```
<!--kg-card-end: markdown-->

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.

<!--kg-card-begin: markdown-->
```fsharp
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
```
<!--kg-card-end: markdown-->

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](https://fsharpforfunandprofit.com/rop/)

Rather than repeat all the code, the implementation can be found on the GitHub repo for this project, [https://github.com/simon-reynolds/FsChess](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

<!--kg-card-begin: markdown-->
```fsharp
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
        }
```
<!--kg-card-end: markdown-->
* * *

### 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.