このf＃minimaxで最高の最初のレベルを返す方法は？

Question

この質問は、f＃stactically questionよりもセマンティックアルゴリズムデータと構造の質問です。 Minimaxアルゴリズムがあります。 Minimaxアルゴリズムは、開始位置から最高の次の動きを返す必要があります。これを行うには、次のすべての動きを計算し、次に次のネクストモーブが決定された深さまで、または動きがないまで移動します。このような木を構築します：

     P  
   /  \  
 a      b  
/ \  
c d

私はツリーを処理するための転倒データ構造体を持っています：

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

上の例の木では、 P と a ブランチです b, c と d 葉です。以下のコードは私の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

このコードは私に葉を返しています。たとえば c. 。再帰呼び出しを変更したとき

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

そして、この変更により、良い葉の静的値が上がります。最高の第2レベルのノードを返す必要があります。誰かが助けることができることを願っています！ペドロデュッソ

編集1

すべての答えをありがとう、彼らは私をとても助けてくれます。申し訳ありませんが、物事をあまり特定しませんでした。部分的に行こう：

1）私は葉のように一致しています LeafP(position, 0) なぜなら、ツリーを作成すると、デフォルト値が0の静的値としてリーフを設定するからです。静的値を上げて、葉を排除し、（分岐の前に）葉を（最小または最大）静的値で作るとき、私はこのようにして、元分岐葉の評価を防ぐと思いました（それは持っていなかったので0値）。

2）私の最大の問題は、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)

ペドロデュッソ

Answer 1

私はあなたのサンプルのいくつかの側面をよく理解していません（たとえば、なぜあなたはそれらに0が入っている葉と一致するのですか？）ので、以下にいくつかの変更を加えます。まず第一に、葉や枝にあらゆる種類のデータを保存できるように、ツリータイプを少し一般化しましょう。

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 

Answer 2

相互に再帰的な機能を使用できると思います。

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

この問題の解決策は、f＃.netジャーナル記事で説明されています ゲームプログラミング：TIC-TAC-TOE （2009年12月31日）と次のパターンを使用します。

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

を参照してください 再生可能なデモ.