Come restituire il miglior primo livello in questo F # Minimax?

Question

Questa domanda è più una questione semantica-algoritmico-dati-struttura di un F # sintatticamente domanda. Ho un algoritmo di Minimax. L'algoritmo minimax deve restituire la prossima mossa migliore, da una posizione di partenza. Per fare questo, calcolo tutte le prossime mosse, quindi il prossimo-next-mosse fino ad una profondità determinato o fino a quando non ci sono più mosse. Si costruisce un albero come questo:

     P  
   /  \  
 a      b  
/ \  
c d

Ho il fermo, struct dati per gestire l'albero:

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

Nella struttura exemple sopra, P e a sono Branchs e b, c e d sono Leafs. Il codice che segue è il mio algoritmo 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

Questo codice mi stanno tornando una foglia, per esempio, c. Quando ho cambiato la chiamata ricorsione per

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

E questa modifica rende il valore statico di una foglia buon salire. Ho bisogno di tornare il migliore nodo di secondo livello. La speranza qualcuno può aiutare! Pedro Dusso

Modifica 1

Grazie per tutte le risposte ragazzi, mi hanno aiutato molto. Mi dispiace per non specificato le cose molto. Andiamo in parti:

1) Sto corrispondenza mia LeafP come LeafP(position, 0) perché quando creo il mio albero ho impostato le foglie con un valore predefinito di 0 come valore statico. Come sto andando i miei valori statici, eliminando la foglia e rendendo le foglie (prima di sportelli) con (min o max) valori statici ho pensato che in questo modo mi avrebbe impedito di valutare una foglia ex-Branch (perché non avrebbe il valore 0).

2) Il mio problema più grande era quello di ottenere il secondo livello (la prossima mossa che deve essere giocato) migliore posizione posteriore. Ho risolto in questo modo:

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]

Invece di passare l'intero albero, sto passando solo gli dei del nodo di partenza, e filtrare la lista risultato (un elenco di ex Rami con i valori statici che è andato in su per essere il migliore per il suo livello attuale) i bambini ancora. In questo modo sto diventando il nodo che volevo.

ho pensato che le risposte KVB molto interessante, ma un po 'complicato per me. Gli altri quelli poco studiato, ma semplicemente Ridammi il valore statico - e io non li potrebbe fare al lavoro per me: (

Grazie per tutte le risposte, tutti loro mi ha ispirato molto.

Ecco il mio codice completo: ( http: //www.inf .ufrgs.br / ~ pmdusso / opere / Functional_Implementation_Minimax_FSharp.htm )

Pedro Dusso

Answer 1

Io non riesco a capire alcuni aspetti del vostro campione (ad esempio perché si corrisponde solo contro foglie con 0 in loro?), Quindi dovrò fare alcuni cambiamenti sotto. Prima di tutto, diamo generalizzano l'albero tipo un po ', in modo che possa memorizzare tutti i tipi di dati nelle foglie e rami:

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

Diamo anche utilizzare un tipo player dedicato, piuttosto che utilizzare 0 o 1:

type Player = Black | White

Infine, cerchiamo di generalizzare la valutazione del miglior spostare un po ', in modo che la funzione di valutazione foglia viene passato come argomento:

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

Penso che si possa utilizzare le funzioni ricorsive reciprocamente:

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 soluzione a questo problema è stato descritto nell'articolo F # .NET Journal Giochi di programmazione: tic-tac-toe (31 dic 2009) e utilizza il seguente schema:

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

Si veda anche il giocabile demo .