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:
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#.