2

这个问题更像是一个语义-算法-数据结构问题,而不是一个 F# 句法问题。我有一个 Minimax 算法。极小极大算法应该从起始位置返回最佳下一步移动。为此,它计算所有下一步移动,然后计算下一个下一步移动,直到确定的深度或直到没有更多移动。它像这样构建一棵树:

     P  
   /  \  
 a      b  
/ \  
c d

我有休闲数据结构来处理树:

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

在上面的示例树中,Pa是分支bcd是叶子。下面的代码是我的极小极大算法:

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

佩德罗·杜索

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 期刊文章游戏编程:井字游戏(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 回答