Minimax and alpha-beta
Choosing a move in a two-player zero-sum game: game tree, evaluation function, limited depth, minimax back-up, alpha-beta pruning and the effect of move ordering.
- 22 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
Minimax algorithm: what is it?
Show the answer
An algorithm that picks the move assuming the opponent always replies in the way best for them: the maximum is backed up at the player's nodes and the minimum at the opponent's nodes.
A MAX root with three MIN nodes of leaves (3, 5), (2, 9) and (0, 7): the MIN nodes are worth 3, 2 and 0, the root is worth 3, and the first move is played.
The root is a MAX node with three MIN children, with leaves (4, 7, 6), (5, 1) and (8, 9, 2). Which move does minimax choose?
- The first, worth 4
- The third, because it contains the leaf 9
- The second, because its first leaf is 5
- The third, worth 8, its first leaf
Show the answer
The first, worth 4
Each MIN node takes its minimum: 4, 1 and 2. The MAX root takes the largest of these minima, 4, so the first move. Looking at the best leaf forgets that the opponent chooses.
Alpha-beta prunes most when the … are examined first; in the best case it evaluates only on the order of the … of the number of leaves minimax does.
Show the answer
Alpha-beta prunes most when the best moves are examined first; in the best case it evaluates only on the order of the square root of the number of leaves minimax does.
A good order sets good bounds early. In the best case, about b to the power d/2 leaves instead of b to the power d, which allows searching about twice as deep in the same time.
Alpha-beta pruning: what is it?
Show the answer
An improvement of minimax that stops examining a branch as soon as it can no longer change the root's value; the result is identical, with fewer leaves evaluated.
Two bounds are kept: alpha, the best payoff already guaranteed to MAX, and beta, the best already guaranteed to MIN. As soon as beta ≤ alpha, the rest of the branch is useless.