alpha–beta pruning
In plain wordsA 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.
An optimization of minimaxminimax, n.: A 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. search that reaches exactly the same decision while leaving unexamined every part of the tree whose value could not alter it. It passes two bounds down the 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.: alpha, the value the maximizing player is already guaranteed, and beta, the value the minimizing player is already guaranteed. As soon as a node's value is known to fall outside the window between them — for instance, because one opposing reply already makes the move inferior to an alternative — its remaining children are pruned. With perfect move ordering it examines about b^(d/2) positions instead of b^d, effectively doubling the reachable depth; with random ordering the savings are smaller, so iterative deepening, transposition tables and killer-move heuristics are used to order moves well. It was the core of chess programs from the 1960s through 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., and Stockfish still searches with it.
Origin
Credit is disputed: John McCarthy recalled proposing the idea around 1956; Allen Newell, Cliff Shaw and Herbert Simon used an approximate form in their 1958 chess program; Timothy Hart and Daniel Edwards described it in an MIT AI memo in 1961; and Alexander Brudno described it independently in the Soviet Union in 1963. Donald Knuth and Ronald Moore published the first full analysis in 1975.
Related
- minimaxminimax, n.: A 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.
- 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.
- iterative deepening searchiterative 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.
- 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.
- 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
- Knuth, D. E. & Moore, R. W. (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence 6(4), 293–326.
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., combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers., 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., Garry KasparovGarry Kasparov, prop. n.: A Russian chess world champion whose 1997 loss to IBM's Deep Blue computer became the symbol of machines overtaking people, and who later championed humans and computers working together., minimaxminimax, n.: A 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., 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., pruningpruning, n.: Cutting away the parts of an AI model that contribute least, as a gardener trims branches, so the model becomes smaller or faster while still working nearly as well., 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., iterative deepening searchiterative 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.