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

Question

我的总结 objective：弄清楚在使用我认为不能成为尾递归的算法时如何使用连续传递样式来避免堆栈溢出。或者，找到一种使函数尾递归的方法。

详情： 我是 F#（和一般的函数式编程）的新手，我正在尝试使用 alpha-beta 修剪来实现 minimax 算法。这是一种算法，用于确定两人游戏的最佳可能着法。该算法的伪代码可以在这里找到：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 是尾递归的，但这些方法在分配 newAlpha 和 [=16= 时调用 minimax ] 所以当我用大深度调用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

正如你在"basic examples"中看到的那样，一般的想法是带一个额外的参数（"continuation"，通常表示为k），这是一个函数，并且每次你 return 一个值时，将该值传递给延续。因此，例如，以这种方式修改 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)

然后调用站点需要 "turned inside out"，可以这么说，而不是像这样：

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 的 return 值，但现在 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
    )

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

所以让我们先做takeMax。同样的想法：添加一个额外的参数 k 并且每次我们将 "return" 一个值时，将它传递给 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

等等，刚刚发生了什么？我只是说每次我 return 一个值我应该把它传递给 k ，但在这里我没有这样做。相反，我将 k 本身传递给 takeMax。嗯？

嗯，"instead of returning pass to k" 的规则只是方法的第一部分。第二部分是-"on every recursive call, pass k down the chain"。这样，原始的 top-level k 将沿着整个递归调用链传播，并最终由决定停止递归的任何函数调用。

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

虽然有一个很好的对称性：如果算法确实是 tail-recursive，您将能够将原始的 top-level 延续传递到调用链中，而无需分配任何中间 lambda，等等你不需要任何堆内存。

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

Attempting to use continuation passing style to avoid stack overflow with minimax algorithm

stack-overflow

f#

functional-programming

minimax

continuation-passing