extending Minimax with Alpha-Beta-pruning

Last time we discussed the Minimax-algorithm and I promised to extend it with Alpha-Beta-pruning. Today I want to fulfill this promise.

But before starting for real I want to talk a bit of why you want to do this – the answer is simple: It’s a lot faster …

Let’s compare some runtimes first

I will use the implementation for the Connect4-game for this (code you don’t have seen yet) – but I wanted some real world example (or as near to it as possible). So I will let both algorithms (Minimax without and with Alpha-Beta-pruning) run against each other on the task of finding the best turn on an empty Connect4-board with search depth 3 and then 4. First for 100 iterations for depth 3 and then (because the Minimax without just takes to long for this) with 20 iterations for depth 4.

I will run this on my machine without any optimizations (indeed I will use debug mode as it don’t matter that much in this case) in a little console-app.

Here is the code running the tests:

    let measureRuntime times action =
        let row = System.Console.CursorTop
        let start = System.DateTime.Now
        let setCursor() = System.Console.CursorTop <- row
                          System.Console.CursorLeft <- 0
        let print = printfn "iteration %d ..." >> setCursor
        [| 1..times |] |> Array.iter (print >> action)
        let timeSpent = System.DateTime.Now.Subtract(start)
        setCursor()
        printfn "%d iterations took %.0fsec" times timeSpent.TotalSeconds

    let searchInitialGame depth algorithm =
        let game = GameSearchSpace.Root (Board.initialize 8 6)
        let calculate() = (game, LayerRateType.Max) |> algorithm (depth, Board.searchSpace 8 6) |> ignore
        calculate

    let runMeasurements() =
        let measureRuns runs depth = searchInitialGame depth >> measureRuntime runs

        printfn "measuring 100 runs of Minimax depth 3..."
        measureRuns 100 3 MiniMaxAlgorithm.Search

        printfn "measuring 100 runs of AlphaBeta depth 3..."
        measureRuns 100 3 AlphaBetaAlgorithm.Search

        printfn "measuring 20 runs of Minimax depth 4..."
        measureRuns 20 4 MiniMaxAlgorithm.Search

        printfn "measuring 20 runs of AlphaBeta depth 4..."
        measureRuns 20 4 AlphaBetaAlgorithm.Search

I think it’s straight forward so that I don’t have to go into it (leave a comment if you have any questions). On my machine these are the results:

measuring 100 runs of Minimax depth 3...
100 iterations took 37sec
measuring 100 runs of AlphaBeta depth 3...
100 iterations took 12sec
measuring 20 runs of Minimax depth 4...
20 iterations took 59sec
measuring 20 runs of AlphaBeta depth 4...
20 iterations took 9sec

I think it’s worth to implement this – don’t you think?

Basic Idea

The basic idea of this “pruning” is simple. If you are inside MIN-Layer and look at a subtree  and the best child-node you found so far (in this case with the smallest rating Min) you know that no matter what is still to come the end value of this subtree won’t be larger than Min. Now the layer just before this is a MAX layer and it too will have a best value so far (this we will call Beta) so your current subtree can only improve the MAX layer if your final result will be larger then Beta. Well what if Min you found so far is already smaller or equal? Well you can stop with this subtree because no matter what you will find it just won’t improve on the value of the layer above you – you can prune it.

In case you look at a MAX layer it’s just the same – only you will have a biggest value so far and if this is already larger than the best value of the MIN-layer above (his value will be called Alpha) you can stop as well to the same reasoning as we just discussed.

Look at this situation:

AlphaBeta

Suppose you are at the subtree on the right and have rated the first child node with 2 – the best child-node of the first layer (green Node) has value 3 (so Beta = 3) and so we don’t have to consider the two child nodes marked with an “x” anymore – we can prune them.

As we can to this on all levels this will save us a lot of time in the end – as you can see from the performance tests.

Please note that you can make this even more effective if you have some domain-knowledge on where you have to look for good nodes. If you choose the order of child nodes carefully you can save even more time if you see the good nodes right away. in Case of the Connect4 game those would surely be the columns in the middle but I did not opt to go down that road.

Implementation

The implementation is a straight-forward extension of the algorithm we saw in the last article. We just pass down the alpha/beta values, initialize them to extreme values and prune in the right places – I marked the changed lines:

/// Implements a search-function using Minimax with AlphaBeta-pruning
module AlphaBetaAlgorithm =

    /// Private implementation of the algorithm
    let private searchMinMax (depth : int) (space : SearchSpace<'a>) (root : 'a, lrt : LayerRateType) : ('a * float) option =

        /// the method used for a min-Layer
        let rec findMin d (alpha, beta) (node : 'a) =
            // find all children of current node
            let children = space.CreateChildStates node
            if List.isEmpty children then None         // if there are no children then we found Nothing
            elif d = depth                             // else if we reached max. search-depth
            then                                       // then rate current state and return it
                (node, space.RateState node) |> Some
            else                                       // else recursivly find the best child
                let rec findBestChild (best : ('a*float) option) cs =
                    match cs with
                    | []     -> best
                    | c::cs' -> let minV = match best with
                                              | Some (_, minV) -> minV
                                              | None           -> System.Double.MaxValue
                                // recursive decent into the other layer-type
                                let recur = findMax (d+1) (minV, beta) c
                                // if there were no other children, then rate the current node
                                let cVal = match recur with
                                           | Some (_, v)       -> v
                                           | None              -> space.RateState c
                                // this is the alpha-beta-pruning part - if this is allready worse than
                                // what was found in layer above we can stop here
                                if cVal <= beta  then Some (c, cVal)
                                // else check if this child is better than the current-best one
                                elif cVal < minV then findBestChild (Some (c, cVal)) cs'
                                else                  findBestChild best cs'
                findBestChild None children

        /// the method used for a max-layer - similar to findMin
        and findMax d (alpha, beta) (node : 'a) =
            let children = space.CreateChildStates node
            if List.isEmpty children then None
            elif d = depth
            then
                (node, space.RateState node) |> Some
            else
                let rec findBestChild (best : ('a*float) option) cs =
                    match cs with
                    | []     -> best
                    | c::cs' -> let maxV = match best with
                                              | Some (_, v)    -> v
                                              | None           -> System.Double.MinValue
                                let recur = findMin (d+1) (alpha, maxV) c
                                let cVal = match recur with
                                           | Some (_, v)       -> v
                                           | None              -> space.RateState c
                                if cVal >= alpha then Some (c, cVal)
                                elif cVal > maxV then findBestChild (Some (c, cVal)) cs'
                                else                  findBestChild best cs'
                findBestChild None children

        // start the algorithm with the right layertype
        match lrt with
        | LayerRateType.Max -> findMax 0 (System.Double.MaxValue, System.Double.MinValue) root
        | LayerRateType.Min -> findMin 0 (System.Double.MaxValue, System.Double.MinValue) root

    /// the public search-function - see definition in AlgorithmDefinitions.fs
    let Search : Search<_> = (fun (searchDepth, space) -> searchMinMax searchDepth space)

That’s it for today – next time we will look into the representation of the game in F#.