Как вернуть лучший первый уровень в этом Minimax?

https://stackoverflow.com/questions/3114736

29-09-2019
|

Вопрос

Этот вопрос-скорее вопрос семантической алгоритмической структуры-структуры, чем синтаксически вопрос F#. У меня есть минимальный алгоритм. Алгоритм Minimax должен вернуть лучший следующий ход с начальной позиции. Для этого он исчисляет все следующие движения, а затем следующий-следующий тк. Это строит дерево, как это:

     P  
   /  \  
 a      b  
/ \  
c d

У меня есть постоянная структура данных для обработки дерева:

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

В экзативном дереве выше, P а также a ветви и b, c а также d листья. Приведенный ниже код является моим минимальным алгоритмом:

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

Например, этот код возвращает мне лист, c. Анкет Когда я изменил рекурсию

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

И эта модификация делает статическое значение хорошего листа. Мне нужно вернуть лучший узел второго уровня. Надеюсь, кто -нибудь сможет помочь! Педро Дюссо

Редактировать 1

Спасибо за все ответы, ребята, они мне очень помогают. Извините за то, что не указал вещи. Пойдем по частям:

1) Я соответствует своему листа LeafP(position, 0) Потому что, когда я создаю свое дерево, я установил листья со значением по умолчанию 0 в качестве его статического значения. Когда я поднимаю свои статические значения, устраняя лист и делая (до ветвей) листьев со статическими значениями (мин или максимума), я думал, что таким образом я не буду оценить лист бывшего ветвла (потому что он не будет значение 0).

2) Моя самая большая проблема состояла в том, чтобы получить второй уровень (следующий шаг, который должен быть сыгран) лучшая позиция назад. Я решил это так:

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]

Вместо того, чтобы передавать все дерево, я передаю только детьми стартового узла и фильтрую полученный список (список бывших ветвей со статическими значениями, которые снова стали лучшими для его текущего уровня). Таким образом, я получаю узел, который хотел.

Я думал, что KVB отвечает очень интересным, но немного сложным для меня. Другие, которые я изучил, но они просто вернули мне статическую ценность - и я не мог заставить их работать на меня :(

Большое спасибо за все ответы, все они вдохновили меня.

Вот мой полный код: (http://www.inf.ufrgs.br/~pmdusso/works/functional_implementation_minimax_fsharp.htm)

Педро Дюссо

Решение

I don't quite understand some aspects of your sample (e.g. why do you match only against leaves with 0s in them?), so I'll make a few changes below. First of all, let's generalize the tree type a bit, so that it can store any types of data in the leaves and branches:

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

Let's also use a dedicated player type, rather than using 0 or 1:

type Player = Black | White

Finally, let's generalize the evaluation of the best move a bit, so that the leaf evaluation function is passed in as an 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

Другие советы

I think you can use mutually recursive functions:

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

The solution to this problem was described in the F#.NET Journal article Games programming: tic-tac-toe (31st December 2009) and uses the following pattern:

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