How to return the best first level in this F# minimax?
-
29-09-2019 - |
Question
This question is more a semantic-algorithmic-data-structure question than a F# syntactically question. I have a Minimax algorithm. The minimax algorithm should return the best next move, from a start position. To do this, it calculus all next moves, then the next-next-moves until a determined depth or until there is no more moves. It builds a tree like this:
P
/ \
a b
/ \
c d
I have the fallowing data struct to handle the tree:
type TreeOfPosition =
| LeafP of Position * int
| BranchP of Position * TreeOfPosition list
In the exemple tree above, P
and a
are Branchs and b
, c
and d
are Leafs. The code below is my minimax algorithm:
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 code are returning me a Leaf, for example, c
. When I changed the recursion call to
| BranchP(position, children) ->
LeafP(position,
getStaticEvalFromNode(minimax.[minOrmax](
List.map (loop (1 - minOrmax)) children)))
And this modification makes the static value of a good leaf go up. I need to return the best second level node. Hope somebody can help! Pedro Dusso
EDIT 1
Thanks for all answers guys, they help me a lot. Sorry about didn't specified the things very much. Let's go in parts:
1) I’m matching my LeafP like LeafP(position, 0)
because when I create my tree I set the leafs with a default value of 0 as its static value. As I’m going up my static values, eliminating the leaf and making the (before Branches) leafs with (min or max) static values I thought that this way I would prevent to evaluate a ex-Branch leaf (because it would not have the 0 value).
2) My biggest problem was to get the second level (the next move which has to be played) best position back. I solved it this way:
let evaluateTreeHOF ( tree, player : int) =
let rec loop minOrmax node =
match node with
| LeafP(position, 0) -> LeafP(position, evaluateLeaf(position))
| BranchP(position, children) -> LeafP(position,(children
|> List.map (loop (1 - minOrmax))
|> minimax.[minOrmax]
|> getStaticEvalFromNode))
match tree with
| BranchP(position, children) -> children |> List.map (loop (1 - player)) |> minimax.[player]
Instead of passing the entire tree, I’m passing just the children’s of the start node, and filtering the resulted list (a list of ex-Branches with the static values which went up for be the best for its current level) again. This way I’m getting the node I wanted.
I thought the kvb answers very interesting, but a little complicated to me. The other ones I understudied, but they just give me back the static value – and I could not make them to work for me :(
Thanks a lot for all the answers, all of them inspired me a lot.
Here is my full code: (http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm)
Pedro Dusso
Solution
I don't quite understand some aspects of your sample (e.g. why do you match only against leaves with 0s in them?), so I'll make a few changes below. First of all, let's generalize the tree type a bit, so that it can store any types of data in the leaves and branches:
type Tree<'a,'b> =
| Leaf of 'a
| Branch of 'b * Tree<'a,'b> list
Let's also use a dedicated player type, rather than using 0 or 1:
type Player = Black | White
Finally, let's generalize the evaluation of the best move a bit, so that the leaf evaluation function is passed in as an argument:
let bestMove evalPos player tree =
// these replace your minimax function array
let agg1,agg2,aggBy =
match player with
| Black -> List.min, List.max, List.maxBy
| White -> List.max, List.min, List.minBy
// given a tree, this evaluates the score for that tree
let rec score agg1 agg2 = function
| Leaf(p) -> evalPos p
| Branch(_,l) -> agg1 (List.map (score agg2 agg1) l)
// now we use just need to pick the branch with the highest score
// (or lowest, depending on the player)
match tree with
| Leaf(_) -> failwith "Cannot make any moves from a Leaf!"
| Branch(_,l) -> aggBy (score agg1 agg2) l
OTHER TIPS
I think you can use mutually recursive functions:
let maxTree t =
match t with
| child -> xxx
| subtrees s ->
s |> Seq.map minTree |> Seq.max
and minTree t =
match t with
| child -> xxx
| subtrees s ->
s |> Seq.map maxTree |> Seq.min
The solution to this problem was described in the F#.NET Journal article Games programming: tic-tac-toe (31st December 2009) and uses the following pattern:
type t = Leaf | Branch of t seq
let aux k = function
| Leaf -> []
| Branch s -> k s
let rec maxTree t = aux (Seq.map minTree >> Seq.max) t
and minTree t = aux (Seq.map maxTree >> Seq.min) t
See also the playable demo.