Glossary · Phase 7 · Software engineering
Game tree
Every position a game can reach, branching at each move. Game programs look ahead by searching it.
From any position you can list every move, then every reply to each move, and so on until each game ends. That branching picture is the game tree. A function that walks it is naturally recursive: the result for a position is built from the results for the positions after each move.
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
- 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.
- exhaustive test: A test that tries every possible input, so passing proves the claim instead of just making it likely.
- 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.