DataTerminology.comNEW
Also known as: Minimax Algorithm
A decision rule minimizing possible loss in worst-case scenarios.
DESCRIPTION
Minimax is an adversarial search strategy that chooses moves to maximize the minimum utility achievable, assuming optimal opponent play. It explores a game tree of alternating max and min layers. Heuristic evaluations approximate leaf utilities when full search is infeasible. Alpha-beta pruning reduces explored nodes without changing the minimax result. Minimax underpins classic board game AIs and remains a baseline for evaluation.
ALTERNATIVE DEFINITIONS
Stanford University
Minimax chooses the action that maximizes the minimum utility that can be achieved, under the assumption that the opponent plays optimally.
Formalizes adversarial decision-making under optimal opponent assumptions.
UC Berkeley
In minimax, max chooses the highest value action, while min chooses the lowest; the value of a state is defined by optimal play from both sides.
Emphasizes alternating max/min layers and optimal play definition.
RELATED TERMS
Game Tree Alpha-Beta Pruning Heuristic Evaluation Zero-Sum Game Reward Function Adversarial Search Depth-Limited Search Transposition Table
COMPETING TERMS
Expectimax Monte Carlo Tree Search
RELATIONS
- Derivations: Alpha-Beta Pruning
KNOWLEDGE AREAS
TARGET AUDIENCE
AI Engineer Data Scientist Software Developer
EXTERNAL SOURCES
- Wikipedia - Minimax
- MIT OpenCourseWare - Lecture on game search
- Chess Programming Wiki - Minimax in computer chess
TOP QUESTIONS
When should Minimax be used?
Use minimax in deterministic, zero-sum, perfect-information games like chess or checkers. It models rational, adversarial opponents.
Category: Requirements
How does Minimax scale with search depth?
Exponential growth in nodes makes deep searches expensive. Pruning and heuristics are essential for tractability.
Category: Risks
How does Alpha-Beta Pruning relate to Minimax?
Alpha-beta cuts branches that cannot influence the final decision, preserving the minimax result while reducing computation.
Category: Example
What is the role of heuristics in Minimax?
Heuristic evaluations approximate utility at nonterminal nodes, enabling depth-limited search with reasonable decisions.
Category: Requirements
Is Minimax still relevant with modern AI?
Yes, as a baseline, for small games, and in hybrid systems. It provides interpretable decision processes.
Category: Relevancy
How does Minimax compare to Monte Carlo Tree Search?
Minimax relies on deterministic evaluation; MCTS samples and balances exploration/exploitation, often outperforming in large stochastic spaces.
Category: Alternatives
What is a common mistake with Minimax implementations?
Using inconsistent heuristics or ignoring transposition tables, leading to redundant computation and suboptimal performance.
Category: Mistakes
Can Minimax handle uncertainty?
Expectimax and stochastic variants extend minimax to probabilistic environments by modeling chance nodes.
Category: Topic
What is the biggest misunderstanding about Minimax?
That it requires full tree search; in practice, depth limits and heuristics are standard and effective.
Category: Misunderstanding