Monte Carlo Tree Search

Why It Was Important

MCTS broke the deadlock in computer Go, where the branching factor made the exhaustive search that beat Kasparov at chess useless. By sampling rather than enumerating, and balancing exploration against exploitation, it lifted Go programs from amateur to strong play — and married to neural networks a decade later, it became the search half of AlphaGo.

Who Invented It

Rémi Coulom, Levente Kocsis, Csaba Szepesvári

Coulom named the method; Kocsis and Szepesvári contributed the UCT selection rule that made it converge.

Applications

• Computer Go
• Game Playing
• AlphaGo
• Planning Under Uncertainty