Wie Sie die beste erste Stufe in diesem F # Minimax zurückzukehren?

Question

Diese Frage ist eine semantisch-algorithmischen-Daten-Struktur Frage als ein F # syntaktisch Frage. Ich habe einen Minimax-Algorithmus. Der Minimax-Algorithmus sollte den besten nächsten Schritt zurückkehrt, von einer Startposition. Um dies zu tun, Infinitesimalrechnung es alle nächsten Schritte, dann die nächsten nächsten bewegt, bis eine bestimmte Tiefe oder bis es nicht mehr bewegt. Es baut einen Baum wie folgt:

     P  
   /  \  
 a      b  
/ \  
c d

Ich habe die Brache Daten struct den Baum zu behandeln:

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

Im exemple Baum oben, P und a sind Branchs und b, c und d sind Leafs. Der folgende Code ist mein Minimax-Algorithmus:

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

Dieser Code kehrt mich ein Blatt, zum Beispiel c. Wenn ich die Rekursion Aufruf geändert

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

Und diese Änderung macht den statischen Wert eines guten Blatt steigen. Ich brauche die beste zweite Ebene Knoten zurückzukehren. Hoffnung jemand kann helfen! Pedro Dusso

EDIT 1

Danke für alle Antworten Jungs, sie helfen mir sehr. Leider haben über die Dinge nicht angegeben sehr. Gehen wir in Teilen:

1) Ich bin meinen LeafP wie LeafP(position, 0) passend, denn wenn ich meinen Baum erstelle ich die Blätter mit einem Standardwert von 0 als statischem Wert gesetzt. Wie werde ich meine statischen Werte, wodurch das Blatt und die Herstellung der (vor Branches) Blätter mit (min oder max) statischen Werten bis dachte ich, dass diese Art und Weise würde ich ein Ex-Zweig Blatt zu bewerten verhindern (weil es nicht hätte der Wert 0).

2) Mein größtes Problem war die zweite Ebene (den nächsten Schritt zu erhalten, die gespielt werden muss) beste Position zurück. Ich löste es so aus:

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]

Statt den gesamten Baum vorbei, ich bin nur auf die Kinder des Startknotens und Filtern die Folge Liste (eine Liste von Ex-Zweig mit den statischen Werten, die für sein aktuelles Niveau für seine bestes stiegen) nochmal. Auf diese Weise erhalte ich den Knoten ich wollte.

Ich dachte, die KVB Antworten sehr interessant, aber ein wenig zu mir kompliziert. Die andere, die ich under, aber sie geben mir nur den statischen Wert zurück - und ich konnte sie nicht für mich an die Arbeit machen: (

Vielen Dank für alle Antworten, die alle von ihnen hat mich sehr inspiriert.

Hier ist mein vollständiger Code: ( http: //www.inf .ufrgs.br / ~ pmdusso / Werke / Functional_Implementation_Minimax_FSharp.htm )

Pedro Dusso

Answer 1

Ich verstehe nicht ganz, einige Aspekte Ihrer Probe verstehen (z warum passen Sie nur gegen Blätter mit 0s in ihnen?), So dass ich ein paar Änderungen unten machen werde. Zunächst einmal wollen wir verallgemeinern der Baum etwas geben, so dass es alle Arten von Daten, die in den Blättern und Zweigen speichern können:

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

Lassen Sie uns auch einen eigenen Spieler-Typ verwenden, anstatt mit 0 oder 1:

type Player = Black | White

Schließlich wollen wir verallgemeinern die Auswertung des besten ein wenig bewegen, so dass die Blattbewertungsfunktion in als Argument übergeben wird:

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

Ich glaube, Sie können sich gegenseitig rekursive Funktionen zur Verfügung:

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

Die Lösung für dieses Problem wurde in den F # .NET Journal Artikeln beschrieben Spiele-Programmierung: Tic-Tac-toe (31. Dezember 2009) und verwendet das folgende Muster:

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

Siehe auch die spielbare Demo .