Fable Reversi

This post is part of the F# Advent Calendar in English 2019.

Reversi (also known as Othello) is a two-player board game with simple rules.

Played on an 8-by-8 board, players (who we’ll call Black and White) take turns placing pieces of their own colour on empty spaces to flip (to their own colour) any opposing pieces which are in a continuous line between the piece being played and another piece of their own colour. Flips don’t cascade (a flipped piece doesn’t flip any others) and any valid move must flip at least one piece. If a player can’t move, their turn is skipped.

The object of the game is to have the most pieces of your colour at the end of the game – either when no more moves can be played or, more usually, the board is full.

In this post I will present an F# implementation of the game logic along with a Fable/Elmish UI and a simple implementation of a computer player.

The source code can be found on GitHub and a live version where you can play against one of the computer players is here. Warning – the "depth 2" computer player is very slow!

Game logic

The building blocks are very simple – discriminated unions for each colour and for the contents of a square on the board:

type Colour =
    | Black
    | White
    member this.opposite =
        match this with
        | Black -> White
        | White -> Black

type Square =
    | Piece of Colour
    | Empty

And a record for the state of the game:

type Board =
    {
        Squares: Square[]
        NextToMove: Colour
        NumBlack: int
        NumWhite: int
    }

Squares is a single-dimensional array because Fable doesn’t translate 2D arrays to JavaScript at present. I chose to store the number of each side’s pieces to avoid counting them repeatedly. Otherwise, this structure stores the minimum information necessary to fully determine the state of a game.

Of course, we’re going to need some higher-level information to build a game. Given a particular Board, we should be able to work out whether the game is either:

• finished (and who won);
• still in play (and which moves are possible); or
• still in play (but no moves are possible but the current player).

type PossibleMove =
    {
        MoveLocation: Location
        Flips: Location list
        Result: Board
    }

type OngoingGame =
    {
        Board: Board
        PossibleMoves: PossibleMove list
    }

type GameResult =
    | Win of Colour
    | Tie

type FinishedGame =
    {
        Board: Board
        Result: GameResult
    }

type GameState =
    | Ongoing of OngoingGame
    | OngoingSkipMove of Board
    | Finished of FinishedGame

I’m not totally happy with the domain types here – I would prefer a GameState to always have a Board accessible in a consistent way, but chose to use types for each of the three possible states so that the type system can help later on – for example, by guaranteeing that a computer player won’t be asked to pick a move when none are available. Suggestions welcome!

I won’t go through all the code which partitions Boards into these three states. Most interesting is the code for checking whether a valid move can be played on a particular square. This captures why I love F# – it closely matches how a human might explain it:

• a move can only be played on an empty square
• a move can potentially flip opponents pieces in any of the possible directions
• a move must flip at least one piece

    let private isPossibleMove board colour location =
        if squareAt board location = Empty then
            let flips = directions |> List.collect (wouldFlip board colour location)
            if flips.IsEmpty then None else Some flips
        else
            None

The wouldFlip function returns the locations of any pieces in a particular direction that would flip. In human terms, this might translate as "find all the consecutive pieces of the opponent’s colour in that direction, but only include them if they are followed by a piece of my own colour":

    let private wouldFlip board colour location direction =
        let mutable location' = location + direction
        let mutable foundEmpty = false
        let mutable foundColour = false

        let flips =
            [ while (isOnBoard location' && not foundEmpty && not foundColour) do
                match squareAt board location' with
                | Empty -> foundEmpty  foundColour  yield location'
                location' 
    match List.tryFind (fun possibleMove -> possibleMove.MoveLocation = location) possibleMoves with
    | Some possibleMove -> model, Cmd.ofMsg (GameAction (PlayMove possibleMove))
    | None -> model, Cmd.none

The logic is clear: if the location that was clicked on is in the current list of possible moves, send a command to play a move at that location. Otherwise, do nothing.

View

The view function renders the UI for a given state, and also takes a dispatch callback which is used to raise messages, for instance as a result of user actions.

Of most interest is rendering the game board. Firstly we define some helpers to define the various potential styles for a piece and a square:

let toPieceIcon colour =
    [ Fa.i
        [ Fa.Size Fa.Fa2x
          Fa.Solid.Circle
          Fa.Props
            [ Style [ Color colour ] ] ]
        [] ]

let toCellProps colour : IHTMLProp list =
    [ Style
        [ TextAlign TextAlignOptions.Center
          VerticalAlign "middle"
          Height "50px"
          Width "50px"
          BackgroundColor colour ] ]

let blackPiece = toPieceIcon "#000000"
let whitePiece = toPieceIcon "#ffffff"
let blackFlipPiece = toPieceIcon "#606060"
let whiteFlipPiece = toPieceIcon "#d0d0d0"

let plainCellProps = toCellProps "#00b000"
let possibleMoveCellProps = toCellProps "#00d000"
let possibleMoveHoverCellProps = toCellProps "#00f000"
let wouldFlipCellProps = toCellProps "#00d000"

The toPieceIcon function uses FontAwesome, which is possibly overkill for drawing a circle in a colour of our choice! The toCellProps function sets various constant options for each square, plus the background colour (which will depend on context).

Showing a single square is now pretty simple. Note how the dispatch function is used to respond to click and hover events, and how these are only enabled if it’s a human player’s turn.

let showSquare dispatch humanPlaying (location, square, view) =
    let cellProps : IHTMLProp list =
        match view with
        | Plain -> plainCellProps
        | PossibleMove -> possibleMoveCellProps
        | PossibleMoveHover -> possibleMoveHoverCellProps
        | WouldFlip -> wouldFlipCellProps

    let cellContent =
        match square, view with
        | Empty, _ -> []
        | Piece Black, WouldFlip -> blackFlipPiece
        | Piece Black, _ -> blackPiece
        | Piece White, WouldFlip -> whiteFlipPiece
        | Piece White, _ -> whitePiece
    
    let onHover = OnMouseOver (fun _ -> Hover location |> dispatch) :> IHTMLProp
    let onClick = OnClick (fun _ -> Click location |> dispatch) :> IHTMLProp

    let props = if humanPlaying then (onClick :: onHover :: cellProps) else cellProps

    td props cellContent

Finally we can loop through the squares and render them as an HTML table:

let showBoard dispatch humanPlaying boardView =
    let rows =
        boardView.SquareViews
        |> List.map (fun row -> 
            tr [] (row |> List.map (showSquare dispatch humanPlaying)))
    
    Table.table
        [ Table.IsBordered
          Table.IsNarrow
          Table.Props
            [ Style [ TableLayout "fixed"; Height "400px"; Width "400px" ] ] ]
        [ tbody [] rows ]

Computer players

Don’t get too excited here – beating these "AI"s is not very difficult…

All a computer player has to do is to be able to choose a move given a board position:

type ComputerPlayer =
    {
        ChooseMove: OngoingGame -> PossibleMove
    }

Our simplest player just selects one of the possible moves at random:

ChooseMove = fun ongoingGame ->
    let choice = random.Next(0, ongoingGame.PossibleMoves.Length)
    ongoingGame.PossibleMoves.Item choice

A slightly more interesting player is one who tries to flip as many pieces as possible with each move (which is actually a terrible strategy). The code is made more complicated by picking randomly from any moves that tie for the most flips – I tried to keep an element of randomness to stop games between two computer players from developing identically each time:

ChooseMove = fun ongoingGame ->
    let movesWithMostFlips =
        ongoingGame.PossibleMoves
        |> List.groupBy (fun pm -> pm.Flips.Length)
        |> List.maxBy fst
        |> snd
    let choice = random.Next(0, movesWithMostFlips.Length)
    movesWithMostFlips.Item choice

A more complex player can be created using the minimax decision rule, which picks the move that maximises some score measure assuming the opponent plays perfectly. As the number of possible move combinations tends to rise exponentially with the ply (the number of moves ahead we’re analysing) we still need a score measure to evaluate eventual positions.

The essentials of the minimax algorithm look like this (for simplicity, edge cases and logging are not shown), assuming the score measure is called heuristicOngoing:

let minimax maxDepth board =
    let rec minimaxCalc depth board =
        let gameInfo = Board.toGameInfo board

        match gameInfo.State with
...
        | Ongoing ongoing when depth >= maxDepth ->
            let score = heuristicOngoing ongoing
            score
        | Ongoing ongoing ->
            let scores =
                ongoing.PossibleMoves
                |> List.map (fun pm -> minimaxCalc (depth + 1) pm.Result)
            let bestScore = if board.NextToMove = Black then List.max scores else List.min scores
            bestScore

    (minimaxCalc 0 board, heuristicEvaluations)

My very simple score measure for an ongoing game allocates 1 point per piece, 3 per possible moves and 10 for each corner occupied – corners can’t be flipped!

let heuristicOngoing (ongoing: OngoingGame) =
    let piecesScore = ongoing.Board.NumBlack - ongoing.Board.NumWhite
    let movesScore = ongoing.PossibleMoves.Length * if ongoing.Board.NextToMove = Black then 1 else -1
    let cornersScore =
        ongoing.Board
        |> corners
        |> List.sumBy (fun sq ->
            if sq = Piece Black then 1
            elif sq = Empty then 0
            else -1)
    
    float (piecesScore + 3 * movesScore + 10 * cornersScore)

For completed games, a score of +/- 1000 is assigned for a win or loss.

Even with maxDepth set to only 2, this algorithm will comfortably beat the simpler players above.

Performance

With maxDepth 2, the computer player will spend around five seconds per complete game when running in .NET, although the performance when converted to JavaScript is much worse. The most complicated positions tend to occur in the middle of a game, when the number of possible moves are higher. Typically up to a few thousand positions are analysed per move in this case.

The computer players could be improved in straightforward ways:

• cacheing potential move trees
• calculating while the human player is thinking
• optimising the code with the JavaScript target platform in mind
• parallelising the calculations (although I’m not sure this is possible in JavaScript)
• a smarter score measure

Let me know what you think!