Alpha-beta pruning
An optimisation of minimax that skips branches provably unable to affect the result — same answer, a fraction of the work.
The search carries two bounds: alpha, the best score you're already guaranteed, and beta, the best the opponent is already guaranteed. As soon as a branch turns out worse than an alternative already found, the rest of it needn't be examined; the opponent would never let you get there. The answer is exactly the same as full minimax.
Several groups hit on the idea independently in the 1950s, and Donald Knuth and Ronald Moore analysed it in 1975: with perfect move ordering it visits roughly the square root of the nodes, which in practice doubles the reachable depth. That's why chess engines put so much effort into trying the likeliest moves first, often with help from a transposition table. Deep Blue was built on the same principle.