Alpha Dog's Tricks: Algorithm Monte Carlo, baca dan faham!

Perisian anjing alpha: Algorithm Monte Carlo, lihat dan faham!

Pada 9-15 Mac tahun ini, satu peristiwa besar berlaku di dunia gojek, iaitu pertempuran manusia dan mesin yang berlangsung selama lima pusingan di Seoul, Korea Selatan. Hasil pertandingan itu adalah kekalahan manusia, dengan juara dunia gojek, Lee Hsiung, akhirnya kalah 1-4 kepada program kecerdasan buatan Google, AlphaGo. Jadi apa itu AlphaGo, dan di mana kunci untuk menang? Di sini kita akan belajar tentang satu algoritma: algoritma Monte Carlo.

• AlphaGo dan algoritma Monte Carlo

Menurut laporan Xinhua, program AlphaGo adalah program permainan Go yang dikembangkan oleh pasukan DeepMind, sebuah syarikat Google di Amerika Syarikat.

Dalam artikel sebelumnya, kami telah membincangkan algoritma rangkaian saraf yang sedang dibangunkan oleh Google untuk membolehkan mesin belajar secara autonomi, seperti AlphaGo.

Wang Feiyu, Timbalan Pengerusi dan Setiausaha Persatuan Automasi China, berkata bahawa perancang tidak perlu mahir dalam permainan, mereka hanya perlu memahami peraturan asas permainan. Di sebalik AlphaGo adalah sekumpulan saintis komputer yang cemerlang, tepatnya pakar dalam bidang pembelajaran mesin. Para saintis menggunakan algoritma rangkaian saraf untuk memasukkan rekod pertandingan pakar permainan ke dalam komputer, dan membiarkan komputer bermain dengan dirinya sendiri, terus berlatih dalam proses ini.

Jadi, di mana kunci untuk menjadikan AlphaGo pintar? Itulah algoritma Monte Carlo.

Apakah algoritma Monte Carlo?Di sini, saya akan menerangkan bagaimana algoritma Monte Carlo boleh digunakan. Sekiranya terdapat 1000 epal dalam bakul, maka anda boleh memilih yang terbesar setiap kali anda menutup mata anda, dan anda tidak boleh mengehadkan jumlah pilihan anda. Jadi, anda boleh menutup mata anda dan memilih secara rawak satu, kemudian memilih secara rawak satu berbanding dengan yang pertama, meninggalkan yang lebih besar, kemudian memilih secara rawak satu, berbanding dengan yang sebelumnya, dan anda boleh meninggalkan yang lebih besar.

Dengan kata lain, algoritma Monte Carlo adalah bahawa semakin banyak sampel, semakin banyak penyelesaian yang terbaik dapat didapati, tetapi tidak menjamin yang terbaik, kerana jika anda mempunyai 10,000 epal, kemungkinan besar anda akan menemui yang lebih besar.

Di samping itu, ia juga boleh digunakan untuk menghidupkan semula data yang telah dikemas kini di laman web ini. Secara lumrah, jika terdapat kunci, terdapat 1000 kunci untuk dipilih, tetapi hanya satu yang betul. Oleh itu, setiap kali anda mengambil satu kunci secara rawak untuk mencuba, anda tidak dapat membukanya, anda akan menukar satu lagi. Semakin banyak percubaan, peluang terbaik untuk membuka lebih besar, tetapi sebelum membuka, kunci yang salah tidak berguna.

Oleh itu, algoritma Las Vegas adalah penyelesaian yang terbaik, tetapi tidak dapat dijumpai. Misalkan 1000 kunci, tidak ada kunci yang dapat dibuka, kunci sebenar adalah kunci ke-1001, tetapi dalam sampel tidak ada algoritma ke-1001, algoritma Las Vegas tidak dapat mencari kunci untuk membuka kunci.

Algoritma Monte Carlo AlphaGoKesulitan Go adalah sangat besar bagi AI kerana terdapat terlalu banyak cara untuk bermain Go, dan komputer sukar untuk membezakan. Yang pertama, kemungkinan gojek terlalu banyak. Pada setiap langkah gojek, terdapat banyak kemungkinan, pemain mempunyai 19 x 19 = 361 pilihan permainan pada permulaan. Dalam satu putaran 150 putaran gojek, terdapat sehingga 10,170 situasi yang mungkin berlaku. Yang kedua, peraturan terlalu halus, dan ke tahap tertentu, pilihan permainan bergantung pada naluri yang terbentuk melalui pengalaman.

AlphaGo juga bukan sekadar algoritma Monte Carlo, malah ia adalah versi peningkatan dari algoritma Monte Carlo.

AlphaGo berjaya menyelesaikan permainan catur dengan menggunakan algoritma carian pokok Monte Carlo dan dua rangkaian saraf mendalam. Sebelum bertanding dengan Lee Siwon, Google mula-mula melatih rangkaian saraf Alpha Go dengan hampir 30 juta langkah manusia terhadap ketam untuk mengajarnya untuk meramalkan bagaimana pemain profesional manusia akan jatuh. Kemudian lebih jauh lagi, membiarkan AlphaGo bermain catur dengan dirinya sendiri, yang menghasilkan satu lagi skematik baru yang besar.

Tugas mereka adalah untuk memilih langkah-langkah permainan yang lebih berjangka, meninggalkan permainan yang jelas, dan mengawal jumlah pengiraan dalam jumlah yang dapat dilakukan oleh komputer. Pada dasarnya, ini adalah sama seperti yang dilakukan oleh pemain manusia.

Pengkaji Institut Automasi Akademi Sains China, Yi Jianqiang, berkata bahawa perisian permainan catur tradisional, yang biasanya menggunakan carian ganas, termasuk komputer biru biru, adalah untuk membina pokok carian untuk semua hasil yang mungkin (setiap hasil adalah buah di atas pokok) dan melakukan carian melintasi mengikut keperluan. Kaedah ini juga dapat dilaksanakan dalam bidang catur, lompat catur, dan lain-lain, tetapi tidak dapat dilaksanakan untuk gojek, kerana setiap 19 garis gojek yang melintasi, kemungkinan jatuhnya sangat besar sehingga komputer tidak dapat membina buah pokok ini (terlalu banyak) untuk mencapai carian melintasi. AlphaGo menggunakan kaedah yang sangat pintar, menyelesaikan masalah ini dengan sempurna.

Dia juga menjelaskan bahawa unit yang paling asas dalam rangkaian saraf yang mendalam adalah seperti neuron dalam otak manusia, dengan banyak lapisan yang disambungkan seperti rangkaian saraf otak manusia. Kedua-dua rangkaian saraf di AlphaGo adalah rangkaian strategi dan rangkaian penilaian.

Rangkaian strategi permainan ini digunakan untuk menghasilkan strategi kejatuhan. Dalam proses bermain, ia tidak memikirkan bagaimana ia harus bermain, tetapi bagaimana pemain terbaik manusia akan bermain. Dengan kata lain, ia akan menjangkakan di mana permainan seterusnya akan dimainkan oleh manusia berdasarkan keadaan semasa papan permainan.

Walau bagaimanapun, rangkaian strategi tidak tahu sama ada langkah yang akan diambil itu baik atau tidak, ia hanya tahu sama ada langkah itu sama dengan manusia, ketika itu ia perlu menilai rangkaian untuk bertindak.

Mengikut Wangchi, rangkaian penilaian acuan akan menilai keadaan seluruh papan untuk setiap kemungkinan yang mungkin, dan kemudian memberikan acuan peluang kemenangan. Nilai-nilai ini akan dikembalikan kepada algoritma carian pokok Monte Carlo untuk merumuskan jalan yang paling tinggi dengan proses seperti di atas. Algoritma carian pokok Monte Carlo memutuskan bahawa rangkaian strategi hanya akan terus merumuskan di mana peluang kemenangan adalah lebih tinggi, sehingga ia boleh membuang laluan tertentu, tanpa menggunakan satu laluan untuk menjadi hitam.

AlphaGo menggunakan kedua-dua alat ini untuk menganalisis situasi dan menilai kelebihan dan kekurangan setiap strategi seterusnya, seperti pemain chess manusia yang menilai keadaan semasa dan membuat kesimpulan mengenai keadaan masa depan. Dengan menggunakan algoritma carian pokok Monte Carlo untuk menganalisis, contohnya, 20 langkah masa depan, ia dapat menentukan di mana kemungkinan kemenangan seterusnya akan lebih tinggi.

Walau bagaimanapun, tidak ada keraguan bahawa algoritma Monte Carlo adalah salah satu teras AlphaGo.

Dua eksperimen kecil Akhirnya, lihatlah dua eksperimen kecil mengenai algoritma Monte Carlo.

• 1.计算圆周率pi。

Prinsip: Mula-mula lukis sebuah segi empat, lukis bulatan di dalamnya, kemudian lukis titik rawak di dalam segi empat ini, letakkan titik yang jatuh di dalam bulatan kira-kira sebagai P, maka P = kawasan bulatan / kawasan segi empat. P= ((Pi)RR) / ((2R*2R) = Pi/4, iaitu Pi = 4P

Langkah: 1. Letakkan pusat bulatan pada titik asal, dan buat bulatan dengan R sebagai radius, maka kawasan bulatan 1/4 suku pertama ialah PiRR/4 2. Buat persegi luar bulat 1/4, koordinatnya adalah ((0,0) ((0,R) ((R,0) ((R,R), maka luas persegi ini adalah RR 3. Mengambil titik (x, y), sehingga 0 <= X <= R dan 0 <= Y <= R, iaitu titik dalam segi empat. 4. Melalui formula XX+YYR menentukan sama ada titik berada dalam satu perempat lingkaran. 5. Letakkan semua titik (iaitu bilangan percubaan) adalah N, dan bilangan titik (yang memenuhi langkah 4) yang jatuh di dalam satu perempat bulatan adalah M,

P=M/N, jadi Pi=4*N/M.Gambar 1

M_C ((10000) menghasilkan 3.1424

• 2.蒙特卡洛模拟求函数极值，可避免陷入局部极值

# Menghasilkan nombor secara rawak pada julat [-2,2], mencari y yang sepadan, dan mencari nilai terbesar yang dianggap sebagai fungsi pada [-2,2]Gambar 2

Selepas 1000 simulasi, nilai yang sangat tinggi didapati 185.12292832389875 ((sangat tepat)

Lihat di sini, kawan-kawan faham. Kod boleh ditulis dengan tangan, menarik! Dibaharui dari WeChat