minimax
In plain wordsA way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
A decision rule and search algorithm for two-player, zero-sum games of perfect information. The program expands a game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws. to some depth, scores leaf positions with an evaluation functionevaluation function, n.: In a game-playing program, a formula that looks at a board position and gives it a score saying how good it is, without playing the game out to the end. (or the exact result at the end of the game), and backs values up the tree: at nodes where it moves it takes the maximum of its children's values and at opponent nodes the minimum, so the root's value is the best outcome achievable against a perfect opponent. Full-width search to depth d costs on the order of b^d positions for branching factor b, so practical programs add alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep., iterative deepeningiterative deepening search, n.: A search strategy that explores one step deep, then starts over and explores two steps deep, then three, and so on. It repeats some work but needs very little memory and still finds the shortest answer. and move ordering; games with dice use expectiminimax, which averages over chance nodes. In decision theory, minimax more generally means choosing the option that minimizes the maximum possible loss.
A four-ply minimax search is enough to stop the program from blundering its queen.
Origin
John von Neumann proved the minimax theorem for two-person zero-sum games in 1928. Claude Shannon's 1950 paper 'Programming a Computer for Playing Chess' proposed depth-limited minimax with an evaluation function, the blueprint for chess programs up to Deep BlueDeep Blue, prop. n.: IBM's chess computer that beat world champion Garry Kasparov in 1997, the first time a machine defeated a reigning world champion in a match under standard tournament conditions..
Related
- alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep.
- game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
- evaluation functionevaluation function, n.: In a game-playing program, a formula that looks at a board position and gives it a score saying how good it is, without playing the game out to the end.
- Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.
- Deep BlueDeep Blue, prop. n.: IBM's chess computer that beat world champion Garry Kasparov in 1997, the first time a machine defeated a reigning world champion in a match under standard tournament conditions.
- self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples.
- Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.
Sources
- von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen 100, 295–320.
- Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine 41(314), 256–275.
Mentioned in
Arthur SamuelArthur Samuel, prop. n.: An American IBM engineer whose checkers program improved by playing against itself, and whose 1959 paper helped make 'machine learning' the name of a field., Claude ShannonClaude Shannon, prop. n.: An American engineer and mathematician who invented information theory, the mathematics of bits and communication, and wrote one of the first plans for a chess-playing computer., Deep BlueDeep Blue, prop. n.: IBM's chess computer that beat world champion Garry Kasparov in 1997, the first time a machine defeated a reigning world champion in a match under standard tournament conditions., depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch., game theorygame theory, n.: The mathematics of strategic decisions, where each player's best move depends on what the others do. It is used to study competition and cooperation among people, firms, nations and AI agents., game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws., John von NeumannJohn von Neumann, prop. n.: A Hungarian-American mathematician who shaped the design of modern computers, co-founded game theory, and is the first person known to have spoken of a coming technological 'singularity'., Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average., alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep., ChinookChinook, prop. n.: A checkers program from the University of Alberta that in 1994 became the first program crowned world champion in a contest against people, and in 2007 proved that perfect checkers always ends in a draw., counterfactual regret minimizationcounterfactual regret minimization, n.: A method for working out near-unbeatable strategies in games with hidden information, like poker, by repeatedly playing against itself and shifting each decision toward the moves it most regrets not making., evaluation functionevaluation function, n.: In a game-playing program, a formula that looks at a board position and gives it a score saying how good it is, without playing the game out to the end., MiniMax (company)MiniMax (company), prop. n.: A Shanghai artificial intelligence company, founded in 2021, that makes AI companion apps, the Hailuo video generator and large language models, several released openly., Nash equilibriumNash equilibrium, n.: A stable standoff in a game: each player's choice is already their best answer to what the others are doing, so nobody gains by changing course alone — though the result need not be good for anyone., Samuel's checkers programSamuel's checkers program, prop. n.: A 1950s IBM program by Arthur Samuel that learned to play checkers better than its author, partly by playing against itself. It was among the first programs to learn, and its 1959 paper popularized the phrase 'machine learning'.