Minimax
Choosing a move by assuming each player always picks what's best for them, and scoring each position by that perfect play.
Give every finished game a score from X's point of view: +1 if X won, -1 if O won, 0 for a draw. Now work backward. On X's turn, X picks the move with the highest score; on O's turn, O picks the lowest. Each player assumes the other plays perfectly, so the score of a position is the result of perfect play from there. That rule is minimax.
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.
- game tree: Every position a game can reach, branching at each move. Game programs look ahead by searching it.
- 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.