如何在此F＃minimax中返回最佳的第一级？

Question

这个问题更多的是语义 - 算法数据结构问题，而不是f＃句法问题。我有一个最小算法。 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)))

这种修改使得好叶子的静态值升高。我需要返回最佳的第二级节点。希望有人可以帮助！佩德罗·杜斯索（Pedro Dusso）

编辑1

感谢所有答案，他们对我有很大帮助。对不起，没有说明这些内容太多。让我们进入一部分：

1）我像叶子一样匹配 LeafP(position, 0) 因为当我创建树时，我将默认值为0的叶子设置为其静态值。当我上升到静态值时，消除叶子并制作（分支前）具有（min或max）静态值的叶子，我认为我会阻止评估前分支叶子（因为它不会有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)

佩德罗·杜斯索（Pedro Dusso）

Answer 1

我不太了解您的样本的某些方面（例如，为什么只与其中的叶子匹配？），所以我将在下面进行一些更改。首先，让我们稍微概括一下树类型，以便它可以在叶子和分支中存储任何类型的数据：

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

另请参阅 可玩的演示.