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.