Prinsip Dasar Pencarian Graf Monte Carlo
- Monte Carlo Tree Search (MCTS), ketika diterapkan pada graf berarah alih-alih pohon, menjadi "Monte Carlo Graph Search" ("MCGS"), yang terkadang dianggap sulit diimplementasikan.
- Referensi akademik yang ada mengikuti penjelasan "standar" MCTS untuk pohon, sehingga sulit memahami secara konseptual bagaimana menggeneralisasikannya ke graf.
- Dokumen ini menyajikan penjelasan yang dianggap lebih intuitif, yang pada dasarnya setara tetapi lebih rapi, dan menurunkannya dari prinsip dasar untuk menjelaskan mengapa pencarian graf harus bekerja dengan cara ini.
Pengantar / Latar Belakang
- Dalam pencarian pohon permainan atau aplikasi pencarian pohon lainnya, mungkin ada beberapa urutan langkah atau aksi yang berbeda tetapi berujung pada keadaan yang sama.
- Misalnya, dalam catur,
1. d4 d5 2. Nf3 berujung pada posisi yang sama dengan 1. Nf3 d5 2. d4.
- Saat situasi seperti ini dimungkinkan dalam permainan, jumlah kemungkinan bertambah secara eksponensial seiring kedalaman pencarian, sehingga pencarian mendalam menjadi lebih mahal dari yang seharusnya.
- Idealnya, kita ingin cabang-cabang pencarian semacam ini berbagi perhitungan.
- Namun, implementasi MCTS standar memperlakukan permainan sebagai pohon bercabang dan secara tidak efisien menelusuri ulang posisi yang duplikat di dalam pohon.
Penjelasan Umum MCTS - Pohon Statistik Berjalan
- MCTS sering dijelaskan sebagai algoritma yang melacak statistik berjalan dari playout yang melewati node-node pohon.
- Setiap node merepresentasikan satu keadaan permainan, dan melacak jumlah kunjungan (N) serta rata-rata berjalan (Q) dari nilai utilitas yang disampling oleh playout.
- Satu iterasi atau playout MCTS terdiri dari menuruni pohon sambil mengambil sampel aksi berikutnya untuk dieksplorasi, memperluas pohon saat mencapai keadaan baru, mengestimasi utilitas U dari keadaan baru, lalu naik kembali ke atas pohon sambil menaikkan N pada tiap node dan memperbarui rata-rata Q dengan utilitas baru U yang disampling.
Apa yang Salah pada Graf?
- Jika algoritma di atas diterapkan begitu saja pada graf berarah asiklik alih-alih pohon, algoritmanya bisa menjadi tidak akurat.
- Hal ini karena MCTS umumnya dijelaskan dalam kerangka statistik berjalan dari playout sebagai perluasan dari metode berbasis multi-armed bandit.
- Czech, Korus, dan Kersting menyelesaikan masalah ini dan mencapai algoritma yang sound, tetapi ada pendekatan alternatif yang memandang MCTS dari perspektif pembelajaran kebijakan online.
- Dalam penjelasan alternatif ini, generalisasi ke graf muncul secara relatif alami.
Melihat Ulang MCTS sebagai Optimisasi Kebijakan yang Dinormalisasi
- Ketika MCTS memperbarui statistik pada node-node berbeda, pada dasarnya ia sedang menjalankan suatu bentuk pembelajaran kebijakan online.
- Distribusi kunjungan MCTS secara kasar merepresentasikan kebijakan "posterior" yang secara bertahap memperbaiki prior policy P dari jaringan saraf untuk memaksimalkan utilitas yang diharapkan.
Menjalankan Pencarian Graf Monte Carlo yang Benar
- Semua masalah yang muncul saat memperluas MCTS ke graf berasal dari asumsi bahwa kunjungan anak node hanya datang dari parent node.
- Teori menjamin bahwa jumlah aksi kumulatif yang dipilih oleh PUCT menyediakan kebijakan posterior yang mendekati kebijakan optimal π, sehingga inilah yang perlu dilacak.
- Dengan menggunakan interpretasi bahwa nilai Q yang dilaporkan node adalah nilai harapan dari kebijakan posterior, kita dapat menerapkan rumus Q rekursif tanpa harus membahas cara menghitung playout individual.
Diskusi tentang Pilihan Implementasi
- Algoritma yang disajikan dalam dokumen ini sangat mirip dengan algoritma milik Czech, Korus, dan Kersting, tetapi ada beberapa pilihan implementasi dan beberapa perbedaan kecil.
- Ada berbagai cara yang bisa dipilih demi kesederhanaan implementasi, seperti strategi untuk mengurangi "keusangan" nilai Q atau menggunakan pembaruan yang sama secara serentak alih-alih bertahap.
Opini GN⁺
- Artikel ini dapat menarik minat orang-orang yang tertarik pada bidang kecerdasan buatan dan teori permainan dengan menyajikan kompleksitas Monte Carlo Graph Search (MCGS) serta pendekatan baru untuk memahaminya.
- Algoritma seperti MCTS memainkan peran penting dalam permainan strategi kompleks seperti catur dan Go, serta berkontribusi pada pengembangan AI untuk permainan-permainan tersebut.
- Namun, materi yang dibahas dalam artikel ini bisa terasa cukup sulit bagi software engineer tingkat pemula dan memerlukan latar belakang teori.
- Hal yang perlu dipertimbangkan saat mengimplementasikan MCGS adalah bagaimana menyeimbangkan efisiensi dan akurasi algoritma, yang dapat sangat memengaruhi performa di lingkungan permainan nyata.
- Proyek atau produk lain dengan fungsi serupa mencakup AlphaZero dari DeepMind, yang telah mencapai tingkat melampaui pemain manusia terbaik dalam catur, Go, dan shogi.
1 komentar
Komentar Hacker News
Penelusuran graf diperlukan untuk kemajuan penalaran AI, dan LLM sederhana akan gagal. Tautannya memuat banyak referensi bagus, termasuk hashing Zobrist untuk tabel permainan. Kita perlu menemukan hashing yang baik untuk deskripsi status berbasis bahasa agar penelusuran graf tidak meledak secara komputasional. Bacaan yang bagus tentang penelusuran pohon adalah 'Thinking Fast and Slow' dan 'Teaching Large Language Models to Reason with Reinforcement Learning', yang membandingkan pendekatan MCTS dengan strategi RL lain saat ini.
Saya langsung mengenali pengembang jenius KataGo dari URL HN. Postingan Reddit-nya di cbaduk secara konsisten luar biasa.
Mengenai nama "Monte-Carlo Tree Search", pembaca perlu menyadari bahwa tidak ada unsur "Monte-Carlo" dalam algoritme yang disebutkan dan algoritme itu sepenuhnya deterministik. Fakta bahwa MCTS umumnya diimplementasikan secara deterministik terasa aneh. Saya semula mengira ada keacakan dalam sampling.
Makalah yang disebutkan benar-benar luput dari radar saya saat mempelajari MCTS. Akan sangat menyenangkan mencoba modifikasi ini pada kesempatan berikutnya.
Pengetahuan latar: