Monte Carlo Tree Search (MCTS): AlphaGo'nun Zekasının Kalbi

"Olası bir trilyon hamle"

Bir Go tahtası: $19 \times 19 = 361$ pozisyon. Tüm oyun ağacı: yaklaşık $10^{170}$ olası durum.

Evrendeki atom sayısı: yaklaşık $10^{80}$.

Brute force imkansız. Mini-max + alpha-beta kesme bile yetmez.

2006'da bir yeni algoritma: Monte Carlo Tree Search (MCTS).

Temel fikir

İki güçlü teknik birleştir:

1. Monte Carlo simülasyonu: rastgele oyunlar.
2. Ağaç araması: en umut verici hareketlere odaklan.

Dört adım

Her MCTS iterasyonu:

1. Selection

Ağaç kökünden başla. UCB1 formülü ile çocuk seç:

$\text{UCB1} = \frac{w_i}{n_i} + c \sqrt{\frac{\ln N}{n_i}}$

$w_i$ = $i$ düğümünün kazanma sayısı, $n_i$ = ziyaret, $N$ = parent ziyaret, $c$ = exploration sabiti.

İlk terim: exploitation (iyi bilinene git).
İkinci terim: exploration (az denenmişe git).

2. Expansion

Yaprak düğümde yeni çocuk ekle.

3. Simulation (rollout)

Yeni düğümden başlayarak rastgele oyun sonuna kadar oyna. Sonucu kaydet.

4. Backpropagation

Sonucu kökten o düğüme kadar tüm yola yay. İstatistikleri güncelle.

Bu dört adımı milyonlarca kez tekrarla. En çok ziyaret edilen kök çocuk = en iyi hamle.

Niçin işe yarar?

MCTS'in sihri:

• Brute force yok: tüm ağacı incelemeye gerek yok.
• Adaptif: önemli yerlerde derin, önemsiz yerlerde sığ.
• Rastgelelik yardımı: dar bir uzayda da iyi sonuç.
• Heuristic gerekmez: domain bilgisi sıfırla bile iyi.

UCB1'in zarafeti

UCB1 = Upper Confidence Bound. Olasılık teorisinden:

"Bilinmeyen bir bandit içinde, en iyi olanı bulmak için exploration vs exploitation dengesi."

UCB1 bu dengeyi matematik olarak optimal yapar (logaritmik regret).

Tarihsel köken

• 2006: Rémi Coulom Go AI için MCTS'yi tanıttı.
• 2007-09: MoGo, Crazy Stone — ilk Go programları.
• 2016: AlphaGo (Google DeepMind) MCTS + derin sinir ağları = dünya şampiyonunu yendi.
• 2017: AlphaZero — sıfır insan bilgisi ile satranç, Go, shogi.
• 2020: MuZero — kurallar bile öğrenildi.

AlphaGo'nun yapısı

MCTS + iki sinir ağı:

1. Policy network: hangi hamleler muhtemelen iyi?
2. Value network: bu pozisyon kazanma olasılığı?

MCTS bu iki ağdan yardım alır:

• Policy → expansion için hareket önerisi.
• Value → simulation yerine değer tahmini.

Sonuç: çok daha az iterasyonda insan-üstü oyun.

Modern uygulamalar

1. Oyun AI

Go, satranç, shogi, poker, StarCraft.

2. Planlama

Robot manevra planlaması.

3. Otomatik yazılım sentezi

Kod yazan AI sistemler.

4. İlaç keşfi

Molekül uzayında arama.

5. Optimizasyon

Karmaşık karar uzayları.

6. LLM "düşünme"

Modern büyük dil modellerinde "test-time compute" — MCTS-tipi arama. GPT-o1, DeepSeek R1.

Sınırlamalar

• Hesap pahalı: milyonlarca simülasyon.
• Doğru değer fonksiyonu gerek: AlphaGo öncesi MCTS ortalama performans.
• Sürekli aksiyon uzayı: standartı zor.

AlphaGo etkisi

Mart 2016: AlphaGo, Lee Sedol (dünya şampiyonu) ile 4-1 mağlup etti.

Tarihte bir an: 2500 yıllık Go matematiği, makine öğrenmesine teslim oldu.

Bu, modern AI'nın kamuoyu uyanışıydı.

Sonuç

Monte Carlo Tree Search:

• Rastgele simülasyon + akıllı ağaç araması birleşimi.
• UCB1 ile exploration-exploitation dengesi.
• AlphaGo (2016) ile dünyaya ışıldadı.
• Modern oyun AI ve planlama'nın standardı.
• Modern LLM'lerin "düşünme" tekniği.

Bir matematik algoritma — astronomik karar uzaylarını navigasyon edilebilir yapar. Modern yapay zeka çağının önemli ara basamağı.

"Rastgelelik akıllıca kullanılırsa, dehadan farksız." MCTS'nin paradigması.