Kombinasi MCTS dan Neural Network

Pada artikel-artikel sebelumnya, kita telah membahas Neural Network (Policy Network dan Value Network) serta konsep Reinforcement Learning secara terpisah. Sekarang, mari kita jelajahi inovasi inti AlphaGo—bagaimana menggabungkan Monte Carlo Tree Search (MCTS) dengan Neural Network secara sempurna.

Kombinasi ini adalah kunci keberhasilan AlphaGo: Neural Network menyediakan "intuisi", MCTS menyediakan "penalaran", keduanya saling melengkapi.

---

Tinjauan MCTS Tradisional

Apa itu MCTS?

Monte Carlo Tree Search (MCTS) adalah algoritma pencarian berbasis sampling acak, sangat cocok untuk AI game.

Ide inti MCTS adalah: daripada menghitung semua kemungkinan langkah secara menyeluruh, lebih baik mensimulasikan sejumlah besar permainan secara acak dan menggunakan statistik untuk memperkirakan kualitas setiap langkah.

Empat Tahap

MCTS tradisional terdiri dari empat tahap yang terus diulang:

Mari kita pahami setiap tahap secara detail:

1. Selection (Seleksi)

Dimulai dari node root, turun mengikuti pohon, memilih child node yang "paling menjanjikan" hingga mencapai leaf node.

Kriteria seleksi adalah rumus UCB1 (Upper Confidence Bound):

$\text{UCB1}(s, a) = \bar{X}_{s,a} + c \sqrt{\frac{\ln N_s}{N_{s,a}}}$

Di mana:

• $\bar{X}_{s,a}$: Rata-rata return dari node $(s, a)$ (term eksploitasi)
• $\sqrt{\frac{\ln N_s}{N_{s,a}}}$: Bonus eksplorasi (term eksplorasi)
• $N_s$: Jumlah kunjungan parent node
• $N_{s,a}$: Jumlah kunjungan child node
• $c$: Konstanta yang menyeimbangkan eksplorasi dan eksploitasi

Kecerdasan rumus ini terletak pada:

• Node dengan kunjungan sedikit mendapat bonus eksplorasi lebih tinggi
• Seiring bertambahnya kunjungan, seleksi semakin condong ke node dengan nilai aktual tinggi

2. Expansion (Ekspansi)

Setelah mencapai leaf node, pilih satu aksi yang belum dieksplorasi, buat child node baru.

Sebelum ekspansi:              Setelah ekspansi:
     ○ (root)                      ○ (root)
    /│\                           /│\
   ○ ○ ○                         ○ ○ ○
  /│              →             /│
 ○ ○                           ○ ○
   ↑                              \
   leaf node                       ● (node baru)

3. Simulation (Simulasi/Rollout)

Dari node baru, gunakan strategi tertentu (biasanya acak atau heuristik sederhana) untuk menyelesaikan permainan dengan cepat dan mendapatkan hasilnya.

Inilah asal nama "Monte Carlo"—menggunakan simulasi acak untuk memperkirakan hasil.

Strategi rollout MCTS tradisional bisa berupa:

• Acak murni: Memilih langkah legal secara uniform random
• Heuristik ringan: Menggunakan aturan sederhana untuk menyaring langkah yang jelas buruk

4. Backpropagation (Propagasi Balik)

Meneruskan hasil simulasi (menang/kalah) kembali melalui jalur, memperbarui informasi statistik setiap node:

Konten pembaruan:
- Jumlah kunjungan: N(s, a) ← N(s, a) + 1
- Nilai kumulatif: W(s, a) ← W(s, a) + z
- Nilai rata-rata: Q(s, a) = W(s, a) / N(s, a)

Di mana $z$ adalah hasil simulasi (+1 atau -1).

Keterbatasan MCTS Tradisional

Performa MCTS tradisional pada Go terbatas, masalah utamanya adalah:

1. Kualitas rollout buruk: Simulasi acak sering menghasilkan permainan tidak masuk akal
2. Membutuhkan banyak simulasi: Setiap langkah mungkin membutuhkan puluhan ribu simulasi
3. Evaluasi tidak akurat: Hanya mengandalkan statistik menang/kalah, efisiensi pemanfaatan informasi rendah
4. Tidak bisa memanfaatkan pola: Setiap kali pencarian ulang, tidak mengakumulasi pengalaman

Masalah-masalah ini diselesaikan secara elegan oleh Neural Network di AlphaGo.

---

Bagaimana Neural Network Meningkatkan MCTS

Arsitektur Keseluruhan

AlphaGo mengintegrasikan dua Neural Network ke dalam MCTS:

Peran Policy Network

Policy Network berperan dalam tahap Expansion.

Dalam MCTS tradisional saat ekspansi, semua aksi yang belum dieksplorasi dianggap sama pentingnya. Namun Policy Network menyediakan prior probability (probabilitas prior):

$P(s, a) = \pi_\theta(a|s)$

Ini membuat MCTS memprioritaskan eksplorasi langkah-langkah yang "terlihat lebih baik", sangat meningkatkan efisiensi pencarian.

Misalnya, dalam suatu posisi:

• "Tengen" mungkin hanya memiliki probabilitas 0.01%
• "Joseki di sudut" mungkin memiliki probabilitas 15%
• "Area besar" mungkin memiliki probabilitas 10%

MCTS akan memprioritaskan eksplorasi langkah dengan probabilitas tinggi, bukan membuang waktu pada pilihan yang jelas buruk.

Peran Value Network

Value Network berperan dalam tahap Evaluation.

MCTS tradisional perlu menyelesaikan seluruh permainan untuk mendapat evaluasi. Namun Value Network bisa langsung mengevaluasi win rate posisi mana pun:

$v(s) = V_\phi(s)$

Ini seperti meminta seorang master mengevaluasi posisi, bukan membiarkan dua pemula menyelesaikan permainan baru kemudian melihat hasilnya.

AlphaGo versi original menggunakan campuran Value Network dan Rollout:

$V(s_L) = (1 - \lambda) \cdot v_\theta(s_L) + \lambda \cdot z_L$

Di mana:

• $v_\theta(s_L)$: Evaluasi Value Network
• $z_L$: Hasil Rollout
• $\lambda$: Koefisien campuran (AlphaGo menggunakan $\lambda = 0.5$)

Visualisasi Search Tree

Mari kita visualisasikan search tree MCTS:

載入中...

Dalam visualisasi ini, Anda bisa melihat:

• Ukuran node mencerminkan jumlah kunjungan
• Jalur biru adalah jalur terbaik yang dipilih MCTS
• Setiap node menampilkan jumlah kunjungan N dan nilai rata-rata Q

---

Penjelasan Detail Proses Pencarian

Alur Lengkap

Mari kita ikuti satu simulasi MCTS lengkap:

Algoritma: Simulasi Tunggal MCTS AlphaGo

Input: Node root s_root, Policy Network π, Value Network V

1. Selection (Seleksi)
   s = s_root
   jalur = []

   while s bukan leaf node:
       # Gunakan rumus PUCT untuk memilih aksi
       a* = argmax_a [Q(s,a) + U(s,a)]

       di mana U(s,a) = c_puct · P(s,a) · √N(s) / (1 + N(s,a))

       jalur.append((s, a*))
       s = state setelah eksekusi aksi a*

2. Expansion (Ekspansi)
   Jika s bukan terminal state:
       # Gunakan Policy Network untuk menghitung prior probability
       P(s, ·) = π(·|s)

       # Buat child node untuk semua aksi legal
       for a in aksi_legal:
           buat child node (s, a)
           set P(s,a), N(s,a)=0, W(s,a)=0

3. Evaluation (Evaluasi)
   # Campuran Value Network dan Rollout
   v = V(s)                          # Evaluasi Value Network
   z = rollout(s)                    # Hasil Rollout
   value = (1-λ)·v + λ·z             # Campuran

   # AlphaGo Zero disederhanakan hanya menggunakan Value Network
   # value = V(s)

4. Backpropagation (Propagasi Balik)
   for (s', a') in reverse(jalur):
       N(s', a') += 1
       W(s', a') += value
       Q(s', a') = W(s', a') / N(s', a')
       value = -value                 # Ganti perspektif

Penjelasan Detail Tahap Seleksi

Tahap seleksi menggunakan rumus PUCT (akan dibahas detail di artikel berikutnya):

$a^* = \arg\max_a \left[ Q(s,a) + c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)} \right]$

Rumus ini menyeimbangkan:

• Q(s,a): Nilai rata-rata yang sudah diketahui (eksploitasi)
• U(s,a): Bonus eksplorasi, menggabungkan prior probability dan jumlah kunjungan (eksplorasi)

Penjelasan Detail Tahap Ekspansi

Ketika mencapai leaf node, gunakan Policy Network untuk menginisialisasi node baru:

def expand(state, policy_network):
    # Dapatkan probabilitas semua aksi legal
    action_probs = policy_network(state)

    # Filter aksi ilegal dan renormalisasi
    legal_actions = get_legal_actions(state)
    legal_probs = action_probs[legal_actions]
    legal_probs = legal_probs / legal_probs.sum()

    # Buat child node
    for action, prob in zip(legal_actions, legal_probs):
        child = create_node(
            state=apply_action(state, action),
            prior=prob,
            visit_count=0,
            value_sum=0
        )
        add_child(current_node, action, child)

Penjelasan Detail Tahap Evaluasi

AlphaGo versi original menggunakan campuran dua evaluasi:

Evaluasi Value Network:

• Input langsung posisi, output win rate
• Perhitungan cepat (satu inferensi neural network)
• Memberikan evaluasi perspektif global

Evaluasi Rollout:

• Menggunakan fast policy (Fast Rollout Policy) untuk menyelesaikan permainan
• Perhitungan lebih lambat tapi memberikan hasil permainan lengkap
• Bisa menemukan beberapa taktik yang mungkin terlewatkan neural network

def evaluate(state, value_network, rollout_policy, lambda_mix=0.5):
    # Evaluasi Value Network
    v = value_network(state)

    # Evaluasi Rollout
    current = state
    while not is_terminal(current):
        action = rollout_policy(current)
        current = apply_action(current, action)
    z = get_result(current)

    # Campuran
    return (1 - lambda_mix) * v + lambda_mix * z

AlphaGo Zero menghapus Rollout, hanya menggunakan Value Network. Ini menyederhanakan sistem dan meningkatkan efisiensi.

Penjelasan Detail Backpropagation

Meneruskan hasil evaluasi melalui jalur, memperbarui statistik:

def backpropagate(path, value):
    for state, action in reversed(path):
        # Update jumlah kunjungan
        state.visit_count[action] += 1
        # Update total nilai
        state.value_sum[action] += value
        # Update nilai rata-rata
        state.Q[action] = state.value_sum[action] / state.visit_count[action]
        # Ganti perspektif (keuntungan lawan adalah kerugian saya)
        value = -value

Perhatikan langkah value = -value: Go adalah zero-sum game, kemenangan satu pihak adalah kekalahan pihak lain.

---

Alokasi Sumber Daya Komputasi

Jumlah Pencarian

AlphaGo melakukan sejumlah besar simulasi MCTS untuk setiap langkah:

Versi	Simulasi per Langkah	Waktu Berpikir
AlphaGo Fan	~100,000	Menit
AlphaGo Lee	~100,000	Menit
AlphaGo Zero (pelatihan)	1,600	Detik
AlphaGo Zero (pertandingan)	~1,600	Detik

AlphaGo Zero mencapai kekuatan bermain lebih tinggi dengan simulasi lebih sedikit, ini adalah hasil peningkatan kualitas neural network.

Strategi Alokasi Waktu

Posisi berbeda mungkin memerlukan waktu berpikir berbeda:

def allocate_time(game_state, remaining_time):
    # Alokasi dasar
    num_moves_remaining = estimate_remaining_moves(game_state)
    base_time = remaining_time / num_moves_remaining

    # Faktor penyesuaian
    complexity = estimate_complexity(game_state)
    importance = estimate_importance(game_state)

    # Posisi kompleks atau penting dapat lebih banyak waktu
    allocated_time = base_time * complexity * importance

    # Pastikan tidak timeout
    return min(allocated_time, remaining_time * 0.3)

Dalam pertandingan nyata, AlphaGo menghabiskan lebih banyak waktu berpikir pada posisi kritis (seperti momen mendekati batas menang/kalah).

Pencarian Paralel

MCTS secara alami cocok untuk paralelisasi:

Teknik Virtual Loss:

Ketika satu thread sedang mengeksplorasi jalur P:
1. Sementara anggap jalur ini sudah kalah (virtual loss)
2. Thread lain akan cenderung mengeksplorasi jalur lain
3. Ketika hasil kembali, update statistik sebenarnya dan hapus virtual loss

Ini memastikan beberapa thread tidak mengeksplorasi jalur yang sama berulang kali.

def parallel_mcts_simulation(root, num_threads=8):
    virtual_losses = {}

    def simulate(thread_id):
        # Tahap seleksi (dengan virtual loss)
        path = []
        node = root
        while not node.is_leaf():
            action = select_with_virtual_loss(node, virtual_losses)
            add_virtual_loss(node, action, virtual_losses)
            path.append((node, action))
            node = node.children[action]

        # Ekspansi dan evaluasi
        value = expand_and_evaluate(node)

        # Backpropagation dan hapus virtual loss
        backpropagate(path, value)
        remove_virtual_losses(path, virtual_losses)

    # Eksekusi paralel beberapa simulasi
    threads = [Thread(target=simulate, args=(i,)) for i in range(num_threads)]
    for t in threads:
        t.start()
    for t in threads:
        t.join()

Batch Processing GPU

Inferensi neural network paling efisien di GPU dalam mode batch. AlphaGo menggunakan batch evaluation:

Tanpa batch:
  Simulasi 1 → Evaluasi 1 → Simulasi 2 → Evaluasi 2 → ...
  Utilisasi GPU rendah

Dengan batch:
  Kumpulkan 32 posisi untuk dievaluasi
  → Kirim ke GPU sekaligus untuk evaluasi
  → Kembalikan 32 hasil
  Utilisasi GPU tinggi

Ini membutuhkan penjadwalan lebih kompleks, tapi sangat meningkatkan throughput.

---

Temperature dan Seleksi Akhir

Temperature saat Pelatihan

Dalam self-play training, AlphaGo menggunakan temperature untuk mengontrol eksplorasi:

$\pi(a) = \frac{N(s,a)^{1/\tau}}{\sum_{a'} N(s,a')^{1/\tau}}$

Di mana $\tau$ adalah parameter temperature.

• $\tau = 1$: Probabilitas proporsional dengan jumlah kunjungan (pertahankan diversitas)
• $\tau \to 0$: Pilih aksi dengan kunjungan terbanyak (seleksi deterministik)

Strategi AlphaGo Zero:

• 30 langkah pertama: $\tau = 1$, pertahankan diversitas opening
• Setelahnya: $\tau \to 0$, pilih langkah terbaik

Seleksi saat Pertandingan

Dalam pertandingan nyata, seleksi biasanya deterministik:

def select_move(root, temperature=0):
    if temperature == 0:
        # Pilih aksi dengan kunjungan terbanyak
        return argmax(root.visit_counts)
    else:
        # Sampling dari distribusi probabilitas yang disesuaikan temperature
        probs = root.visit_counts ** (1 / temperature)
        probs = probs / probs.sum()
        return np.random.choice(actions, p=probs)

Mempertimbangkan Win Rate

Kadang juga mempertimbangkan nilai rata-rata bukan hanya jumlah kunjungan:

def select_move_with_value(root, temperature=0):
    # Campuran jumlah kunjungan dan nilai
    scores = root.visit_counts * (1 + root.Q_values)
    scores = scores / scores.sum()

    if temperature == 0:
        return argmax(scores)
    else:
        probs = scores ** (1 / temperature)
        probs = probs / probs.sum()
        return np.random.choice(actions, p=probs)

---

Perbandingan dengan Neural Network Murni

Mengapa Perlu Pencarian?

Pertanyaan alami adalah: jika neural network sudah bisa memprediksi langkah bagus, mengapa masih perlu pencarian?

Jawabannya adalah: pencarian bisa memperbaiki kesalahan neural network dan menemukan langkah lebih baik.

Metode	Kelebihan	Kekurangan
Neural network murni	Cepat, intuitif	Mungkin ada titik buta
MCTS murni	Bisa analisis mendalam	Lambat, butuh evaluasi
Neural network + MCTS	Gabungkan kelebihan keduanya	Beban komputasi besar

Bukti Eksperimental

Eksperimen DeepMind menunjukkan:

Neural Network murni: ~3000 Elo
Policy + sedikit MCTS: ~3500 Elo
Policy + Value + MCTS: ~4500 Elo

Pencarian memberikan peningkatan kekuatan bermain yang signifikan.

Fungsi Pencarian

Pencarian sangat berharga dalam situasi berikut:

1. Kalkulasi taktis: Membaca serangan dan penangkapan kompleks
2. Koreksi bias: Memperbaiki kesalahan sistematis neural network
3. Menangani posisi langka: Neural network mungkin tidak pernah melihat saat pelatihan
4. Verifikasi intuisi: Memastikan langkah yang "terlihat bagus" memang benar-benar bagus

---

Perbedaan Berbagai Versi AlphaGo

AlphaGo Fan/Lee

Arsitektur:
- SL Policy Network (Supervised Learning)
- RL Policy Network (Reinforcement Learning)
- Value Network
- Fast Rollout Policy

Saat pencarian:
- Gunakan prior probability dari SL Policy Network
- Campuran evaluasi Value Network dan Rollout

AlphaGo Master

Arsitektur:
- Neural network lebih besar
- Lebih banyak data pelatihan
- Fitur yang ditingkatkan

Saat pencarian:
- Mirip AlphaGo Lee
- Network lebih kuat = kebutuhan pencarian lebih sedikit

AlphaGo Zero

Arsitektur:
- Single dual-head ResNet
- Dilatih dari nol
- Tanpa Rollout

Saat pencarian:
- Policy head menyediakan prior probability
- Value head langsung mengevaluasi
- Lebih simpel, lebih kuat

Ringkasan Evolusi

---

Pertimbangan Implementasi

Manajemen Memori

MCTS tree bisa menjadi sangat besar:

Asumsi:
- Rata-rata 200 aksi legal per langkah
- Kedalaman pencarian 10
- Ekspansi penuh: 200^10 ≈ 10^23 node (tidak mungkin)

Praktik aktual:
- Hanya ekspansi node yang dikunjungi
- Bersihkan node yang jarang dikunjungi secara berkala
- Gunakan ulang search tree dari langkah sebelumnya

Penggunaan Ulang Tree

Setelah lawan bermain, sebagian search tree bisa digunakan ulang:

def reuse_tree(root, opponent_move):
    if opponent_move in root.children:
        new_root = root.children[opponent_move]
        # Bersihkan branch lain yang tidak diperlukan
        for action in root.children:
            if action != opponent_move:
                delete_subtree(root.children[action])
        return new_root
    else:
        # Lawan bermain langkah tak terduga, perlu mulai ulang
        return create_new_root()

Cache Neural Network

Posisi yang sama mungkin dievaluasi berkali-kali, gunakan cache untuk menghindari perhitungan berulang:

class NeuralNetworkCache:
    def __init__(self, max_size=100000):
        self.cache = LRUCache(max_size)

    def evaluate(self, state, network):
        state_hash = hash(state)
        if state_hash in self.cache:
            return self.cache[state_hash]
        else:
            result = network(state)
            self.cache[state_hash] = result
            return result

Pemanfaatan Simetri

Go memiliki 8 simetri, bisa digunakan untuk meningkatkan pencarian:

def evaluate_with_symmetry(state, network):
    # Generate semua transformasi simetri
    symmetries = generate_symmetries(state)  # 8 versi

    # Evaluasi semua versi
    values = [network(s) for s in symmetries]

    # Rata-rata (lebih stabil)
    return np.mean(values)

---

Kedalaman dan Lebar Pencarian

Penyesuaian Dinamis

MCTS secara otomatis menyeimbangkan kedalaman dan lebar:

• Lebar: Dikontrol oleh prior probability Policy Network
• Kedalaman: Ditentukan oleh akurasi Value Network

Ketika neural network sangat baik:

• Langkah dengan kepercayaan tinggi dieksplorasi lebih dalam
• Langkah dengan kepercayaan rendah disingkirkan dengan cepat
• Pencarian secara alami terfokus pada branch penting

Perbandingan dengan Pencarian Tradisional

Metode	Kontrol Kedalaman	Kontrol Lebar
Minimax	Kedalaman tetap	Alpha-Beta pruning
MCTS Tradisional	Ditentukan simulasi	UCB1
AlphaGo MCTS	Dipandu Policy + Value	PUCT + Policy

Pencarian AlphaGo lebih "cerdas"—ia tahu area mana yang layak untuk didalami, mana yang bisa dilewati dengan cepat.

---

Korespondensi Animasi

Konsep inti yang dibahas dalam artikel ini dan nomor animasinya:

Nomor	Konsep	Korespondensi Fisika/Matematika
E5 C5	Empat tahap MCTS	Tree search

---

Ringkasan

Kombinasi MCTS dan Neural Network adalah inovasi inti AlphaGo. Kita telah mempelajari:

1. MCTS Tradisional: Selection, Expansion, Simulation, Backpropagation
2. Peningkatan Neural Network: Policy Network memandu ekspansi, Value Network menggantikan Rollout
3. Proses Pencarian: Seleksi PUCT, evaluasi batch, backpropagation
4. Alokasi Sumber Daya: Jumlah simulasi, manajemen waktu, pencarian paralel
5. Seleksi Temperature: Strategi berbeda untuk pelatihan dan pertandingan
6. Detail Implementasi: Manajemen memori, penggunaan ulang tree, caching

Artikel berikutnya, kita akan menjelajahi detail matematika rumus PUCT secara mendalam.

---

Bacaan Lanjutan

• Artikel Berikutnya: Penjelasan Detail Rumus PUCT — Prinsip matematika seleksi MCTS
• Artikel Sebelumnya: Self-Play — Mekanisme dan efek self-play
• Terkait: Penjelasan Detail Policy Network — Arsitektur strategy network

---

Referensi

1. Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489.
2. Silver, D., et al. (2017). "Mastering the game of Go without human knowledge." Nature, 550, 354-359.
3. Coulom, R. (2006). "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search." Computers and Games.
4. Kocsis, L., & Szepesvari, C. (2006). "Bandit based Monte-Carlo Planning." ECML.
5. Browne, C., et al. (2012). "A Survey of Monte Carlo Tree Search Methods." IEEE TCIAIG.
6. Rosin, C. D. (2011). "Multi-armed bandits with episode context." Annals of Mathematics and Artificial Intelligence.