Monte Carlo ağaç araması

Kısaca MCTS denilen Monte Carlo ağaç araması, her varyantı aynı derinliğe kadar incelemeye çalışmaz. Ağacı aşamalı olarak büyütür ve sonraki hesaplama bölümünün nereye ayrılacağını seçmek için biriken sonuçları kullanır. Çok ziyaret edilen bir hamle otomatik olarak iyi değildir, ancak tahmini genellikle daha fazla aramayla desteklenmiştir.

Bir MCTS döngüsü

1. Seçim: Başlangıç konumundan ilerleyip mevcut dalları izlerken, güçlü görünen hamlelerle hâlâ belirsiz kalan hamleleri dengeler.
2. Genişletme: Ağacın henüz geliştirmediği bir konum veya hamleyi ekler.
3. Değerlendirme: Yeni konumdan sonucu tahmin eder. Klasik yöntemler benzetimli partileri tamamlayabilir; modern sistemler ise konumu değerlendirmek için örüntüleri tanımak üzere eğitilmiş bir model olan sinir ağını kullanabilir.
4. Geri yayılım: Sonucu ziyaret edilen yol boyunca geriye taşır ve ziyaret sayılarını ve tahminlerini günceller.

Bu döngünün tekrarlanması sömürü ile keşfi dengeler. Sömürü, kanıtların zaten olumlu olduğu yerlere daha fazla çaba ayırmaktır. Keşif, bir sürprizi fazla erken elememek için belirsiz alternatifleri sınamaktır. İkisini dengeleyen kesin kural uygulamaya bağlıdır.

Minimax'tan farklı olarak MCTS, bir dalın ne kadar araştırılacağına çoğu zaman yalnızca tekdüze derinliğe göre değil, arama sırasında toplanan kanıtlara göre karar verir. Sinir ağlarına dayalı bazı satranç programlarında ağ, olası hamleleri öneren bir politika ve sonucu tahmin eden bir değer sağlar. Genel arama süreci farklı olsa da değer, değerlendirme fonksiyonuna benzer bir rol üstlenir.