American Checkers with AI

This is the third question in the series. Number 1 had most of the official two-player rules implemented, and Number 2 was the basic UI. This one has the complete two-player rules implemented, an AI using minimax with alpha-beta pruning. All suggestions welcome, especially those that help me program in a more functionally and more cleanly.

Checkers.fs contains my basic types:

module public Checkers.Types
type Player = Black | White

type PieceType = Checker | King

type Coord = { Row :int; Column :int }

let offset c1 c2 =
        { Row = c1.Row + c2.Row; Column = c1.Column + c2.Column }

type Move = Coord List

type MoveTree = { Move :Move; Parent :Option; Children :Option> }

type internal AlphaBetaMove = { Alpha :float Option; Beta :float Option; Move :Move }

Piece.fs contains the information on a piece:

module public Checkers.Piece
open Checkers.Types

type Piece = { Player :Player; PieceType :PieceType }

let Promote piece = { Player = piece.Player; PieceType = King }

let whiteChecker = Some <| { Player = White; PieceType = Checker }
let whiteKing = Some <| { Player = White; PieceType = King }

let blackChecker = Some <| { Player = Black; PieceType = Checker }
let blackKing = Some <| { Player = Black; PieceType = King }

Board.fs contains a type alias and some helper methods:

```
module public Checkers.Board
open Checkers.Types
open Checkers.Piece
open System.Collections.Generic

type Board = Piece option list list

let square (coord :Coord) = List.item coord.Row >> List.item coord.Column

let rowFromSeq (value :'a seq) =
Some (List.ofSeq value)

let listFromSeq (value :'a seq seq) =
List.ofSeq (Seq.choose rowFromSeq value)

let defaultBoard =
[
List.replicate 4 [None; blackChecker] |> List.concat
List.replicate 4 [blackChecker; None] |> List.concat
List.replicate 4 [None; blackChecker] |> List.concat
List.replicate 8 None
List.replicate 8 None
List.replicate 4 [whiteChecker;

I don't like these at all:

let internal chooseNewAlpha currentAlpha (candidateAlpha :float Option) =
    match currentAlpha with
    | Some x -> if candidateAlpha.IsSome then Some  candidateAlpha

let internal chooseNewBeta currentBeta (candidateBeta :float Option) =
    match currentBeta with
    | Some x -> if candidateBeta.IsSome then Some  candidateBeta

In our chat you state you were told to use if when matching against a simple boolean (there's no specific reason to use it over match, or match over it for that situation, so I'll not comment on that) but you can rewrite that with one match instead of a match with a nested if:

let internal chooseNewAlpha currentAlpha (candidateAlpha :float Option) =
    match (currentAlpha, candidateAlpha) with
    | (Some current, Some candidate) -> Some  Some current
    | (None, Some candidate) -> Some candidate
    | _ -> None

let internal chooseNewBeta currentBeta (candidateBeta :float Option) =
    match (currentBeta, candidateBeta) with
    | (Some current, Some candidate) -> Some  Some current
    | (None, Some candidate) -> Some candidate
    | _ -> None

Why match with a Tuple? Because current and candidate are codependent: each one can affect the result of the other. So we want to take both into account idiomatically.

let internal moveIsDiagonal startCoord endCoord =
    startCoord <> endCoord &&
    System.Math.Abs(startCoord.Row - endCoord.Row) = System.Math.Abs(startCoord.Column - endCoord.Column)

F# has an abs method: startCoord <> endCoord && abs (startCoord.Row - endCoord.Row) = abs (startCoord.Column - endCoord.Column).

I would consider a refactor:

[]
let Rows = 7

[]
let Columns = 7

You use Rows and 0 in the same place, but now 0 doesn't make sense.

let internal kingRowIndex(player) =
    match player with
    | Player.Black -> Rows
    | Player.White -> 0

You should have:

[]
Rows = 8

[]
Columns = 8

[]
FirstRow = 0

[]
LastRow = Rows - 1

[]
FirstColumn = 0

[]
LastColumn = Columns - 1

Thus we have:

let internal kingRowIndex(player) =
    match player with
    | Player.Black -> LastRow
    | Player.White -> FirstRow

Some of your functions can take advantage of function composition:

let internal isValidJump startCoord endCoord (board :Board) =
    match (square startCoord board).Value.PieceType with
    | PieceType.Checker -> isValidCheckerJump startCoord endCoord board
    | PieceType.King -> isValidKingJump startCoord endCoord board

Could be something like:

let internal isValidJump startCoord endCoord (board:Board) =
    let jumpFunc =
        match (square startCoord board).Value.PieceType with
        | PieceType.Checker -> isValidCheckerJump
        | PieceType.King -> isValidKingJump

    jumpFunc startCoord endCoord board

let getPieceHops coord (board :Board) =
    let piece = (square coord board).Value
    let moves = 
        match piece.PieceType with
        | Checker -> checkerHops piece.Player
        | King -> kingHops piece.Player

    let hops = List.ofSeq (seq {
        for move in moves do
        let endCoord = offset coord move
        yield
            match coordExists endCoord && isValidHop coord endCoord board with
            | true -> Some [coord; endCoord]
            | false -> None })

    List.map (fun (item :Option) -> item.Value) (List.where (fun (item :Option) -> item.IsSome) hops)

Boy is that a mess.

You use a for loop (not F# idiomatic), filter in the for loop and return either None or Some, then use a List.map on a List.where to filter only the Some values and return the actual value.

You use a List.where, which is a synonym for List.filter (which is the preferred method), and the worst part is you use it on a list that could have already been filtered.

let getPieceHops coord (board :Board) =
    let piece = (square coord board).Value
    let moves = 
        match piece.PieceType with
        | Checker -> checkerHops piece.Player
        | King -> kingHops piece.Player

    let hopsFilter = List.filter (fun (head::tail) ->
        let startCoord = head
        let endCoord = tail |> List.head
        coordExists endCoord && isValidHop startCoord endCoord board)

    moves |> List.map (fun move -> [coord; offset coord move]) |> hopsFilter

We eliminated multiple excessive methods, and return the same thing you did initially. (Or should have.)

I've finally had time to review minimax, and I think this should be a suitable version that uses tail-call recursion and should do what you want.

Do note I've not tested this at all yet, this was a rewrite in Notepad. Something like the following should work, though you've mentioned to me in chat, so I've updated it substantially.

```
let rec minimax player searchDepth alpha beta (board:Board) =
match searchDepth = 0 || (isWon board).IsSome with
| true ->
let weightDifference = Some weightDifference

StackExchange Code Review Q#150652, answer score: 4