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