Monte Carlo Ağaç Araması Nedir?

Monte Carlo ağaç araması (Monte Carlo Tree Search, MCTS), özellikle olası hamle sayısının çok büyük olduğu oyunlarda ve planlama problemlerinde kullanılan bir arama yöntemidir. Her hamlenin değerini kesin hesaplamak yerine, o hamleden sonra oyunu birçok kez simüle ederek istatistiksel bir tahmin üretir. Adını rastgele örneklemeye dayanan Monte Carlo yöntemlerinden alır.

Monte Carlo ağaç araması nedir?

Minimax gibi klasik yöntemler tüm dalları belirli bir derinliğe kadar inceler. Go gibi her hamlede yüzlerce seçeneğin olduğu oyunlarda bu imkânsız hâle gelir. MCTS ise arama ağacını asimetrik büyütür: iyi görünen hamleleri daha çok, kötü görünenleri daha az inceler.

Nasıl çalışır?

Her yinelemede dört adım uygulanır:

1. Seçim: Kökten başlayarak, hem iyi sonuç vermiş hem de yeterince denenmemiş düğümleri dengeleyen bir formülle aşağı inilir.
2. Genişletme: Ulaşılan düğüme yeni bir çocuk düğüm eklenir.
3. Simülasyon: Bu noktadan oyun, rastgele ya da basit kurallarla sonuna kadar oynanır.
4. Geri yayma: Sonuç (kazanç ya da kayıp), yol üzerindeki tüm düğümlerin istatistiklerine eklenir.

Belirli bir süre ya da yineleme sayısı dolduğunda en çok ziyaret edilen hamle seçilir.

Kullanım alanları ve sınırlar

MCTS, 2016'da Go'da üst düzey bir profesyonel oyuncuyu yenen sistemde derin sinir ağlarıyla birlikte kullanılarak geniş ilgi gördü. Oyunların yanı sıra robot planlama ve çizelgeleme gibi alanlarda da uygulanır. Avantajı, ayrıntılı bir değerlendirme fonksiyonu olmadan da çalışabilmesidir. Dezavantajı ise iyi sonuç için çok sayıda simülasyon gerektirmesi ve simülasyonların gerçekçi olmadığı durumlarda yanıltıcı tahminler üretebilmesidir.