Lewati ke konten utama

Self-Play

Di artikel sebelumnya, kita memperkenalkan konsep dasar reinforcement learning. Sekarang, mari kita eksplorasi salah satu kunci keberhasilan AlphaGo—Self-Play.

Ini adalah konsep yang tampak paradoks: Bagaimana AI bisa menjadi lebih kuat dengan bermain melawan dirinya sendiri?

Jawabannya mendalam sekaligus elegan, melibatkan game theory, dinamika evolusi, dan esensi pembelajaran.


Mengapa Self-Play Efektif?

Penjelasan Intuitif

Bayangkan Anda adalah seorang pemula Go, berlatih sendirian di pulau terpencil:

  1. Anda bermain satu permainan, memainkan kedua sisi hitam dan putih sekaligus
  2. Setelah permainan selesai, Anda menganalisis langkah mana yang bagus, mana yang buruk
  3. Di permainan berikutnya, Anda mencoba menghindari kesalahan sebelumnya
  4. Anda mengulangi proses ini jutaan kali

Secara intuitif, ini tampak bermasalah:

  • Jika level Anda sangat rendah, kedua sisi bermain langkah buruk, apa yang bisa dipelajari?
  • Apakah akan terjebak dalam "keseimbangan yang salah"—kedua sisi bermain langkah salah tapi saling membatalkan?

Tetapi sebenarnya, self-play dapat menghasilkan kemajuan berkelanjutan. Alasannya sebagai berikut:

Penemuan Kelemahan secara Bertahap

Wawasan kunci adalah: Bahkan jika kedua sisi adalah AI yang sama, hasil setiap permainan tetap mengandung informasi.

Posisi A: AI memilih langkah X, akhirnya menang
Posisi A: AI memilih langkah Y, akhirnya kalah

→ Kesimpulan: Di posisi A, X lebih baik dari Y

Melalui statistik sejumlah besar permainan, AI dapat mempelajari pilihan mana yang lebih baik di setiap posisi. Inilah esensi policy gradient: pilihan bagus diperkuat, pilihan buruk ditekan.

Adversarial Learning

Self-play memiliki properti khusus: Lawan pelatihan secara otomatis menyesuaikan dengan level Anda.

Siklus pelatihan 1: AI menemukan taktik efektif T
Siklus pelatihan 2: AI sebagai lawan belajar cara mempertahankan T
Siklus pelatihan 3: AI asli dipaksa mencari taktik lebih baik T'

Ini membentuk perlombaan senjata (Arms Race), kedua sisi terus menemukan dan mengatasi kelemahan masing-masing.

Perbandingan dengan Catatan Permainan Manusia

Metode PelatihanKelebihanKekurangan
Catatan manusiaMempelajari kristalisasi kebijaksanaan manusiaTerbatas pada level manusia
Self-playPotensi peningkatan tanpa batasMungkin terjebak di optimum lokal
Kombinasi keduanyaMulai cepat + peningkatan berkelanjutanStrategi terbaik

AlphaGo versi asli pertama menggunakan catatan manusia untuk supervised learning, kemudian menggunakan self-play untuk reinforcement learning. AlphaGo Zero membuktikan bahwa hanya menggunakan self-play juga dapat mencapai level superhuman.


Perspektif Game Theory

Nash Equilibrium

Dalam game theory, Nash Equilibrium adalah keadaan stabil: dalam keadaan ini, tidak ada pemain yang memiliki motivasi untuk mengubah strategi secara sepihak.

Untuk zero-sum, perfect information game seperti Go, Nash equilibrium memiliki makna khusus:

π=argmaxπminπV(π,π)\pi^* = \arg\max_\pi \min_{\pi'} V(\pi, \pi')

Di mana V(π,π)V(\pi, \pi') adalah nilai ekspektasi ketika strategi π\pi melawan strategi π\pi'.

Inilah Prinsip Minimax yang terkenal: Strategi terbaik adalah yang berkinerja terbaik dalam situasi terburuk.

Self-Play dan Nash Equilibrium

Secara teoretis, jika self-play dapat konvergen, ia harus konvergen ke Nash equilibrium. Untuk permainan deterministik seperti Go, Nash equilibrium adalah permainan sempurna.

Tetapi ruang state Go terlalu besar (1017010^{170}), kita tidak mungkin menemukan Nash equilibrium yang sebenarnya. Self-play sebenarnya mendekati equilibrium ini.

Fictitious Play

Self-play terkait dengan konsep fictitious play dalam game theory:

  1. Setiap pemain mengamati strategi historis lawan
  2. Menghitung distribusi rata-rata strategi lawan
  3. Memilih respons terbaik terhadap distribusi rata-rata ini

Dalam kondisi tertentu, fictitious play dapat dibuktikan akan konvergen ke Nash equilibrium.

Self-play AlphaGo dapat dilihat sebagai implementasi neural network dari konsep ini.


Mekanisme Self-Play

Alur Dasar

Alur self-play AlphaGo:

Algoritma: Self-Play Training

Inisialisasi: Policy Network π_θ (dapat dimulai dari supervised learning atau inisialisasi acak)

Ulangi langkah berikut hingga konvergen:

1. Generate data permainan
Untuk i = 1 hingga N (paralel):
a. Gunakan policy saat ini π_θ untuk satu permainan self-play
b. Kumpulkan trajectory: τ_i = (s_0, a_0, r_1, s_1, a_1, ...)
c. Catat hasil akhir z_i ∈ {-1, +1}

2. Update policy
a. Hitung policy gradient:
∇J = (1/N) Σ_i Σ_t ∇_θ log π_θ(a_t|s_t) · z_i
b. Update parameter: θ ← θ + α · ∇J

3. Update value network
a. Latih Value Network dengan pasangan (s, z)
b. Minimalkan: L = E[(V_φ(s) - z)²]

4. Opsional: Evaluasi dan simpan checkpoint
a. Biarkan policy baru melawan versi lama
b. Jika win rate > 55%, update pool lawan

Generasi Data Pelatihan

Setiap self-play menghasilkan trajectory:

τ=(s0,a0,s1,a1,,sT,z)\tau = (s_0, a_0, s_1, a_1, \ldots, s_T, z)

Di mana:

  • sts_t: State papan di langkah waktu tt
  • ata_t: Tindakan yang dipilih di langkah waktu tt
  • zz: Hasil akhir (+1 menang, -1 kalah)

Satu permainan 200 langkah menghasilkan 200 sampel pelatihan. Ratusan ribu self-play per hari, jumlah data pelatihan sangat besar.

Update Policy

Menggunakan policy gradient untuk update Policy Network:

θθ+αθE[tlogπθ(atst)z]\theta \leftarrow \theta + \alpha \cdot \nabla_\theta \mathbb{E}\left[\sum_t \log \pi_\theta(a_t|s_t) \cdot z\right]

Efek update ini:

  • Jika akhirnya menang (z=+1z = +1), tingkatkan probabilitas semua langkah
  • Jika akhirnya kalah (z=1z = -1), kurangi probabilitas semua langkah

Ini terlihat kasar—permainan yang menang mungkin juga memiliki langkah buruk, permainan yang kalah mungkin juga memiliki langkah bagus. Tetapi melalui statistik sejumlah besar permainan, "noise" ini akan dirata-ratakan, langkah yang benar-benar bagus akan diidentifikasi.

Pelatihan Value Network

Value Network menggunakan regression untuk pelatihan:

ϕϕβϕE[(Vϕ(s)z)2]\phi \leftarrow \phi - \beta \cdot \nabla_\phi \mathbb{E}\left[(V_\phi(s) - z)^2\right]

Ini membuat Value Network belajar memprediksi: Mulai dari posisi saat ini, berapa probabilitas menang akhirnya?

Peran Value Network adalah:

  1. Menyediakan evaluasi leaf node di MCTS
  2. Sebagai baseline untuk policy gradient
  3. Langsung digunakan untuk evaluasi posisi

Pentingnya Randomisasi

Menghindari Siklus Deterministik

Jika self-play sepenuhnya deterministik, mungkin terjebak dalam siklus:

Strategi A selalu memainkan pembukaan tetap
Strategi A melawan strategi A selalu menghasilkan permainan yang sama
Hanya satu permainan yang dipelajari berulang kali
AI tidak dapat mengeksplorasi kemungkinan lain

Inilah mengapa randomisasi sangat penting dalam self-play.

Sumber Randomisasi

Cara AlphaGo memperkenalkan randomisasi dalam self-play:

1. Policy network itu sendiri stokastik

Policy Network menghasilkan distribusi probabilitas, bukan pilihan deterministik:

aπθ(as)a \sim \pi_\theta(a|s)

Posisi yang sama, setiap kali mungkin memilih langkah berbeda.

2. Parameter suhu

Menggunakan suhu (temperature) lebih tinggi saat pelatihan untuk meningkatkan keragaman:

πτ(as)=πθ(as)1/τaπθ(as)1/τ\pi_\tau(a|s) = \frac{\pi_\theta(a|s)^{1/\tau}}{\sum_{a'} \pi_\theta(a'|s)^{1/\tau}}

  • τ>1\tau > 1: Lebih acak, lebih banyak exploration
  • τ<1\tau < 1: Lebih deterministik, lebih banyak exploitation
  • τ=1\tau = 1: Distribusi asli

3. Dirichlet Noise

AlphaGo Zero menambahkan Dirichlet noise ke prior probability di root node saat self-play:

P(s,a)=(1ε)πθ(as)+εηaP(s, a) = (1 - \varepsilon) \cdot \pi_\theta(a|s) + \varepsilon \cdot \eta_a

Di mana ηDir(α)\eta \sim \text{Dir}(\alpha), ε=0.25\varepsilon = 0.25, α=0.03\alpha = 0.03 (untuk 361 tindakan Go).

Ini memastikan bahkan langkah dengan probabilitas sangat rendah memiliki kesempatan untuk dieksplorasi.

Metode Pool

Cara lain meningkatkan keragaman adalah mempertahankan pool:

Pool = [π_1, π_2, π_3, ..., π_k] (versi strategi berbeda)

Setiap permainan:
1. Pilih lawan secara acak dari pool
2. Bermain melawan lawan tersebut
3. Update strategi saat ini dengan hasil
4. Secara berkala tambahkan strategi yang diperbaiki ke pool

Manfaat metode ini:

  • Keragaman: Lawan dengan gaya berbeda
  • Stabilitas: Menghindari overfitting ke lawan tertentu
  • Robustness: Belajar menghadapi berbagai strategi

AlphaGo versi asli dan AlphaGo Zero keduanya menggunakan teknik serupa.


Kurva Pertumbuhan Kekuatan

Sistem Rating Elo

Untuk melacak perubahan kekuatan AI, AlphaGo menggunakan Sistem Rating Elo.

Prinsip dasar sistem Elo:

P(A menang)=11+10(RBRA)/400P(\text{A menang}) = \frac{1}{1 + 10^{(R_B - R_A)/400}}

Di mana RAR_A dan RBR_B adalah skor Elo kedua pihak.

  • Selisih 200: Yang lebih kuat diharapkan menang 75%
  • Selisih 400: Yang lebih kuat diharapkan menang 90%
  • Selisih 800: Yang lebih kuat diharapkan menang 99%

Pertumbuhan Kekuatan AlphaGo

Mari visualisasikan pertumbuhan kekuatan berbagai versi AlphaGo:

載入中...

Analisis Kecepatan Pertumbuhan

Dari kurva dapat diamati beberapa fenomena menarik:

1. Pertumbuhan cepat di awal

Dalam beberapa jam pertama pelatihan, AI mempelajari aturan dasar dan taktik sederhana. Ini adalah fase buah yang mudah dipetik—terlalu banyak kesalahan jelas yang dapat diperbaiki.

2. Pertumbuhan stabil di tengah

Setelah kesalahan dasar dihilangkan, AI mulai mempelajari taktik dan joseki yang lebih halus. Kecepatan pertumbuhan melambat, tetapi tetap stabil.

3. Pertumbuhan melambat di akhir

Ketika AI sudah sangat kuat, peningkatan lebih lanjut menjadi sulit. Mungkin perlu menemukan strategi yang sepenuhnya baru, bukan hanya memperbaiki kesalahan.

Momen Melampaui Manusia

Milestone kunci dalam kurva pelatihan AlphaGo:

MilestoneSetara denganWaktu Pencapaian
Melampaui amatir kuatElo ~2700Sekitar 3 jam
Melampaui Fan HuiElo ~3500Sekitar 36 jam
Melampaui Lee SedolElo ~4500Sekitar 60 jam
Melampaui AlphaGo asliElo ~5000Sekitar 72 jam

Angka-angka ini (dari AlphaGo Zero) mengejutkan: AI melampaui kebijaksanaan Go ribuan tahun manusia dalam 3 hari dari nol.


Analisis Konvergensi

Apakah Self-Play Konvergen?

Ini adalah pertanyaan teoretis penting. Jawaban singkatnya adalah: Dalam kondisi tertentu ya, tetapi Go terlalu kompleks, kita tidak dapat membuktikannya secara ketat.

Jaminan Teoretis

Untuk permainan yang lebih sederhana (seperti tic-tac-toe), dapat dibuktikan:

  1. Eksistensi: Nash equilibrium ada (Teorema Minimax)
  2. Konvergensi: Algoritma tertentu (seperti fictitious play) akan konvergen ke Nash equilibrium

Untuk Go, kita tidak memiliki jaminan konvergensi yang ketat, tetapi bukti eksperimental menunjukkan:

  • Kekuatan terus meningkat
  • Tidak ada osilasi atau degradasi yang jelas
  • Kekuatan akhir melampaui semua manusia yang dikenal

Mode Kegagalan yang Mungkin

Masalah yang mungkin ditemui self-play:

1. Strategy Cycling

Strategi A mengalahkan strategi B
Strategi B mengalahkan strategi C
Strategi C mengalahkan strategi A

Ini memang terjadi di beberapa permainan (seperti batu gunting kertas). Tetapi Go memiliki kompleksitas yang cukup, siklus murni seperti ini tampaknya tidak terjadi.

2. Overfitting ke Diri Sendiri

AI mungkin mempelajari strategi yang hanya ditargetkan untuk gaya sendiri, dan tidak dapat menghadapi lawan dengan gaya berbeda. Inilah mengapa AlphaGo bermain melawan berbagai versi dirinya sendiri, dan akhirnya diuji dengan pemain manusia.

3. Optimum Lokal

AI mungkin terjebak di optimum lokal—strategi yang "cukup bagus tapi bukan terbaik". Randomisasi dan banyak permainan membantu menghindari masalah ini.

Pengamatan Aktual

Dari proses pelatihan AlphaGo diamati:

  1. Kemajuan berkelanjutan: Skor Elo terus naik seiring pelatihan
  2. Tidak ada degradasi: Tidak ada situasi kekuatan turun tiba-tiba
  3. Evolusi gaya: Gaya bermain AI berubah secara bertahap seiring pelatihan
  4. Penemuan joseki baru: AI menemukan pembukaan dan taktik yang belum pernah digunakan manusia

Pengamatan ini menunjukkan bahwa meskipun kita tidak memiliki jaminan teoretis, self-play memang efektif dalam praktik.


Detail Implementasi

Parallel Self-Play

Untuk mempercepat pelatihan, AlphaGo menggunakan self-play paralel skala besar:

Keputusan desain kunci:

  • Synchronous vs Asynchronous: AlphaGo menggunakan update asynchronous, Worker tidak perlu menunggu satu sama lain
  • Frekuensi update: Update parameter setelah menyelesaikan N permainan
  • Pemilihan lawan: Pilih secara acak salah satu dari beberapa versi terakhir sebagai lawan

Strategi Checkpoint

Simpan checkpoint model secara berkala untuk:

  1. Pool: Mempertahankan versi lawan yang berbeda
  2. Evaluasi: Melacak perubahan kekuatan
  3. Pemulihan kegagalan: Dapat melanjutkan jika pelatihan terputus
# Pseudocode
def training_loop():
for iteration in range(num_iterations):
# Generate data permainan
trajectories = parallel_self_play(current_policy, num_games=1000)

# Update policy
update_policy(trajectories)

# Evaluasi dan simpan secara berkala
if iteration % 100 == 0:
elo = evaluate_against_pool(current_policy)
save_checkpoint(current_policy, elo)

if elo > best_elo:
add_to_pool(current_policy)
best_elo = elo

Kebutuhan Sumber Daya Pelatihan

Skala pelatihan AlphaGo mengesankan:

VersiHardwareWaktu PelatihanJumlah Self-Play
AlphaGo Fan176 GPUBeberapa bulan~30M
AlphaGo Lee48 TPUBeberapa minggu~30M
AlphaGo Zero4 TPU3 hari~5M
AlphaGo Zero (versi 40 hari)4 TPU40 hari~30M

Perhatikan AlphaGo Zero mencapai kekuatan lebih tinggi dengan hardware lebih sedikit dan waktu lebih singkat—ini adalah peningkatan efisiensi algoritma.

Pengaturan Hyperparameter

Beberapa hyperparameter kunci:

# Pengaturan self-play
NUM_PARALLEL_GAMES = 5000 # Jumlah permainan paralel
GAMES_PER_ITERATION = 25000 # Permainan per iterasi
MCTS_SIMULATIONS = 1600 # Simulasi MCTS per langkah

# Pengaturan pelatihan
BATCH_SIZE = 2048 # Ukuran batch pelatihan
LEARNING_RATE = 0.01 # Learning rate awal
L2_REGULARIZATION = 1e-4 # Weight decay

# Pengaturan exploration
TEMPERATURE = 1.0 # Suhu untuk 30 langkah pertama
DIRICHLET_ALPHA = 0.03 # Parameter Dirichlet noise
EXPLORATION_FRACTION = 0.25 # Rasio noise

Hyperparameter ini disetel melalui banyak eksperimen dan memiliki dampak signifikan pada efek pelatihan.


Varian Self-Play

AlphaGo Versi Asli

Alur pelatihan AlphaGo versi asli:

1. Supervised Learning (SL): Belajar dari catatan manusia
→ Menghasilkan SL Policy Network (π_SL)

2. Reinforcement Learning (RL): Self-play
Inisialisasi π_RL = π_SL
Pool lawan = [π_SL]

Ulangi:
a. π_RL bermain melawan strategi di pool
b. Update π_RL dengan policy gradient
c. Jika π_RL menjadi lebih kuat, tambahkan ke pool

→ Menghasilkan RL Policy Network (π_RL)

3. Pelatihan Value Network:
Generate posisi dengan self-play π_RL
Latih V(s) untuk memprediksi win rate

AlphaGo Zero

AlphaGo Zero menyederhanakan alur ini:

1. Pure self-play (tanpa data manusia)
Inisialisasi jaringan acak f_θ

Ulangi:
a. Self-play dengan MCTS + f_θ
b. Latih policy head dan value head secara bersamaan
c. Update f_θ

→ Satu jaringan menghasilkan policy dan value sekaligus

Perbaikan kunci:

  • Tanpa data manusia: Mulai dari nol
  • Satu jaringan: Policy dan value berbagi fitur
  • Pelatihan lebih ringkas: End-to-end learning

AlphaZero

AlphaZero lebih lanjut menggeneralisasi:

Algoritma yang sama, permainan berbeda:
- Go: Mencapai level melampaui AlphaGo Zero
- Catur: Melampaui Stockfish
- Shogi: Melampaui Elmo

Satu-satunya bagian spesifik permainan: Encoding aturan

Ini membuktikan bahwa self-play adalah paradigma pembelajaran universal, tidak terbatas pada Go.


Apa yang Dipelajari Manusia?

Joseki Baru yang Ditemukan AI

Self-play menghasilkan banyak langkah yang belum pernah digunakan manusia:

1. Inovasi pembukaan

Beberapa pembukaan yang disukai AlphaGo:

  • Invasi 3-3: Menginvasi sudut di awal
  • Langkah tinggi: Secara tradisional dianggap "tidak stabil"
  • Variasi avalanche besar: Manusia menganggap kompleks dan sulit dihitung

2. Penilaian situasi baru

Evaluasi AI terhadap beberapa posisi sangat berbeda dari manusia:

  • Beberapa bentuk yang terlihat "tipis" sebenarnya sangat solid
  • Nilai beberapa "tebal" dilebih-lebihkan
  • Evaluasi ulang terhadap "sente" dan "gote"

Dampak pada Go Manusia

Setelah AlphaGo, Go profesional mengalami perubahan signifikan:

  1. Diversifikasi pembukaan: Pemain profesional mulai menggunakan pembukaan baru yang ditemukan AI
  2. Perubahan metode pelatihan: AI menjadi alat pelatihan utama pemain profesional
  3. Pemikiran ulang teori: Banyak "teori" tradisional dipertanyakan dan diperbaiki
  4. Estetika baru: Mulai mengapresiasi gaya Go AI

Ke Jie berkata setelah kalah dari AlphaGo:

"AlphaGo membuat saya mengenal ulang Go. Dulu saya pikir manusia memahami Go, sekarang saya tahu kita hanya menyentuh permukaan."


Refleksi Filosofis

Esensi Pembelajaran

Self-play mengajukan pertanyaan mendalam tentang pembelajaran:

Dari mana pengetahuan berasal?

  • Pembelajaran manusia bergantung pada informasi eksternal (guru, buku, pengalaman)
  • AI self-play hanya memiliki aturan, tanpa pengetahuan eksternal
  • Tetapi tetap dapat "menemukan" pengetahuan—dari mana pengetahuan ini berasal?

Jawabannya mungkin: Pengetahuan tersirat dalam aturan dan struktur permainan. Aturan Go mendefinisikan apa itu langkah bagus, apa itu langkah buruk, self-play hanya mengungkap struktur tersembunyi ini.

Kreativitas dan Penemuan

Ketika AI memainkan "langkah ilahi" (Move 37), apakah itu kreasi atau penemuan?

Satu pandangan: Langkah itu selalu "ada" dalam aturan Go, AI hanya "menemukan"-nya. Pandangan lain: AI "menciptakan" langkah itu, karena tidak ada yang (termasuk AI itu sendiri) tahu sebelumnya.

Pertanyaan ini tidak memiliki jawaban standar, tetapi menantang pemahaman tradisional kita tentang kreativitas.

Posisi Kecerdasan Manusia

Jika AI dapat dari nol, melalui self-play melampaui kebijaksanaan ribuan tahun manusia, apa artinya bagi manusia?

Pandangan optimis:

  • AI adalah alat yang diciptakan manusia
  • Penemuan AI dapat meningkatkan pemahaman manusia
  • Manusia dapat berkolaborasi dengan AI, mencapai level lebih tinggi

Pandangan hati-hati:

  • Di beberapa bidang, komputasi murni mungkin melampaui intuisi manusia
  • Perlu memikirkan ulang nilai "keahlian profesional"
  • Metode pendidikan dan pelatihan mungkin perlu berubah

Korespondensi Animasi

Konsep inti dalam artikel ini dan nomor animasi terkait:

NomorKonsepKorespondensi Fisika/Matematika
E5Siklus self-playIterasi titik tetap
E6Evolusi strategiDinamika evolusi

Ringkasan

Self-play adalah salah satu teknologi kunci keberhasilan AlphaGo. Kita telah mempelajari:

  1. Mengapa efektif: Adversarial learning, penemuan kelemahan bertahap
  2. Mekanisme: Pengumpulan trajectory, policy gradient, pelatihan value network
  3. Randomisasi: Parameter suhu, Dirichlet noise, pool
  4. Pertumbuhan kekuatan: Sistem Elo, analisis kurva pertumbuhan
  5. Konvergensi: Jaminan teoretis dan pengamatan aktual
  6. Detail implementasi: Pelatihan paralel, strategi checkpoint, hyperparameter

Di artikel berikutnya, kita akan mengeksplorasi bagaimana AlphaGo menggabungkan neural network dengan MCTS, memanfaatkan kelebihan keduanya.


Bacaan Lanjutan


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. Silver, D., et al. (2018). "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play." Science, 362(6419), 1140-1144.
  4. Heinrich, J., & Silver, D. (2016). "Deep Reinforcement Learning from Self-Play in Imperfect-Information Games." arXiv preprint.
  5. Lanctot, M., et al. (2017). "A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning." NeurIPS.