The Minimax algorithm determines the best score in a game after players get to move a certain number of times. Minimax is only applicable in 2-player games, where the gain of player A is exactly the loss of player B.
Implementation
maxNode(int depth) {
// Leaf nodes are evaluated
if (depth == 0)
return evaluation()
// Maximize score for all possible moves
score = 0
bestScore = INT_MIN
for (move : generateMoves()) {
playMove(move)
score = minNode(depth - 1)
takebackMove(move)
bestScore = max(bestScore, score)
}
return bestScore
}
minNode(depth) {
// Leaf nodes are evaluated
if (depth == 0)
return evaluation()
// Minimize score for all possible moves
score = 0
bestScore = INT_MAX
for (move : generateMoves()) {
playMove(move)
score = maxNode(depth - 1)
takebackMove(move)
bestScore = min(bestScore, score)
}
return bestScore
}
Description
The algorithm is split into two functions, max
and min
, which are called recursivly from each other. Both functions take turns at each depth like players take turns in a game. By playing all possible moves for each position, a game tree is generated. If depth is 0, the position is then evaluated according to side and the score is propagated back. Now, each depth in the tree represents the possible outcomes for player A or player B.
For all nodes in the tree, the player to turn chooses the move that scores best for him: The maximizing player decides to take the highest score while the minimizing player takes the lowest score. Therefore, the best outcome at each node is propagated back to the parent node. The root node receives the bets score, if both players always play their best moves.
Usage
The Minimax Algorithm is used in a variety of 2-player games like Chess, Go or Shogi. It acts as artifial intelligence in order to play the most promising moves and in the game. However, most implementations rely on a modified version called Negamax to avoid redundant code.
The initial call to start a recursive game tree search depends on the player to move. The minimizing player calls min(depth)
while the maximizing player finds his best score with max(depth)
.
Complexity
Time
For a branching factor and depth :
Space
For maximum number of child nodes for all nodes and depth :