MCTS
Definisi
MCTS (Monte Carlo Tree Search) adalah algoritma search yang menggabungkan tree search dengan random sampling (Monte Carlo).
4 Langkah
- Selection — traverse tree dari root dengan UCT/PUCT
- Expansion — tambah child node baru
- Simulation (rollout) — random play sampai akhir
- 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)