Comment retourner le meilleur premier niveau dans ce F # Minimax?

Question

Cette question est plus une question sémantique-données algorithmiques de structure que la question d'un F #. J'ai un algorithme Minimax. L'algorithme minimax devrait revenir le meilleur prochaine étape, à partir d'une position de départ. Pour ce faire, il calcul tous les prochains mouvements, puis les prochaines-next-se déplace jusqu'à une profondeur déterminée ou jusqu'à ce qu'il n'y a plus de mouvements. Il construit un arbre comme ceci:

     P  
   /  \  
 a      b  
/ \  
c d

Je la struct de données pour gérer l'mise en jachère arbre:

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

Dans l'arborescence ci-dessus exemple, P et a sont Branchs et b, c et d sont des feuilles. 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écursion à

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

Et cette modification rend la valeur statique d'une bonne feuille aller vers le haut. Je dois retourner le meilleur noeud de second niveau. quelqu'un Hope peut vous aider! Pedro Dusso

EDIT 1

Merci pour tous les gars réponses, ils me aident beaucoup. Désolé pour ne pas précisé les choses très bien. Entrons parties:

1) Je suis correspondant à ma LeafP comme LeafP(position, 0) parce que quand je crée mon arbre, je mets les feuilles avec une valeur par défaut de 0 comme valeur statique. Comme je vais mes valeurs statiques, ce qui élimine la feuille et de faire les (avant Branches) leafs avec (min ou max) des valeurs statiques je pensais que cette façon j'empêcherait d'évaluer une feuille ex-Branche (parce qu'il ne serait pas la valeur 0).

2) Mon plus gros problème était d'obtenir le deuxième niveau (la prochaine étape qui doit être joué) meilleur retour de position. 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 juste les enfants du noeud de départ, et filtrer la liste résultat (une liste des ex-branches avec les valeurs statiques qui est passé pour être le meilleur pour son niveau actuel) encore. De cette façon, je deviens le nœud que je voulais.

Je pensais que les réponses de KVB très intéressant, mais un peu compliqué pour moi. Les autres j'insuffisamment étudiés, mais ils me redonner la valeur statique - et je ne pouvais pas les faire travailler pour moi: (

Merci beaucoup pour toutes les réponses, tous m'a beaucoup inspiré.

Voici mon code complet: ( http: //www.inf .ufrgs.br / ~ pmdusso / travaux / Functional_Implementation_Minimax_FSharp.htm )

Pedro Dusso

Answer 1

Je ne comprends pas tout à fait certains aspects de votre échantillon (par exemple pourquoi ne vous correspondez que contre les feuilles avec eux dans 0s?), Donc je vais faire quelques changements ci-dessous. Tout d'abord, nous allons généraliser l'arbre de type un peu, de sorte qu'il peut stocker tout type de données dans les feuilles et les branches:

type Tree<'a,'b> = 
| Leaf of 'a 
| Branch of 'b * Tree<'a,'b> list

Utilisons aussi un type de lecteur dédié, plutôt que d'utiliser 0 ou 1:

type Player = Black | White

Enfin, nous allons généraliser l'évaluation des meilleurs bouger un peu, de sorte que la fonction d'évaluation de la feuille est passée en 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 

Answer 2

Je pense que vous pouvez utiliser les fonctions mutuellement récursives:

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

Answer 3

La solution à ce problème a été décrit dans le F # .NET article Journal programmation Jeux: tic-tac-toe (31ème Décembre 2009) et utilise le schéma suivant:

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

Voir aussi démo jouable .