Last time, we built a naive minimax algorithm in Scala. While it was effective, it was unfortunately very slow. To increase the performance of the algorithm, we’ll implement a common variant of minimax with what is called “alpha-beta pruning”. Again, if you want to see the full code right away, head over to GitHub.
Recall that the minimax algorithm works by playing out all possible games given a starting game state. During the course of the analysis, undoubtably paths will be encountered that have no hope of resulting in victory. Alpha-beta pruning removes those as possible paths and stops searching any deeper down those paths. This is accomplished by applying a check for each iteration to see if the score returned is worse than the best score encountered.
private def minimax(state:GameState):Int = {
minimize(state, maxDepth, Integer.MIN_VALUE, Integer.MAX_VALUE)
}
private def minimize(state:GameState, depth:Int, alpha:Int, beta:Int):Int = {
if(state.isTerminal || depth == 0) return state.hVal
var newBeta = beta
state.availableMoves.foreach(move => {
val newState = state.makeMove(move)
newBeta = math.min(beta, maximize(newState, depth - 1, alpha, newBeta))
if (alpha >= newBeta) return alpha
})
newBeta
}
You should see a lot similarity here. The big difference is that now we instead of just accepting the best result as the result of maximize function, β is now the smaller of the previous β value or the result of maximize. Next comes the critical check. If α ≥ β we immediately exit the function and return α as the best possible score.
The maximize function is of course quite similar, except this time we return β if no better scores are are found.
private def maximize(state:GameState, depth:Int, alpha:Int, beta:Int):Int = {
if(state.isTerminal || depth == 0) return state.hVal
var newAlpha = alpha
state.availableMoves.foreach(move => {
val newState = state.makeMove(move)
newAlpha = math.max(newAlpha, minimize(newState, depth - 1, newAlpha, beta))
if (newAlpha >= beta) return beta
})
newAlpha
}
When I ran this code in the same game as the naive algorithm, the processing time was an order of magnitude faster.