Coding Functional style taking longer time than its Imperative style

I wanted to try out F# so I decided to I converted a library file from c# to f#. I have done that successfully(thanks a you people in stackoverflow). At first I ported the code from c# to f#. Than I tried to covert the code into FP after a lot of pain I have managed to get this far.

Here is the Source Code for the whole project if anyone what to use it.

dl.dropboxusercontent.com/u/87039989/TicTacToe.zip The code has changed so the speed test may not be 100%. To the one here.

[Speed: Average of 5 calls to Move() with same scenario]

C# 466.4 (ticks/1000)

public class Agent
{
    private readonly Reffery _reff = new Reffery();

    public Agent(Board cBoard, int symbol)
    {
        this.Symbol = symbol;
        RootBoard = new Board(cBoard);
    }

    public Board RootBoard { get; set; }
    public int Symbol { get; set; }

    public int Move()
    {
        var max = -10;
        var bestMove = 0;
        if (RootBoard.MoveNumber == 0)
            return 4;
        for (var i = 0; i = max)
            {
                max = val;
                bestMove = i;
            }
        }
        return bestMove;
    }
    private int MinMaxAlphaBeta(Board board, bool min, int alpha, int beta)
    {

        var point = BoardPoint(board);
        if (point != -2)
        {
            return point;
        }
        for (var i = 0; i  alpha)
                alpha = val;
        }
        return min ? beta : alpha;
    }

    private int BoardPoint(Board board)
    {
        int hum = Symbol == 1 ? 2 : 1;
        var condition = _reff.checkBoardCondition(board);
        if (condition == (Reffery.Condition)Symbol) return 1;
        if (condition == (Reffery.Condition)hum) return -1;
        if (condition == (Reffery.Condition.Draw)) return 0;
        return -2;
    }
}

F# imperative 327(Ticks/1000)

```
type Agent(board:Board,symbol:int)=
let mutable _nodeCount=0;
let mutable _rootBoard= new Board(board)

let mutable _symbol = symbol
let mu

To start, I see a few issues with the functional version of your code which are contributing to the performance loss:

• Whenever you need maximum performance, use arrays instead of list or seq (if feasible for your specific application). Functions operating on arrays are generally faster than those operating on lists or sequences.

• Avoid creating intermediate variables. There are several places in the functional version of your code where you create a sequence, transform it into a list, then call a function (e.g., List.max) which uses the list once then discards it. That's fine to do when you're prototyping an application, but once things are working and you want to start improving the performance, look for places where you can consolidate two or more function calls to avoid creating intermediate variables. For example, you can use Seq.max instead of Seq.toList and List.max.

• Don't use ref cells unless you really need to. I know they seem like an obvious choice when you're coming from C#, since they allow you to update 'local' variables from within a locally-scoped function (e.g., your UpdateAlphaBeta function); however, they store your value in the heap instead of the stack so you end up paying an indirection penalty each time you access the value. You can often re-implement your functions to use recursion or mutual recursion and pass the values around to each other instead of using ref cells.

Here's a functional style reworking of your code. There are still some performance optimizations that could be made, but this code should be reasonably fast anyway (I would be surprised if it wasn't noticeably faster than your original functional code). You'll want to compile this in Release mode for benchmarking, otherwise the recursive functions won't get optimized/inlined into simple loops. I'd be interested to hear how this code performs in your benchmark, just to have the numbers to compare against your original code.

type Agent (board : Board, symbol : int) =
    let aisymbol = symbol
    let rootBoard = Board (board)
    let _reff = Boards.Reffery ()

    member private this.BoardPoint (board : Board) : int =
        let condition = _reff.checkBoardCondition (board)

        let human = if aisymbol = 1 then 2 else 1

        if condition = enum aisymbol then 1
        elif condition = enum human then -1
        elif condition = Reffery.Condition.Draw then 0
        else -2

    member private this.MinMaxAlphaBeta (board : Board, isMin : bool, alpha : int, beta : int) : int =
        let point = this.BoardPoint (board)
        if point <> -2 then point
        else
            let UpdateAlphaBeta x alpha beta =
                match x with
                | 10 ->
                    if isMin then
                        beta, alpha, beta
                    else
                        alpha, alpha, beta
                | _ ->
                    if isMin && x  alpha then
                        x, x, beta
                    else
                        x, alpha, beta

            let rec loop x alpha beta i =
                if i > 8 then x
                else
                    let x', alpha', beta' =
                        let x =
                            let b = Board (board)
                            if b.SetBoardBool i then
                                // NOTE : This is a _recursive_ call!
                                this.MinMaxAlphaBeta (b, not isMin, alpha, beta)
                            else 10

                        UpdateAlphaBeta x alpha beta

                    let x_new =
                        if isMin then min x x' else max x x'

                    loop x_new alpha' beta' (i + 1)

            let x_initial = 0
            loop x_initial alpha beta 0   // Start at the zero-th element.

    member this.Move () : int =
        if rootBoard.MoveNumber = 0 then 4
        else
            let GetVal i =
                let b = Board (rootBoard)
                if b.SetBoardBool i then
                    this.MinMaxAlphaBeta (b, true, -10, 10)
                else -3

            // Gets the index (in the range [0..8]) which produces the maximum value.
            let rec getMaxVal maxValue maxIndex i =
                if i > 8 then maxIndex
                else
                    let value_i = GetVal i
                    if value_i > maxValue then
                        getMaxVal value_i i (i + 1)
                    else
                        getMaxVal maxValue maxIndex (i + 1)

            getMaxVal (GetVal 0) 0 1

StackExchange Code Review Q#32319, answer score: 4