Alpha-beta pruning
A speed-up for minimax that skips moves that can't change the decision. It gives the same answer while looking at far fewer positions.
Chess has more possible positions than there are atoms in the observable universe, so a chess program can't search to the end. It searches a few moves ahead, scores the positions it reaches with an evaluation function (material, mobility, king safety), and uses alpha-beta pruning to skip branches that can't change the decision. Programs for Go went further with Monte Carlo tree search and neural networks that learn the evaluation. The skeleton you're building is the same in all of them.
Try it now
Scores flow up the tree: each player takes the best option for themselves.
Learn it properly
Project: an unbeatable game opponent · Game state and rules, minimax with a cache, and an exhaustive test that proves it never loses. About 45 minutes.
Other terms from the same lesson
- exhaustive test: A test that tries every possible input, so passing proves the claim instead of just making it likely.
- game tree: Every position a game can reach, branching at each move. Game programs look ahead by searching it.
- minimax: Choosing a move by assuming each player always picks what's best for them, and scoring each position by that perfect play.
- negamax: A shorter way to write minimax: each player maximizes their own score, and a score changes sign as it passes to the other player.
Never trained an AI?
Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account.