Minimax chooses a move in a two-player zero-sum game by maximizing the current player's outcome while assuming the opponent chooses the reply that minimizes it. The search explores future positions until it can classify them as wins, losses, or draws. section 8.4
A practical minimax implementation follows this cycle:
- Represent the position, whose turn it is, and the last move; generate a new immutable position for each legal move. section 8.4
- Stop recursion at a win or draw, returning a score such as 1 for the original player's win, -1 for a loss, and 0 for a draw. section 8.4
- At maximizing turns, keep the highest child score; at minimizing turns, keep the lowest child score. section 8.4
- Evaluate every legal first move and return the move with the best resulting score. section 8.4
Tic-tac-toe
For a position with two moves left, minimax compares the possible continuations and selects the move that preserves the best outcome against the opponent's response. Small test positions can check an immediate win, a required block, and a win that takes two moves. section 8.4
// Find the best possible outcome for originalPlayer
func minimax(_ board: Board, maximizing: Bool, originalPlayer: Piece)
-> Int {
// Base case -- evaluate the position if it is a win or a draw
if board.isWin && originalPlayer == board.turn.opposite { return 1 }
// win
else if board.isWin && originalPlayer != board.turn.opposite
{ return -1 } // loss
else if board.isDraw { return 0 } // draw
// Recursive case -- maximize your gains or minimize the opponent's gains
if maximizing {
var bestEval = Int.min
for move in board.legalMoves { // find the move with the highest
evaluation
let result = minimax(board.move(move), maximizing: false,
originalPlayer: originalPlayer)
bestEval = max(result, bestEval)
}
return bestEval
} else { // minimizing
var worstEval = Int.max
for move in board.legalMoves {
let result = minimax(board.move(move), maximizing: true,
originalPlayer: originalPlayer)
worstEval = min(result, worstEval)
}
return worstEval
}
}
The recursive Swift function makes the terminal cases and the alternating maximize/minimize branches explicit. section 8.4
Minimax works well for many traditional strategy games, including chess, checkers, Connect Four, and Scrabble. Larger search spaces reduce its effectiveness; alpha-beta pruning extends the approach, while Go may require other techniques. section 8.5
