Bagaimana cara "pencarian Monte-Carlo" bekerja?

16

Saya telah mendengar tentang konsep ini dalam posting Reddit tentang Alpha Go. Saya sudah mencoba membaca makalah dan artikelnya, tetapi tidak bisa memahami algoritma.

Jadi, dapatkah seseorang memberikan penjelasan yang mudah dimengerti tentang bagaimana algoritma pencarian Monte-Carlo bekerja dan bagaimana itu digunakan dalam membangun bot AI bermain-game?

gaming monte-carlo-tree-search Dawny33
sumber
Penjelasan yang bagus tentang algoritma MCTS dapat ditemukan di: https://towardsdatascience.com/monte-carlo-tree-search-in-reinforcement-learning-b97d3e743d0f .
nbro

Jawaban:

13

Metode Monte Carlo adalah pendekatan di mana Anda menghasilkan sejumlah besar nilai acak atau simulasi dan membentuk semacam kesimpulan berdasarkan pola umum, seperti cara dan varians.

Sebagai contoh, Anda bisa menggunakannya untuk prakiraan cuaca . Memprediksi cuaca jangka panjang cukup sulit, karena ini adalah sistem yang kacau dimana perubahan kecil dapat menghasilkan hasil yang sangat berbeda. Dengan menggunakan metode Monte Carlo, Anda dapat menjalankan sejumlah besar simulasi, masing-masing dengan perubahan atmosfer yang sedikit berbeda. Kemudian Anda dapat menganalisis hasil dan misalnya menghitung probabilitas hujan pada hari tertentu berdasarkan berapa banyak simulasi yang berakhir dengan hujan.

Adapun penggunaan Monte Carlo di Alpha Go, mereka tampaknya menggunakan apa yang disebut Pencarian Pohon Monte Carlo . Dalam pendekatan ini, Anda membuat pohon gerakan yang mungkin, beberapa belokan ke masa depan, dan mencoba menemukan urutan terbaik. Namun, karena jumlah gerakan yang memungkinkan dalam permainan go sangat besar, Anda tidak akan dapat menjelajah sangat jauh ke depan. Ini berarti bahwa beberapa gerakan yang terlihat bagus sekarang mungkin berubah menjadi buruk nantinya.

Jadi, di Pencarian Pohon Monte Carlo, Anda memilih urutan bergerak yang menjanjikan dan menjalankan satu atau lebih simulasi tentang bagaimana permainan dapat melanjutkan dari titik itu. Kemudian Anda dapat menggunakan hasil simulasi itu untuk mendapatkan ide yang lebih baik tentang seberapa baik urutan gerakan yang sebenarnya dan Anda memperbarui pohon yang sesuai. Ulangi sesuai kebutuhan sampai Anda menemukan langkah yang baik.

Jika Anda ingin informasi lebih lanjut atau melihat beberapa ilustrasi, saya menemukan makalah yang menarik tentang topik: C. Browne et al., Survei Metode Pencarian Pohon Monte Carlo ( repositori terbuka / tautan permanen (paywalled) )

Lurker Disenchanted
sumber
Jadi pada dasarnya apa yang dilakukan monte carlo di alphago adalah menciptakan strategi jangka panjang, dengan mempertimbangkan kombinasi langkah yang berbeda, dan bukan sebaliknya (pilih strategi dan kemudian langkah untuk mencapainya)?
Diego Antonio Rosario Palomino
Tidak disebutkan elemen kunci dari pendekatan Monte Carlo, yang merupakan elemen stokastik terintegrasi ke dalam pemilihan langkah yang tersedia untuk diselidiki. Tidak ada trade-off dari ketepatan untuk mencapai pemrosesan yang lebih ramping yang disebutkan. Itulah dua aspek terpenting dan tidak ada jawabannya. Sebaliknya, "sejumlah besar nilai acak atau simulasi," disebutkan, ketika itu adalah sejumlah kecil simulasi dari faktor pseudo-acak (pencarian yang kurang lengkap) yang merupakan karakteristik dari konvergensi Monte Carlo.
FauChristian