Comment retourner le meilleur premier niveau dans ce F minimax?

Question

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:

 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

Answer 1

Je ne comprends pas tout à fait certains aspects de votre échantillon (par ex.pourquoi est-ce que tu ne fais que correspondre à des feuilles avec des 0 en eux?), 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 meilleures 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 la F # .NET Journal article Games programming: 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 la playable demo.