¿Cómo devolver el mejor primer nivel en este F # Minimax?

Question

Esta pregunta es más una cuestión-algorítmica-estructura de datos semántica de una pregunta F # sintácticamente. Tengo un algoritmo Minimax. El algoritmo minimax debe devolver el mejor movimiento siguiente, desde una posición de inicio. Para ello, se Cálculo Todos los próximos movimientos, entonces el siguiente-siguiente-se desplaza hasta una profundidad determinada o hasta que no haya más movimientos. Se construye un árbol como este:

     P  
   /  \  
 a      b  
/ \  
c d

Tengo la estructura de datos para manejar el barbecho del árbol:

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

En el árbol exemple anterior, P y a son Branchs y b, c y d son hojas. El código siguiente es mi 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

Este código me están volviendo una hoja, por ejemplo, c. Cuando cambié la llamada recursiva al

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

Y esta modificación hace que el valor estático de una hoja buena subir. Tengo que devolver el mejor nodo de segundo nivel. alguien esperanza puede ayudar! Pedro Dusso

EDIT 1

Gracias por todas las respuestas chicos, ellos me ayudan mucho. Lo siento por no especifica las cosas mucho. Vamos a ir por partes:

1) Estoy a juego mi LeafP como LeafP(position, 0) porque cuando creo mi árbol me puse las hojas con un valor por defecto de 0 como valor estático. Como estoy subiendo mis valores estáticos, lo que elimina la hoja y hacer que las hojas (antes de ramas) con valores estáticos (mínimos y máximos) pensé que de esta manera me impediría evaluar una hoja ex-Rama (porque no tendría el valor 0).

2) Mi mayor problema era conseguir el segundo nivel (el siguiente movimiento que tiene que ser jugado) la mejor posición de la espalda. Lo resuelto de esta manera:

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]

En lugar de pasar todo el árbol, que estoy pasando justo de las del nodo de inicio, y filtrar la lista de resultado (una lista de ex-Ramas con los valores estáticos que subió para ser el mejor para su nivel actual) a los niños de nuevo. De esta manera me estoy poniendo el nodo que quería.

Yo pensaba que las respuestas KVB muy interesantes, pero un poco complicado para mí. Los otros que poco estudiados, pero simplemente Devuélveme el valor estático - y no pude hacerlos funcionar para mí: (

Muchas gracias por todas las respuestas, todos ellos me inspiró mucho.

Aquí está mi código completo: ( http: //www.inf .ufrgs.br / ~ pmdusso / obras / Functional_Implementation_Minimax_FSharp.htm )

Pedro Dusso

Answer 1

Yo no entiendo muy bien algunos aspectos de su muestra (por ejemplo, ¿por qué coincidir sólo contra las hojas con 0s en ellos?), Así que voy a hacer algunos cambios a continuación. En primer lugar, vamos a generalizar el árbol escriba un poco, por lo que puede almacenar cualquier tipo de datos en las hojas y ramas:

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

Let También se utiliza un tipo de reproductor dedicado, en lugar de usar 0 o 1:

type Player = Black | White

Por último, vamos a generalizar la evaluación de la mejor moverse un poco, de modo que la función de evaluación de la hoja se pasa como un argumento:

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

Creo que se puede utilizar funciones mutuamente recursivas:

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 solución a este problema se describe en el artículo F # .NET Diario Juegos de programación: tic-tac-toe (31 de diciembre de 2009) y utiliza el siguiente patrón:

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

Véase también el jugable de demostración .