Cette question est plus une question de structure de données sémantique-algorithmique qu'une question de syntaxe F #. J'ai un algorithme Minimax. L'algorithme minimax devrait renvoyer le meilleur coup suivant, à partir d'une position de départ. Pour ce faire, il calcule tous les mouvements suivants, puis le prochain suivant jusqu'à une profondeur déterminée ou jusqu'à ce qu'il n'y ait plus de mouvement. Il construit un arbre comme celui-ci:Comment retourner le meilleur premier niveau dans ce F minimax?
P
/\
a b
/\
c d
J'ai la struct de données mise en jachère pour gérer l'arbre:
type TreeOfPosition =
| LeafP of Position * int
| BranchP of Position * TreeOfPosition list
Dans l'arbre exemple ci-dessus, P
et a
sont Branchs et b
, c
et d
sont Leafs. Le code ci-dessous est mon algorithme minimax:
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
Ce code me renvoie une feuille, par exemple, c
. Quand j'ai changé l'appel récursif à
| BranchP(position, children) ->
LeafP(position,
getStaticEvalFromNode(minimax.[minOrmax](
List.map (loop (1 - minOrmax)) children)))
Et cette modification fait monter la valeur statique d'une bonne feuille. Je dois retourner le meilleur noeud de deuxième niveau. J'espère que quelqu'un peut vous aider! Pedro Dusso
EDIT 1
Merci pour tous les gars réponses, ils me aident beaucoup. Désolé pour n'a pas précisé les choses beaucoup. Allons en pièces:
1) Je suis correspondant à mon LeafP comme LeafP(position, 0)
parce que quand je crée mon arbre, je fixe les feuilles avec une valeur par défaut de 0 comme valeur statique. Comme je monte mes valeurs statiques, en éliminant la feuille et en faisant les feuilles (avant les branches) avec des valeurs statiques (min ou max) je pensais que de cette façon j'éviterais d'évaluer une feuille ex-Branch (parce qu'elle n'aurait pas la valeur 0).
2) Mon plus gros problème était d'obtenir le deuxième niveau (le prochain coup qui doit être joué) la meilleure position de retour. Je l'ai résolu de cette façon:
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]
Au lieu de passer tout l'arbre, je passe seulement aux enfants d'au noeud de départ, et filtrer la liste résultat (une liste des ex-branches avec les valeurs statiques qui sont allés pour être le meilleur pour son niveau actuel). De cette façon, je reçois le nœud que je voulais.
Je pensais que le kvb répondait très intéressant, mais un peu compliqué pour moi. Les autres j'insuffisamment étudiés, mais ils me redonnent la valeur statique -. Et je ne pouvais pas les faire fonctionner pour moi :(
Merci un lot pour toutes les réponses, tous m'a beaucoup inspiré
Voici mon code complet: (http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm)
Pedro Dusso
Pourriez-vous élaborer votre question encore un peu? – gradbot