Era 11 / 15 · Game-Playing Milestones 1997 & 2016

Beating the Champions

Search plus evaluation beat the best humans — chess, then Go.

Beat 1 · Concrete

Looking Ahead

From one position, the engine fans out candidate moves and looks several plies ahead.

Look-ahead search tree From a board position, lines branch out to candidate moves and deeper plies.

Beat 2 · Abstract

The Game Tree

Minimax scores each line, backs the values up, keeps the best, and prunes the hopeless.

Minimax game tree Leaf evaluations back up to the root; the best line is chosen and weak lines pruned.

Beat 3 · Interactive

Expand the Search

Search deeper or wider; watch the chosen move's evaluation firm up toward certainty.

Expandable search More search shrinks the evaluation's uncertainty until the chosen move is firm. eval +0.9 · firm

depth 1 · breadth 3 · samples 24 · eval +0.90 · exploring

A nod to AlphaGo's move 37 — deep search surfaces the move no human expected.

Milestones & methods
1997 · Chess
Deep Blue beats Kasparov
Brute-force search — ~200M positions/second — plus a handcrafted evaluation toppled the reigning world champion.
2016 · Go
AlphaGo beats Lee Sedol
Go's branching defeated brute force; learned value and policy networks guided the search. Move 37 stunned the experts.
Method
Minimax → MCTS
Chess: minimax with alpha-beta pruning. Go: Monte-Carlo Tree Search steered by neural value & policy nets.