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

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

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

As you have undoubtedly seen in the "basic examples", the general idea is to take one extra parameter (the "continuation", usually denoted k), which is a function, and every time you would return a value, pass that value to the continuation instead. So, for example, to modify minimax this way, we'd get:

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)

And then the call site needs to be "turned inside out", so to speak, so instead of something like this:

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

we would write something like this:

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

See? a used to be a return value of minimax, but now a is the parameter of the continuation that is passed to minimax. The runtime mechanics is that, once minimax has finished running, it would call this continuation, and its result value would show up there as parameter a.

So, to apply this to your real code, we'd get this:

| 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
    )

Ok, this is all well and good, but this is only half the job: we have rewritten minimax in CPS, but takeMin and takeMax are still recursive. Not good.

So let's do takeMax first. Same idea: add an extra parameter k and every time we would "return" a value, pass it to k instead:

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
        )

And now, of course, I have to modify the call site correspondingly:

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

Wait, what just happened? I just said that every time I return a value I should pass it to k instead, but here I'm not doing it. Instead, I'm passing k itself to takeMax. Huh?

Well, the rule that "instead of returning pass to k" is only the first part of the approach. The second part is - "on every recursive call, pass k down the chain". This way, the original top-level k would travel down the whole recursive chain of calls, and be ultimately called by whatever function decides to stop the recursion.

Keep in mind that, although CPS helps with stack overflow, it does not free you from memory limits in general. All those intermediate values don't go on the stack anymore, but they have to go somewhere. In this case, every time we construct that lambda fun minimaxResult -> ..., that's a heap allocation. So all your intermediate values go on the heap.

There is a nice symmetry though: if the algorithm was truly tail-recursive, you'd be able to pass the original top-level continuation down the call chain without allocating any intermediate lambdas, and so you wouldn't require any heap memory.

Recommended topics

Hot tags