这个问题更像是一个语义-算法-数据结构问题,而不是一个 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)
佩德罗·杜索