Minimax

Minimax is a decision rule that selects an action whose worst-case outcome is better than the worst-case outcomes of alternatives. In two-player games, it assumes an opponent who chooses the strongest response.

Game tree: A tree-shaped representation of possible states and actions in a sequential decision problem. Minimax evaluates branches of a game tree from terminal outcomes back to the current position.
Decision theory: The study of how agents choose among actions under certainty, risk, or uncertainty. Minimax is one rule within the broader study of rational choice.
Tic-tac-toe: A two-player game in which players place marks on a three-by-three grid to form a line. Its small game tree makes complete minimax search practical.
Maximin: A rule that chooses the action with the best worst-case payoff for the decision-maker. In two-player zero-sum games, maximin and minimax identify the same value from opposing viewpoints.
Utility: A numerical measure of the value an outcome provides to a decision-maker. Utility scores provide the outcomes that minimax compares.
Adversarial search: Search through possible actions when another agent’s choices affect outcomes. Minimax is a foundational method for searching against an opponent.
Chess: A two-player strategy game played on an eight-by-eight board with distinct pieces and movement rules. Chess programs use minimax-style search to compare candidate moves.
Expectimax: A game-tree search method that uses expected values at chance events instead of assuming an adversarial choice. Expectimax models probabilistic outcomes where minimax treats the opposing move as worst-case.
Zero-sum game: A game in which one player’s gain is exactly another player’s loss. In two-player zero-sum games, maximizing one player’s value is equivalent to minimizing the other’s.
Maximum: The greatest value in a specified set of values. A maximizing player selects the largest value among the opponent’s possible outcomes.

Linked from 14 pages