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

Этот вопрос больше относится к вопросу о семантической алгоритмической структуре данных, чем к синтаксическому вопросу 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 как 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)

Педро Дуссо


f# algorithm data-structures minimax
person Pedro Dusso    schedule 24.06.2010    source источник
comment
Не могли бы вы уточнить свой вопрос?   -  person gradbot    schedule 25.06.2010

Ответы (3)


arrow_upward
3
arrow_downward

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

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

Давайте также будем использовать выделенный тип игрока, а не использовать 0 или 1:

type Player = Black | White

Наконец, давайте немного обобщим оценку лучшего хода, чтобы функция оценки листа была передана в качестве аргумента:

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
person kvb    schedule 25.06.2010

arrow_upward
1
arrow_downward

Я думаю, вы можете использовать взаимно рекурсивные функции:

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
person Yin Zhu    schedule 25.06.2010
comment
Я не понял, что такое дочерний элемент и поддеревья в вашем коде. Листья и ветки? Я спрашиваю об этом, потому что поддерево является потомком верхнего узла ... Я не понял вашей точки зрения. - person Pedro Dusso; 25.06.2010

arrow_upward
0
arrow_downward

Решение этой проблемы описано в статье журнала F # .NET Программирование игр: крестики-нолики (31 декабря 2009 г.) и использует следующий шаблон:

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

См. Также игровую демонстрацию.

person J D    schedule 25.06.2010
comment
Мы можем прочитать этот документ только при подписке на The F # .NET Journal? :( - person Pedro Dusso; 26.06.2010
comment
Джон, я проверил ваше решение. Это работает, но таким образом он возвращает мне статическое значение листового узла, и я ищу весь узел, чтобы воспроизвести его. Возможно с некоторыми доработками. Все ответы здесь вдохновили меня написать собственное решение, которое я добавлю к своему вопросу, отредактировав его. - person Pedro Dusso; 26.06.2010