Coding Functional style taking longer time than its Imperative style

Question

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 <= 8; i++)
 {
 var board = new Board(RootBoard);
 if (!board.SetBoardBool(i)) continue;
 var val = MinMaxAlphaBeta(board, true, -10, 10);
 if (val >= 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 <= 8; i++)
 {
 var newBoard = new Board(board);
 newBoard.Copy(board);
 if (!newBoard.SetBoardBool(i)) continue;
 var val = MinMaxAlphaBeta(newBoard, !min, alpha, beta);
 if (min && val < beta)
 beta = val;
 else if (!min && val > 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 mutable _reff = new Boards.Reffery()
 new (board:Board) = Agent(board,0)
 member this.Move() :int = 
 let mutable max= -10
 let mutable bestMove=0
 if _rootBoard.MoveNumber = 0 then 4
 else
 for i= 0 to 8 do
 let mutable b = new Board(_rootBoard)
 if b.SetBoardBool(i) then 
 let mutable value = this.MinMaxAlphaBeta(b, true, -10, 10)
 //Debug.Print (i.ToString() + " , " + value.ToString())
 if value >= max then
 max <- value
 bestMove <- i
 bestMove
 member private this.MinMaxAlphaBeta(board:Board, min:bool, alpha:int, beta:int):int=
 let mutable a=alpha //Extra Line
 let mutable b=beta //Extra Line
 let point = this.BoardPoint(board);
 if point <> -2 then
 point
 else
 for i = 0 to 8 do
 let mutable newBoard = new Board(board)
 if newBoard.SetBoardBool(i) then
 let mutable value = this.MinMaxAlphaBeta(newBoard,not min, a, b)
 if min && value < b then
 b <- value
 elif (not min) && value > a then
 a <- value;
 if min then b else a
 member private this.BoardPoint(board:Board):int=
 let hum = if _symbol= 1 then 2 else 1
 let mutable pos = _reff.checkBoardCondition(board)
 if pos = enum<Reffery.Condition> _symbol then 1
 elif pos = enum<Reffery.Condition> hum then -1
 elif pos = Reffery.Condition.Draw then 0
 else -2

F# functional 453.6(Ticks/1000)

type Agent(board:Board,symbol:int)=
 let aisymbol= symbol 
 let rootBoard= new Board(board)
 let _reff = new Boards.Reffery()
 member this.Move() :int =
 if rootBoard.MoveNumber=0 then 4
 else
 let GetVal (i)= 
 let b = new Board(rootBoard) 
 if b.SetBoardBool(i) then this.MinMaxAlphaBeta(b, true, -10, 10)
 else -3
 [| for i = 0 to 8 do yield (GetVal i , i) |] |> Array.max |> snd
 member private this.MinMaxAlphaBeta(board:Board, isMin:bool, alpha:int, beta:int):int=
 let betaF= ref beta
 let alphaF= ref alpha
 let point= this.BoardPoint(board)
 if point <> -2 then point
 else
 let UpdateAlplaBeta(x)= 
 if x <> 10 then
 if isMin && x < !betaF then betaF := x
 elif (not isMin) && x > !alphaF then alphaF:=x 
 x
 else if isMin then !betaF else !alphaF
 let GetVal (i,isMin,al, be)= 
 let b = new Board(board) 
 if b.SetBoardBool(i) then this.MinMaxAlphaBeta(b, isMin, al, be)
 else 10
 let list = [| for i =0 to 8 do yield UpdateAlplaBeta(GetVal (i, (not isMin), !alphaF , !betaF)) |]
 if isMin then list|>Array.min else list|>Array.max 
 member private this.BoardPoint(board:Board):int=
 let human = if aisymbol= 1 then 2 else 1
 let condition = _reff.checkBoardCondition(board)
 if condition = enum<Reffery.Condition> aisymbol then 1
 elif condition = enum<Reffery.Condition> human then -1
 elif condition = Reffery.Condition.Draw then 0
 else -2

The problem I am facing now is these two lines

 let betaF= ref beta
 let alphaF= ref alpha

I can't remove these two variables.

Also as you can see F# dll executes faster than its c# counter part but the one in functional style it take a bit more time to execute then the is imperative counter part, is this suppose to happen or is there something i am doing wrong? If so how can fix it?

Update

b.SetBoardBool(i)

set a move on position i for the current player and returns true is successful other wise false.

_reff.checkBoardCondition(board)

take a board object check if it has X or O win condition, draw or no condition at all.

• Jack P.: Any chance you could post the entire code? There are a number of simplifications you could make to your code to improve the performance, but it's difficult to know which optimizations you can really make without being able to look at the rest of the code (e.g., the definitions of Board and Refferey.Condition).
• Taufiq Abdur Rahman: will this help?
• Jack P.: Not really. It's just more difficult to suggest changes if I can't put the code into VS and compile it.

Answer 1

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<Reffery.Condition> aisymbol then 1
 elif condition = enum<Reffery.Condition> 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 < beta then
 x, alpha, x
 elif not 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

• Taufiq Abdur Rahman: its not working :( i am get the wrong answer seems like alpha beta not changing is value.
• Taufiq Abdur Rahman: All the value of GetVal is 10 or -10, value of alpha beta does not change
• Jack P.: I can't do any more unless you publish the rest of the code so I can compile/run it on my own machine. If you can't do that, then you'll have to debug the code and fix the problem yourself.
• Taufiq Abdur Rahman: dl.dropboxusercontent.com/u/87039989/TicTacToe.zip here is the code.
• Jack P.: Sorry, you'll have to modify it to suit your needs then. It should be straightforward to step through the code in the debugger to see where it's going wrong, and fix it to get the result you want.