a day ago
- The minimax algorithm is used for turn-based games where each player assumes the opponent will make optimal moves to minimize their loss and maximize their gain.
- It builds a look-ahead tree of possible board positions, with leaf nodes scored as win (+∞), loss (-∞), or draw (0) for the current player.
- Values are propagated upward: maximizing for the current player's turn, minimizing for the opponent's turn, until the root selects the best move.
- A recursive pseudocode demonstrates the algorithm, including tracking the best move and handling depth limits with heuristic evaluation when the tree cannot be fully explored.
- For complex games like chess, heuristic functions evaluate board positions (e.g., control of center) because full exploration is impossible.
- Techniques like alpha-beta pruning reduce the tree size, and the negamax variant simplifies code for zero-sum games.