2

この質問は、F＃の構文上の質問というよりも、意味論的アルゴリズムのデータ構造に関する質問です。私はミニマックスアルゴリズムを持っています。ミニマックスアルゴリズムは、開始位置から次の最良の動きを返す必要があります。これを行うために、それはすべての次の動きを計算し、次に次の次の動きを決定された深さまで、またはそれ以上の動きがなくなるまで動かします。次のようなツリーを構築します。 

     P  
   /  \  
 a      b  
/ \  
c d

ツリーを処理するための休眠データ構造体があります。

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

上記の例のツリーではP、aはブランチと、bはリーフです。以下のコードは私のミニマックスアルゴリズムです：cd

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

すべての回答者に感謝します、彼らは私を大いに助けてくれます。申し訳ありませんが、あまり指定していませんでした。部分的に行きましょう：

LeafP(position, 0)1）ツリーを作成するときに、静的な値としてデフォルト値0を使用してリーフを設定したため、LeafPと一致しています。静的な値を上げて、リーフを削除し、（ブランチの前の）リーフを（最小または最大）静的な値で作成するときに、この方法で元のブランチリーフを評価できないようにすると思いました（ 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）

ペドロ・デュッソ

4

3 に答える 3

3

サンプルのいくつかの側面を完全には理解していません（たとえば、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
于 2010-06-25T16:58:57.033 に答える
1

相互再帰関数を使用できると思います。

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
于 2010-06-25T01:40:55.630 に答える
0

この問題の解決策は、F＃.NET Journalの記事「ゲームプログラミング：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

再生可能なデモも参照してください。

于 2010-06-25T18:32:05.570 に答える