Back to Questions
4.5k
views12
comments
Minimax algorithm
f#functional

My name is Pedro Dusso and I’m from Porto Alegre, south Brasil. This is my first topic here, since I recently bought the Programming F#, from Chris Smith. I wish to learn F# first for have some fundamentation in the Functional world and second because I must chose a functional language to develop a class work.

I should implement a full Minimax algorithm (for the Alquerque board game). I already did it in C# last semester so I’m quite understand Minimax and its evaluation functions, move generators, etc (you can find it in [link:eukreukla.codeplex.com] .) I found something in ML, which looks like easy to “translate”, but much more than the syntax I want to learn the semantics of F#.

I started with a position type, to hold my board. I think a

type Piece = | BLACK | WHITE | EMPTY (this is for save space)

type position = Dictionary<int,Piece>

because I represent my board with a 25 vector in which index can be a black or white piece or could be empty. Then I defined a moves function which is moves: position -> position list. From a board configuration it results a list of possible boards configuration.

Then I arrive at my problem. I must define some kind of game tree. The nodes of this game tree are labeled by positions, such that the children of a node are labeled with the position that can be reached in one move from that node.

The game tree must be built by repeated applications of moves. Starting from the root position, moves is used to generate the labels for the sub-trees of the root. Move is then used again to generate the sub-trees of the sub-trees and so on. This pattern of recursion can be expressed as a higher-order function (reptree f a = node a (map (reptree f) (f a)) (1).

So, I don’t know what to do. I thought in some steps to do this:

1) Receive a N node

2) N.possibleMoves = moves ( N)

3) If N.possibleMoves.IsEmpty == true, end

4) Else List.map moves n.possibleMoves…

All code I could write (wrong) is here:

type treeNode = position * position list

let rec reptree (f, p : treeNode ) =

if ((snd (p)).IsEmpty) then (reptree(f (f p)))

else List.map (moves (snd (p)))

In the end, I just wanna a list of treeNodes (I think) to keep calculation the static value of each position and other Minimax stuff (yes, this is the beggning… I will bother you a lot)

Thanks in advance,

Pedro Dusso

.

Hi Pedro,
welcome!
You seem to be on the right track. One thing is not clear to me: do you need to keep the whole tree in memory? If so, you could do something like the following, where computeMoves generates the tree and evaluatePosition evaluates it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

type Piece = | BLACK | WHITE | EMPTY
type Position = Map<int*int, Piece> 
type TreeNode = Leaf of Position | Branch of Position * TreeNode list


let minimax = [| min; max |]


let initBoard () = (* unit -> Position *)
    ...


let isWin (position : Position) = (* Position -> bool *)
    ...


let isLoss (position : Position) = (* Position -> bool *)
    ...


let isDraw (position : Position) = (* Position -> bool *)
    ...


let rec computeMoves (position : Position) = (* Position -> TreeNode *)
    if isWin position || isLoss position || isDraw position then Leaf(position)
    else
        do_Some_Magic_and_Call_Recursively


let evaluateLeaf (position : Position) = (* Position -> int *)
    if isWin positions then 1
    elif isLoss positions then -1
    else 0


let evaluatePosition (startPosition : Position) (player : int) (* 0, 1 *) =
    let root = computeMoves startPosition
    let rec loop minORmax node =
        match node with
            | Leaf(position) -> evaluateLeaf position
            | Branch(position, children) -> children |> List.map (loop (1 - minORmax)) |> List.reduce (minimax.[minORmax])
    loop root player

Note that:
1) I used map instead of dictionary for the board representation (that's an immutable implementation of dictionary).
2) The evaluation is NOT tail recursive (BAD).
3) I use a 0,1 index to pick the function to be used to reduce the list of children of the current node and then i switch it passing (1-currentIndex) to the next level.
4) You could have an implementation where you generate nodes as you evaluate them and keep memory requirements low.

Also, since it's you first post, you might want to check this out.
Good luck!

By on 6/17/2010 4:28 AM ()

Thanks for the answers mau! They helped a lot.

I putted all my "stable code" until now here: [link:www.inf.ufrgs.br] I dont know which is better, post it here or leave it there...you tell me!

As you can see, I did it a little different from what you told me. I made a computeMoves function to generate the Position lists and then use it inside a computeTree (good tree data structure ;) function. I liked the result.

I'm trying to do it the most modularized as I can, so after I got a Tree of Position, I'm thinking about passing this tree to a "evaluateTree" function, that will work together some other "prune x" function. Just when I get to the leafs I must use the evaluateLeaf function. This way, I hope, I can change the static evaluation function easily.

I'm posting again to ask you (or somebody else...) to explain your evaluatePosition function and how does minimax work with it.

What a immutable implementation does mean? It’s something like define all my keys when I'm constructing the object? I must have a mutable data structure because I need to move and “eat" the pieces all the time...

Thanks again,

Pedro Dusso

By on 6/17/2010 6:39 PM ()

I'm posting again to ask you (or somebody else...) to explain your evaluatePosition function and how does minimax work with it.

My evaluatePosition (which actually evaluates the tree) is a simple recursion that,
- when a leaf is found, evaluates the position as a win or loss
- for intermediate nodes, calls (maps) itself on all the children (

1

children |> List.map (loop (1 - minORmax))

) and then applies min or max on the resulting list of scores, depending on depth in the tree (

1

|> List.reduce (minimax.[minORmax])

).

Minimax is the array of (min, max) functions and minORmax is the index that is switched between 0 and 1 between recursive calls.

What a immutable implementation does mean? It’s something like define all my keys when I'm constructing the object? I must have a mutable data structure because I need to move and “eat" the pieces all the time...

Thanks again,

Pedro Dusso

An immutable data structure like map does not indeed let you change the contents. However, it defines add/remove/etc operations that return a new object with the new contents. In the case of map, add and remove operations create a new map thta shares most of the nodes with the old one, thus not duplicating memory requirements every time a new object is created.

By on 6/18/2010 2:08 AM ()

Hello again!

I think I’m having a good progress, but I still having some difficulties =/.

I project my minimax working something like this:

1
2

let nextPosition = evaluateTree computeTree startPosition

I imagine this working something like computeTree creating a tree of TreeOfPosition (the one you defined ), using the computeMove for that. The tree generated is like this:

val a : TreeNode =

Branch

(dict [(1, EMPTY)],

[Branch

(dict [(2, BLACK)],

[Branch (dict [(4, BLACK)],[]); Branch (dict [(5, WHITE)],[])]);

Branch (dict [(3, WHITE)],[])])

Then, the evaluateTree takes this tree and navigate through it evaluating the Leaf nodes and sending the better ones up.

For this, based in your (very good) tips I built this functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Func: computeTree : Position -> TreeOfPosition

// Desc: Takes a game-position as its argument and returns a tree of all positions that can be reached from it in one move.

// Args: (position : Position) a position (board configuration) to generate the next moves from.

let rec computeTree (position : Position) = 

    if isWin position || isLoss position then 

        LeafP(position)

    else

        let nextMoves = computeMoves position

        BranchP(position, List.map computeTree nextMoves)

And

1
2
3
4
5
6
7
8
9
10
11
12

let evaluateTree ( tree : TreeOfPosition) (player : int) =

    let rec loop minOrmax node =

        match node with

            | LeafP(position) -> evaluateLeaf position

            | BranchP(position, children) -> children |> List.map  (loop (1 - minOrmax)) |> List.reduce (minimax.[minOrmax])

    loop player tree

In the List.reduce I’m getting this error:

Minimax.fs(147,106): error FS0001: This expression was expected to have type

int -> int -> int

but here has type

int

I don’t know this is the right way…

Thanks very much

Pedro Dusso

By on 6/19/2010 4:22 PM ()

I don't know if that's the problem, but you might need to add a type annotation on the minimax definition, like so:

1

let minimax = [| (min : int->int->int); max |]
By on 6/20/2010 5:22 AM ()

Yes, it "compiled"!

I'm trying to understand you function (because I'm still having troubles with the pipe operator...)

The match is works like a powerful C# switch right? It will marry my current node with Leaf or Branch.

If it is Leaf, I will evaluate its position (which returna a integer).

If it is a Branch, it will come back the recursion selecting the min or the max (depending the node high right?) of two nodes and I dont understang anymore :P

Could you right in the "normal" way like f(g(x))...

PS.: i tihnk I'm gonna use 

1

 let minimax = [| List.min; List.max |]

because I must get the min or the max value of a list of node's children...

PD

By on 6/20/2010 3:23 PM ()

The match is works like a powerful C# switch right? It will marry my current node with Leaf or Branch. If it is Leaf, I will evaluate its position (which returna a integer). If it is a Branch, it will come back the recursion selecting the min or the max (depending the node high right?)

Correct.

Could you right in the "normal" way like f(g(x))...

Translation:

1
2
3
4
5
6
7

children |> List.map (loop (1 - minOrmax)) |> List.reduce (minimax.[minOrmax])


=


List.reduce (minimax.[minOrmax]) (List.map (loop (1 - minOrmax)) children)

PS.: i tihnk I'm gonna use [| List.min; List.max |] because I must get the min or the max value of a list of node's children... PD

Well, if your list is made of numeric values, that will work. So in the last step you could do:

1
2
3
4
5
6
7
8
9
10

let minimax = [| List.min; List.max |]


children |> List.map (loop (1 - minOrmax)) |> minimax.[minOrmax]


=


minimax.[minOrmax] (List.map (loop (1 - minOrmax)) children)
By on 6/21/2010 2:16 AM ()

Thanks very much! Its clearly now to me... and worked.

1
2
3
4
5
6
7
8
9
10
11
12

let evaluateTree ( tree : TreeOfPosition, player : int) =

	let rec loop minOrmax node =

		match node with

			| LeafP(position) -> evaluateLeaf position

			| BranchP(position, children) -> List.reduce (minimax.[minOrmax]) (List.map (loop (1 - minOrmax)) children)

	loop player tree

For example, when I build a tree like:

BranchP

(dict [(1, BLACK); (8, WHITE)],

[BranchP

(dict [(2, BLACK)],[LeafP dict [(4, BLACK)]; LeafP dict [(5, WHITE)]]);

LeafP dict [(3, WHITE)]])

which looks like this (with the (virtual) static evaluation in the parantheses)

p1

...a

.......c(-10)/d(0) //takes the min here

...b(0)

p1

...a(0) // takes the max here (i believe i will choose the left branch if they are equal, no bigger reasons)

...b(0)

Them the evaluateTree function returns (int) 0. Wonderful!

However, I need the Position of the value, which in my data struct I think I'm nothing handling.

1
2

type TreeOfPosition = LeafP of Position | BranchP of Position * TreeOfPosition list

As you sad, if mylist is made of numeric values, that will work - but its not... I'm thinking something like this:

1
2

type TreeOfPosition = LeafP of Position * int | BranchP of Position * TreeOfPosition list

Adding a int value to the Leaf tuple I believe I can sort it by this int, which will be the result of the static evaluation.

I look after the List.sort and it requieres a Operators.compare (for non default comparison I believe). So I tested:

1
2
3
4
5
6

let l1 = LeafP(p,2)

let l2 = LeafP(p,3)

Operators.compare l1 l2

And, as I expected, get a error.

"The type 'TreeOfPosition' does not support the 'comparison' constraint because it is a record, union or struct with one or more structural element types which do not support the 'comparison' constraint. Either avoid the use of comparison with this type, or add the 'StructuralComparison' attribute to the type to determine which field type does not support comparison".

And now I'm looking for a way to get this done. I believe this way I can built a let minimax = [| MyOwnMin; MyOwnMax |] which will select the min or the max of the TreeOfPosition list. I believe this is something like implementing a IComparable compareTO in C#?

Thanks one more time,

Pedro

PS.: I dont know why im losing identation....

By on 6/21/2010 4:49 PM ()

I working in something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

[<CustomEquality;CustomComparison>]

type TreeOfPosition = 

    { LeafP   : Position * staticValue;

      BranchP : Position * TreeOfPosition list}

    override x.Equals(yobj) = 

        match yobj with

        | :? TreeOfPosition as y -> (snd x.LeafP = snd y.LeafP)

        | _ -> false

    override x.GetHashCode() = hash (snd x.LeafP)

    interface System.IComparable with

        member x.CompareTo yobj =

            match yobj with

            | :? TreeOfPosition as y -> compare (snd x.LeafP) (snd y.LeafP)

            | _ -> invalidArg "yobj" "cannot compare value of different types"

Hopefully this will work...

By on 6/21/2010 6:23 PM ()

I manage the TreeOfPosition to work with List.min and List.max.

More than override the x.Equals and x.GetHashCode, I needed a particularly mycompare function to work in the tuple, because of its singularly structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

 

[< CustomEquality ; CustomComparison >]

type TreeOfPosition =   

   | LeafP   of Position * int

   | BranchP of Position * TreeOfPosition list

   static member mycompare (x, y) = 

      match x, y with

      // Compare values stored as part of your type

      | LeafP(_, n1), LeafP(_, n2) -> compare n1 n2

      | _ -> 0 // or 1 depending on which is list...

   override x.Equals(yobj) = 

      match yobj with

      | :? TreeOfPosition as y -> (x = y)

      | _ -> false

   override x.GetHashCode() = hash (x)

      interface System.IComparable with

         member x.CompareTo yobj = 

            match yobj with 

            | :? TreeOfPosition as y -> TreeOfPosition.mycompare(x, y)

            | _ -> invalidArg "yobj" "cannot compare value of different types"

Lets "Keep walking" ;)

Pedro Dusso

By on 6/22/2010 2:08 PM ()

Hello again...

No that my List.min is working, the evaluateTree starts to work too. However it is returning a wrong answer. But dont get me wrong! The corret one is there, I just cant get it...

1
2
3
4
5
6
7
8
9
10
11
12

let evaluateTree ( tree : TreeOfPosition, player : int) =

    let rec loop minOrmax node =

        match node with

            | LeafP(position, 0) -> LeafP(position, evaluateLeaf(position))

            | BranchP(position, children)  -> minimax.[minOrmax](List.map (loop (1 - minOrmax)) children)

    loop player tree

This version in returning the TreeOfPosition node with the best (min or max) value of all tree. I mean, it navegates until the leafs, then evaluate all of then, gets the min (or max) and como back sending up that node.

This is wrong beacuse what I want is not a deep good node but the best in the first level (immediately below the start position) node.

So I change my function to

1
2
3
4
5
6
7
8
9
10
11
12

let evaluateTree ( tree : TreeOfPosition, player : int) =

    let rec loop minOrmax node =

        match node with

            | LeafP(position, 0) -> LeafP(position, evaluateLeaf(position))

            | BranchP(position, children)  -> LeafP(position, getStaticEvalFromNode(minimax.[minOrmax](List.map (loop (1 - minOrmax)) children)))

    loop player tree

Which sends up just the static value of the leaf nodes. However, when it finds the best node in the first level, it sends its value to the father node... and return this one :(

Any tips in how to solve this?

Thanks in advance, sorry bothering you so much folks... but I'm learning a lot

Pedro Dusso

By on 6/22/2010 7:11 PM ()

Hello guys,

I’m here to say thank you to all of you, especially mau! All the help you gave me made possible to complete this F# Minimax project.

You can access all the .fs files and project in this link ([link:www.inf.ufrgs.br] in English. Remembering, you can see the full project (C# + F#) at CodePlex in [link:eukreukla.codeplex.com.]

Thanks one more time,

Best Regards,

Pedro Dusso

By on 7/18/2010 2:54 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper