Pencarian pohon Monte Carlo

Pencarian pohon Monte Carlo, yang disingkat MCTS, tidak berusaha memeriksa setiap variasi hingga kedalaman yang sama. Metode ini menumbuhkan pohon secara bertahap dan menggunakan hasil yang terkumpul untuk memilih ke mana bagian komputasi berikutnya diarahkan. Langkah yang sangat sering dikunjungi tidak otomatis baik, tetapi perkiraannya biasanya didukung pencarian yang lebih banyak.

Satu siklus MCTS

1. Seleksi: mulai dari posisi awal dan ikuti cabang yang sudah ada sambil menyeimbangkan langkah yang sudah tampak kuat dengan langkah yang masih belum pasti.
2. Ekspansi: tambahkan posisi atau langkah yang belum dikembangkan oleh pohon.
3. Evaluasi: perkirakan hasil dari posisi baru. Metode klasik dapat menyelesaikan partai simulasi, sedangkan sistem modern dapat menggunakan jaringan saraf, yaitu model terlatih yang mengenali pola, untuk menilainya.
4. Propagasi balik: bawa hasil kembali di sepanjang jalur yang dikunjungi dan perbarui jumlah kunjungan serta perkiraannya.

Pengulangan siklus ini menyeimbangkan eksploitasi dan eksplorasi. Eksploitasi berarti mencurahkan lebih banyak upaya ke tempat yang buktinya sudah menguntungkan. Eksplorasi berarti menguji alternatif yang belum pasti agar kejutan tidak ditolak terlalu dini. Aturan tepat untuk menyeimbangkan keduanya bergantung pada implementasi.

Berbeda dari minimax, MCTS biasanya menentukan seberapa banyak analisis yang diberikan pada suatu cabang berdasarkan bukti yang terkumpul selama pencarian, bukan hanya kedalaman seragam. Dalam beberapa program catur berbasis jaringan saraf, jaringan menyediakan kebijakan, yang menyarankan langkah yang mungkin, dan nilai, yang memperkirakan hasil. Nilai tersebut memiliki peran terkait fungsi evaluasi, meskipun proses pencarian keseluruhannya berbeda.