The Minimax algorithm is used in two-player, turn-based, zero-sum games (like Tic-Tac-Toe, Chess, or Checkers). It helps AI choose the best move assuming the opponent also plays optimally.
It aims to maximize the AI’s gain while minimizing the opponent’s gain — hence the name minimax.
| Term | Explanation |
|---|---|
| Maximizer | The AI player, trying to get the highest score |
| Minimizer | The opponent, trying to minimize the AI’s score |
| Utility Value | Numeric score assigned to terminal states (win = +1, lose = –1, draw = 0) |
| Game Tree | A tree of all possible moves and their outcomes |
| Zero-sum Game | One player’s gain is another player’s loss |
Generate the game tree from the current state.
Evaluate terminal states using a utility function.
Propagate values up the tree:
Choose the move that leads to the best value at the root (AI's turn).
[AI]
Max
/ \
Min Min
/ \ / \
+1 0 -1 +1
At Min nodes: pick the minimum child value → First Min: min(+1, 0) = 0 → Second Min: min(–1, +1) = –1
At Max (AI): pick the maximum of 0 and –1 → Best move = 0
Time: O(b^m)
Space: O(m) for depth-first implementation
Minimax can be optimized with Alpha-Beta pruning, which:
| Concept | Meaning |
|---|---|
| Minimax | Algorithm for two-player adversarial games |
| Maximizer | AI’s turn – aims to maximize utility |
| Minimizer | Opponent’s turn – aims to minimize AI’s score |
| Game Tree | All possible future game states |
| Use | Games like Tic-Tac-Toe, Chess, etc. |
| Optimized by | Alpha-Beta Pruning |
Open this section to load past papers