MCTS

Definisi

MCTS (Monte Carlo Tree Search) adalah algoritma search yang menggabungkan tree search dengan random sampling (Monte Carlo).

4 Langkah

1. Selection — traverse tree dari root dengan UCT/PUCT
2. Expansion — tambah child node baru
3. Simulation (rollout) — random play sampai akhir
4. Backpropagation — update statistik node

Sejarah

• 2006 — Rémi Coulom (Crazy Stone, Go program) mempopulerkan
• 2016 — AlphaGo menggunakan MCTS + deep neural networks
• 2017 — AlphaZero — pure MCTS + neural network
• 2019+ — MuZero, dll

Aplikasi

• Game AI (Go, catur, shogi, hex, dll)
• Planning (robot, logistics)
• Optimization (combinatorial)
• Drug discovery (search molecule)
• Theorem proving (AlphaProof 2024)