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

• 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). – Jack P. Oct 6 '13 at 17:43
• will this help? – Taufiq Oct 6 '13 at 18:00
• Not really. It's just more difficult to suggest changes if I can't put the code into VS and compile it. – Jack P. Oct 6 '13 at 18:17

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

• its not working :( i am get the wrong answer seems like alpha beta not changing is value. – Taufiq Oct 7 '13 at 3:35
• All the value of GetVal is 10 or -10, value of alpha beta does not change – Taufiq Oct 7 '13 at 5:56
• 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. – Jack P. Oct 7 '13 at 12:37
• dl.dropboxusercontent.com/u/87039989/TicTacToe.zip here is the code. – Taufiq Oct 7 '13 at 15:38
• 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. – Jack P. Oct 14 '13 at 12:29