This lesson introduces minimax and maximin as ways to make decisions when another player's actions are uncertain. The central idea is to consider the worst outcome each action could produce, then choose a strategy that handles that worst case well.
Minimax is a decision rule that minimizes the possible loss in a worst-case scenario. When focusing on gains, the related rule is maximin: maximize the minimum payoff you can guarantee. These rules are useful when a decision-maker does not know what others will do or does not want to rely on probabilities.
All flashcards
What is maximin?
A decision rule that selects the action with the highest minimum payoff, maximizing what a player can guarantee in the worst case.
What is minimax in strategic analysis?
A rule that takes the minimum, over opponents’ actions, of the player’s maximum payoff for each such action.
What does a−i represent?
The combined actions of all players other than player i.
How do you find a row player’s maximin move in a payoff table?
Find the lowest row-player payoff in each row, then choose the row whose lowest payoff is greatest.
How are maximin and minimax values related?
A player’s maximin value is at most their minimax value; the values may be equal or different.
Quiz questions
What defines a two-player zero-sum game?Answer: The players’ payoffs sum to zero for every outcome.
What does the minimax theorem guarantee for a finite two-player zero-sum game?Answer: An equilibrium value and strategies that let each player guarantee their equilibrium payoff.
How does a minimizing node evaluate its children in minimax search?Answer: It returns the smallest value among its children.
What is the effect of alpha-beta pruning when used with correct bounds and the same search depth?Answer: It skips branches that cannot affect the final minimax result.
What does a minimax estimator minimize in statistical decision theory?Answer: Its largest risk over the possible parameter values.
Based on the Wikipedia article Minimax, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.