f# - 尝试使用连续传递样式来避免使用 minimax 算法的堆栈溢出

Question

我的目标摘要:弄清楚在使用我认为不能进行尾递归的算法时，如何使用连续传递样式来避免堆栈溢出。或者，找到一种方法使函数尾递归。

详情:
我是 F# 的新手(以及一般的函数式编程)，我正在尝试使用 alpha-beta 修剪来实现极大极小算法。这是一种用于确定两人游戏的最佳可能走法的算法。该算法的伪代码可以在这里找到:https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

这是我发现对理解算法流程有​​用的资源:http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/

我的实现中的一个不同之处在于，我正在开发的游戏的玩家并不总是交替进行。出于这个原因，我从函数中删除了一个参数。我的实现如下:

let rec minimax node depth alpha beta =
    if depth = 0 || nodeIsTerminal node then
        heuristicValue node
    else
        match node.PlayerToMakeNextChoice with
        | PlayerOneMakesNextChoice ->
            takeMax (getChildren node) depth alpha beta    
        | PlayerTwoMakesNextChoice ->
            takeMin (getChildren node) depth alpha beta
and takeMax children depth alpha beta =      
    match children with
    | [] -> alpha
    | firstChild :: remainingChildren ->
        let newAlpha = [alpha; minimax firstChild (depth - 1) alpha beta] |> List.max

        if beta < newAlpha then newAlpha
        else takeMax remainingChildren depth newAlpha beta
and takeMin children depth alpha beta =      
    match children with
    | [] -> beta
    | firstChild :: remainingChildren ->
        let newBeta = [beta; minimax firstChild (depth - 1) alpha beta] |> List.min

        if newBeta < alpha then newBeta
        else takeMax remainingChildren depth alpha newBeta

我遇到的问题是，虽然 takeMax和 takeMin是尾递归的，这些方法调用 minimax分配时 newAlpha和 newBeta所以当我调用 minimax时仍然有可能产生堆栈溢出具有较大的深度。我做了一些研究，发现当函数不能成为尾递归时，使用连续传递风格是一种使用堆而不是堆栈的潜在方式(我相信经过数小时的尝试后，这不能)。虽然我可以理解一些非常基本的例子，但我无法理解如何将这个概念应用于这种情况；如果有人能帮助我完成它，我将不胜感激。

编辑 1:我对解决方案的最佳理解

let minimax node depth alpha beta =
    let rec recurse node depth alpha beta k =
        if depth = 0 || nodeIsTerminal node then
            k (heuristicValue node)
        else
            match node.PlayerToMakeNextChoice with
            | PlayerOneMakesNextChoice ->
                takeMax (getChildren node) depth alpha beta k
            | PlayerTwoMakesNextChoice ->
                takeMin (getChildren node) depth alpha beta k
    and takeMax children depth alpha beta k =      
        match children with
        | [] -> k alpha
        | firstChild :: remainingChildren ->
            let continuation = fun minimaxResult ->
                let newAlpha = [alpha; minimaxResult] |> List.max

                if beta < newAlpha then k newAlpha
                else takeMax remainingChildren depth newAlpha beta k

            recurse firstChild (depth - 1) alpha beta continuation
    and takeMin children depth alpha beta k =      
        match children with
        | [] -> k beta
        | firstChild :: remainingChildren ->
            let continuation = fun minimaxResult ->
                let newBeta = [beta; minimaxResult] |> List.min

                if newBeta < alpha then k newBeta
                else takeMax remainingChildren depth alpha newBeta k

            recurse firstChild (depth - 1) alpha beta continuation
    recurse node depth alpha beta id

Answer 1

正如您在“基本示例”中无疑看到的那样，总体思路是采用一个额外的参数(“延续”，通常表示为 k )，它是一个函数，并且每次您要返回一个值时，传递该参数取而代之的是延续的值(value)。因此，例如，要修改 minimax这样，我们会得到:

let rec minimax node depth alpha beta k =
    if depth = 0 || nodeIsTerminal node then
        k (heuristicValue node)
    else
        match node.PlayerToMakeNextChoice with
        | PlayerOneMakesNextChoice ->
            k (takeMax (getChildren node) depth alpha beta)
        | PlayerTwoMakesNextChoice ->
            k (takeMin (getChildren node) depth alpha beta)

然后调用站点需要“由内而外”，可以这么说，而不是像这样:

let a = minimax ...
let b = f a
let c = g b
c

我们会这样写:

minimax ... (fun a ->
   let b = f a
   let c = g b
   c
)

看？ a曾经是 minimax的返回值，但现在 a是传递给 minimax 的延续的参数.运行时机制是，一旦 minimax已完成运行，它将调用此延续，其结果值将显示为参数 a .

因此，要将其应用于您的真实代码，我们将得到:

| firstChild :: remainingChildren ->
    minimax firstChild (depth - 1) alpha beta (fun minimaxResult ->
        let newAlpha = [alpha; minimaxResult] |> List.max

        if beta < newAlpha then newAlpha
        else takeMax remainingChildren depth newAlpha beta
    )

好的，这一切都很好，但这只是工作的一半:我们已经重写了 minimax在 CPS 中，但 takeMin和 takeMax仍然是递归的。不好。

所以让我们做 takeMax第一的。相同的想法:添加一个额外的参数 k每次我们“返回”一个值时，将它传递给 k反而:

and takeMax children depth alpha beta k =      
    match children with
    | [] -> k alpha
    | firstChild :: remainingChildren ->
        minimax firstChild (depth - 1) alpha beta (fun minimaxResult ->
            let newAlpha = [alpha; minimaxResult] |> List.max

            if beta < newAlpha then k newAlpha
            else takeMax remainingChildren depth newAlpha beta k
        )

现在，当然，我必须相应地修改调用站点:

let minimax ... k =
    ...
    match node.PlayerToMakeNextChoice with
    | PlayerOneMakesNextChoice ->
        takeMax (getChildren node) depth alpha beta k

等等，刚刚发生了什么？我只是说每次我返回一个值时我应该把它传递给 k相反，但在这里我不这样做。相反，我正在通过 k自己到 takeMax .嗯？

好吧，“而不是返回传递给 k”的规则只是该方法的第一部分。第二部分是 - “在每次递归调用时，将 k 向下传递”。这样，原来的顶级 k将沿着整个递归调用链向下传播，并最终被决定停止递归的任何函数调用。

请记住，尽管 CPS 有助于解决堆栈溢出，但它通常不会使您摆脱内存限制。所有这些中间值不再进入堆栈，但它们必须去某个地方。在这种情况下，每次我们构造 lambda fun minimaxResult -> ... ，这是一个堆分配。所以你所有的中间值都在堆上。

但是有一个很好的对称性:如果算法真的是尾递归的，您将能够将原始顶级延续传递到调用链中，而无需分配任何中间 lambda，因此您不需要任何堆内存。