Monte Carlo Tree Search (MCTS) Nedir? (Monte Carlo Ağaç Araması)

#mcts #arama-algoritmasi #oyun-yapay-zeka #alphago #karar-verme #monte-carlo

Monte Carlo Tree Search, rastgele simülasyonlarla oyun ağacını keşfeden ve en iyi hamleyi bulan buluşsal bir karar verme algoritmasıdır.

Monte Carlo Tree Search (MCTS), olasılıksal simülasyonlar kullanarak geniş karar ağaçlarında en iyi hamleyi bulan buluşsal bir arama algoritmasıdır. Klasik minimax aramasından farklı olarak tüm dalları değerlendirmek yerine yüzlerce rastgele simülasyon (rollout) çalıştırır ve kaynakları en umut verici bölgelere yoğunlaştırır. Dört aşamalı bir döngü üzerine kuruludur: Seçim aşamasında mevcut ağaçta UCT (Upper Confidence bounds applied to Trees) formülüyle en iyi düğüm seçilir; Genişleme aşamasında seçilen düğüme yeni çocuk düğümler eklenir; Simülasyon (Rollout) aşamasında rasgele ya da ağırlıklı politika oynamasıyla bir sonuca gidilir; Geri Yayılım aşamasında simülasyon sonucu ağaçtan köke kadar taşınarak istatistikler güncellenir. Verilen süre ya da iterasyon sayısı dolana dek bu döngü tekrar eder; en çok ziyaret edilen kök çocuğu nihai hamle olarak seçilir. Algoritma 2006 yılında Rémi Coulom tarafından bilgisayarlı Go için önerilmiş, Kocsis ve Szepesvári'nin UCT formülüyle güçlendirilmiştir. 2016'da DeepMind'ın AlphaGo programı MCTS'i derin sinir ağlarıyla birleştirerek dünya Go şampiyonu Lee Sedol'ü 4-1 yenerek tarihin en dikkat çekici yapay zeka başarılarından birini gerçekleştirmiştir. 2017'de AlphaZero, satranç, shogi ve Go'da yalnızca öz-oyun ve MCTS kullanarak insan yazılmış bilgiye ihtiyaç duymaksızın tablo kıran performanslar elde etmiştir. MCTS, değerlendirme fonksiyonu tasarlamak güç olmakla birlikte simülasyonların hızlı olduğu board oyunlarından robot planlamasına, ilaç keşfine ve operasyon araştırmasına kadar pek çok alanda tercih edilen güçlü bir karar verme aracıdır.

MCTS Nedir?

Monte Carlo Tree Search (MCTS), oyun teorisi ve yapay zeka planlaması alanında kullanılan olasılıksal bir ağaç arama algoritmasıdır. Adını istatistiksel simülasyon yöntemi olan Monte Carlo yönteminden alır. Klasik minimax algoritmasında tüm olası hamleler enumerasyon yoluyla değerlendirilirken MCTS, bu ağacın yalnızca en umut verici bölgelerini yüzlerce ya da binlerce rastgele simülasyonla örnekler. Böylece çok büyük karar uzaylarında —örneğin Go'nun 10^170'i aşan durum uzayında— makul sürede güçlü kararlar üretebilir. Algoritma 2006 yılında Rémi Coulom tarafından bilgisayarlı Go için önerilmiş; aynı yıl Kocsis ve Szepesvári'nin UCT (Upper Confidence bounds applied to Trees) formülüyle birleşince pratik uygulanabilirliği dramatik biçimde artmıştır.

Dört Aşamalı Döngü

MCTS her iterasyonda dört aşamayı sırasıyla uygular. Seçim (Selection): Kök düğümden başlayarak UCT formülüyle en yüksek puanlı çocuk düğüm seçilir; bu işlem ağacın daha önce ziyaret edilmemiş bir yaprağa ulaşana kadar sürer. UCT = Q_i/N_i + c·√(ln N / N_i) — sol terim kazanma oranını (sömürü), sağ terim az ziyaret edilmiş düğümleri (keşif) ödüllendirir. Genişleme (Expansion): Seçilen yaprak düğüme bir veya daha fazla çocuk düğüm eklenerek ağaç büyütülür. Simülasyon (Rollout): Yeni eklenen düğümden başlayarak rastgele (ya da politika ağırlıklı) hamleler oynanır ve oyun sonuca taşınır; kazanıp kaybetme bilgisi elde edilir. Geri Yayılım (Backpropagation): Simülasyon sonucu ağaç boyunca köke kadar geri yayılır; yolda geçilen her düğümün ziyaret sayısı ve kazanım istatistiği güncellenir. Bu döngü verilen süre dolana ya da hedef iterasyon sayısına ulaşılana kadar tekrar eder. Döngü bittiğinde en çok ziyaret edilen kök çocuğu en iyi hamle olarak seçilir.

AlphaGo ve Derin Öğrenme Entegrasyonu

2016'da DeepMind'ın AlphaGo programı, saf MCTS yerine MCTS'i derin sinir ağlarıyla birleştirdi. Policy network (politika ağı) hangi hamlelerin inceleneceğini daraltırken, value network (değer ağı) simülasyonu terminal duruma kadar götürmek yerine ara pozisyonu puanladı. Bu hibrit yaklaşım hem simülasyon kalitesini hem de ağaç seçim isabetini aynı anda artırdı. Sonuç, dünyanın en iyi Go oyuncusu Lee Sedol'ü 4-1 yenen ilk bilgisayar programıydı; bu tarihsel an yapay zekanın insan üstü performansa ulaştığının sembolü haline geldi. 2017'de AlphaZero bu tasarımı daha da ileri taşıdı: insan yazılmış bilgi ya da oyun kayıtları kullanmaksızın yalnızca öz-oyun ve MCTS ile satranç, shogi ve Go'da tüm rakip programları geçti.

Uygulama Alanları

  • check_circle Board oyunları: Go, satranç, shogi, Hex ve benzeri oyunlarda en iyi bilgisayar programlarının çekirdeğini oluşturur.
  • check_circle Video oyunları ve simülasyon: StarCraft II gibi gerçek zamanlı strateji oyunlarında ve OpenAI Five gibi sistemlerde planlama birimi olarak kullanılır.
  • check_circle Robot planlaması: Belirsizlik altında hareket planlama ve manipülasyon görevlerinde uygun hareket dizilerini bulmak için uygulanır.
  • check_circle İlaç keşfi: Moleküler yapı optimizasyonu ve bileşik arama uzaylarında umut verici adayları hızlı filtrelemek için kullanılır.
  • check_circle Operasyon araştırması: Rota optimizasyonu, çizelgeleme ve kaynak atama problemlerinde keşif-sömürü dengesi gerektiren karar ağaçlarında tercih edilir.

Avantajları ve Sınırlılıkları

MCTS'in temel avantajı, alan bilgisi gerektirmemesidir: oyunun yalnızca kurallarını (geçerli hamleler + sonuç tespiti) bilmek yeterlidir, elle tasarlanmış değerlendirme fonksiyonuna ihtiyaç duyulmaz. Asimetrik ağaç büyüme özelliği sayesinde zaman kısıtlı durumlarda bile kullanılabilir; artan iterasyon sayısıyla doğrudan daha güçlü kararlar üretir. Öte yandan bazı sınırlamaları da mevcuttur. Simülasyonların sığ olması ya da politikanın zayıf kalması halinde rollout'ların kalitesi düşer ve yanıltıcı sinyaller verir. Derinliği uzun horizon gerektiren bazı bulmacalar için salt rastgele rollout yeterli olmayabilir. Ayrıca paralel MCTS implementasyonları senkronizasyon maliyeti taşır ve düğüm güncellemelerinde dikkatli yönetim gerektirir.

MCTS ile İlgili Sık Sorulan Sorular

  • check_circle MCTS minimax'tan neden daha güçlü olabilir?: Minimax tüm dalları belirli bir derinliğe kadar incelerken MCTS kaynaklarını en umut verici bölgelere yoğunlaştırır; asimetrik büyüme sayesinde önemli dallarda çok daha derin gidebilir.
  • check_circle UCT formülündeki c sabiti ne anlama gelir?: c keşif sabitidir; büyük değerler henüz az ziyaret edilmiş düğümleri keşfetmeyi teşvik ederken küçük değerler şu ana kadar en iyi görünen dalları sömürmeye odaklanır. Pratikte √2 sıklıkla kullanılır.
  • check_circle AlphaZero ile saf MCTS arasındaki fark nedir?: Saf MCTS rastgele rollout kullanır. AlphaZero derin sinir ağlarından gelen policy ve value tahminleriyle simülasyon kalitesini artırır; bu sayede çok daha az simülasyonla aynı güç elde edilir.
  • check_circle MCTS deterministik midir?: Hayır, rastgele simülasyon içerdiğinden aynı pozisyonda iki farklı çalıştırma farklı sonuçlar üretebilir. Ancak yeterli iterasyonla sonuçlar yakınsar ve tutarlı hamle tercihlerine ulaşılır.