Minimax is algorithm commonly used by AI in two-player games to determine the best possible move given a current state of the game. It gets its name from the intuitive concept that a player wants to minimize his opponent’s score while maximizing his own score. The core of this algorithm essentially plays out all of the possible games until the game is over. Then the play that resulted in the best end game (minimize opponent’s score, maximize player’s score) is chosen. If you want to see the full code right away, head over to GitHub. Otherwise, read on and let’s see how this is implemented.
def play(state:GameState):(Int, Int) = {
val moveScores = {
for {
move <- state.availableMoves
} yield move -> minimax(state.makeMove(move))
}
val bestMove = moveScores.minBy(_._2)._1
bestMove
}
We start with a GameState which I have intentionally left out of this post. You are free to implement GameState however you see fit (although stay tuned for an actual game that uses this algorithm). We then iterate over all of the available moves in the game state and return a key->value pair of move->score. The best move is the one that minimizes the opponent’s score. So given the list of move->score pairs, we find the pair with the smallest score and return the move. Scala’s syntax for this last bit is pretty terse: moveScores.minBy(_._2)._1. The _. was confusing to me at first, but the underscore could be replaced by any identifier, such as “pair” or “moveToScoreTuple”. The use of the underscore is to imply that we do not particularly care to name the pair because we never need to refer to the pair by name.
If you recall, I said earlier that minimax plays out all possible games until the end. In practice, this would take far too long. Consider a game like Chess in which there are approximately 10120 possible games (more than the number of atoms in the universe). Playing out all of the games would be impractical. So we usually implement a “depth” concept in minimax which tells the algorithm how many moves it is allowed to play. When the depth is reached, the algorithm returns the score of that game state (even though the game is not necessarily over). We kickoff the search using the chosen depth:
val maxDepth = 3
private def minimax(state:GameState):Int = {
minimize(state, maxDepth)
}
private def minimize(state:GameState, depth:Int):Int = {
if(state.isTerminal || depth == 0) return state.hVal
var bestResult = Integer.MAX_VALUE
state.availableMoves.foreach(move => {
val newState = state.makeMove(move)
val bestChildResult = maximize(newState, depth - 1)
bestResult = math.min(bestResult, bestChildResult)
})
bestResult
}
Note that the minimax function returns an Int. This is score of the game state in which the algorithm terminated. To start the process we jump down into the minimize function.
Immediately we want to see if the game is over (state.isTerminal) or if the algorithm has reached the maximum number of moves (depth == 0). If either of those conditions are true we return the “heuristic value” (hVal) of that state, which is the score. If neither of those conditions are true, we continue as normal.
Remember at this point we already made one move (in the play() function), so we’re now evaluating the plays the opponent will make. Since we are trying to minimize the opponent’s score, the worst outcome for us is one in which the opponent scores +∞, which we represent by Integer.MAX_VALUE. We want to see if there is any move in which our opponent will score lower than +∞, so we loop over the available moves our opponent could make in this game state. Of course, our opponent is also trying to win, so the best play for the opponent is the one that maximizes his score! More on this in a moment, but that is the reason why we run val bestChildResult = maximize(newState, depth - 1). Finally we update the bestResult to be the smaller of the current bestResult and the bestChildResult. After checking all possibilities, we have minimized the score and return bestResult.
Now we need to see the other half of the algorithm.
private def maximize(state:GameState, depth:Int):Int = {
if(state.isTerminal || depth == 0) return state.hVal
var bestResult = Integer.MIN_VALUE
state.availableMoves.foreach(move => {
val newState = state.makeMove(move)
val bestChildResult = minimize(newState, depth - 1)
bestResult = math.max(bestResult, bestChildResult)
})
bestResult
}
No surprise that is looks very similar! All we’re doing is flipping a few things around. This time, the worst outcome is the one in which we score -∞. Additionally, we want to return the larger of the bestResult and bestChildResult because we are trying to maximize our score.
Looking at both sides of the algorithm, we can now see the flip-flop that occurs. The minimize function calls maximize and vice versa. This flip back and forth simulates the two players taking alternating turns. Each player wants to make the move that is best for him and worst for his opponent. To increase the speed of the algorithm, we limit the number of possible moves which is why each successive call is made with depth - 1.
Unfortunately, this is still pretty slow. In the next post we’ll see how we can save the algorithm some time by not evaluating games that have already been lost.
