Alpha Dogs' Tricks: Monte Carlo Algorithm, setelah membaca, Anda mengerti!

Algorithm Monte Carlo, yang bisa Anda lihat!

Pada tanggal 9-15 Maret tahun ini, sebuah peristiwa besar terjadi di dunia go-go, yaitu pertempuran antara manusia dan mesin yang berlangsung selama lima putaran di Seoul, Korea Selatan. Hasilnya adalah kekalahan manusia, dengan juara dunia Go-Go Lee Seok-Soo akhirnya kalah 1-4 dari program kecerdasan buatan Google AlphaGo. Jadi apa AlphaGo, dan di mana kunci untuk menang? Di sini kita akan mempelajari algoritma: algoritma Monte Carlo.

• AlphaGo dan algoritma Monte Carlo

Menurut Xinhua, program AlphaGo adalah sebuah program Go-game manusia-robot yang dikembangkan oleh tim DeepMind milik Google di Amerika Serikat.

Dalam artikel sebelumnya, kami telah membahas algoritma jaringan saraf yang sedang dikembangkan Google untuk memungkinkan mesin belajar secara mandiri, seperti AlphaGo.

Wakil Ketua, Sekretaris, Asosiasi Otomatisasi Tiongkok Wang Feiyu mengatakan bahwa para programmer tidak perlu mahir dalam permainan Go, mereka hanya perlu memahami aturan dasar Go. Di balik AlphaGo ada sekelompok ilmuwan komputer terkemuka, tepatnya, ahli dalam bidang pembelajaran mesin. Para ilmuwan menggunakan algoritma jaringan saraf untuk memasukkan catatan pertandingan ahli permainan ke komputer, dan membiarkan komputer bermain sendiri, terus berlatih dalam prosesnya.

Jadi, di mana kunci untuk membuat AlphaGo belajar sendiri menjadi jenius?

Apa itu algoritma Monte Carlo?Dalam artikel ini, kita akan membahas beberapa cara yang paling populer untuk menjelaskan algoritma Monte Carlo: Jika ada 1000 buah apel di keranjang, maka Anda dapat memilih yang terbesar setiap kali Anda menutup mata. Jadi, Anda dapat menutup mata dan memilih secara acak, kemudian memilih secara acak satu dengan bandingkan dengan yang pertama, meninggalkan yang besar, kemudian memilih secara acak satu lagi, dibandingkan dengan yang tersisa sebelumnya, dan Anda dapat meninggalkan yang besar.

Dengan kata lain, algoritma Monte Carlo adalah bahwa semakin banyak sampel, semakin banyak solusi terbaik yang dapat ditemukan, tetapi tidak menjamin bahwa itu adalah yang terbaik, karena jika ada 10.000 buah apel, kemungkinan besar akan ada yang lebih besar.

Di sisi lain, ada juga yang mengatakan bahwa mereka tidak akan bisa melakukan hal yang sama. Secara umum, jika ada sebuah kunci, ada 1000 kunci untuk dipilih, tetapi hanya satu yang benar. Jadi setiap kali Anda mencoba membuka kunci secara acak, Anda harus mengganti satu lagi. Semakin banyak kali Anda mencoba, semakin besar peluang untuk membuka kunci terbaik, tetapi sebelum Anda membukanya, kunci yang salah tidak berguna.

Jadi algoritma Las Vegas adalah solusi terbaik, tetapi tidak mungkin ditemukan. Misalkan dari 1.000 kunci, tidak ada kunci yang dapat dibuka, kunci sebenarnya adalah kunci ke-1001, tetapi tidak ada algoritma ke-1001 dalam sampel, maka algoritma Las Vegas tidak dapat menemukan kunci untuk membuka kunci.

Algoritma Monte Carlo AlphaGoKesulitan go-go sangat besar bagi AI, karena terlalu banyak cara bermain go-go, sehingga sulit bagi komputer untuk memahaminya. Yang pertama, kemungkinan go-go terlalu banyak. Pada setiap langkah go-go, ada banyak kemungkinan, 19 × 19 = 361 pilihan permainan. Dalam 150 putaran go-go, ada hingga 10.170 situasi yang mungkin terjadi. Yang kedua, aturan terlalu halus, dan dalam beberapa hal, pilihan permainan bergantung pada intuisi yang terbentuk dari pengalaman.

Dan AlphaGo bukan hanya sebuah algoritma Monte Carlo, melainkan merupakan sebuah upgrade dari algoritma Monte Carlo.

AlphaGo menggunakan algoritma pencarian pohon Monte Carlo dan dua jaringan saraf mendalam untuk menyelesaikan permainan catur. Sebelum melawan Lee Siwon, Google pertama melatih jaringan saraf Alpha Go dengan hampir 30 juta langkah manusia terhadap tikus untuk memprediksi bagaimana pemain profesional manusia akan jatuh. Lebih jauh lagi, AlphaGo bermain catur dengan dirinya sendiri, menghasilkan skema baru yang besar.

Tugas mereka adalah untuk bekerja sama dan memilih langkah-langkah yang lebih menjanjikan, membuang kesalahan yang jelas, dan dengan demikian mengendalikan perhitungan dalam batas yang dapat dilakukan oleh komputer. Pada dasarnya, ini sama seperti yang dilakukan oleh pemain manusia.

Riset dari Institut Otomatisasi Akademi Ilmu Pengetahuan Cina, Yi Jianqiang, mengatakan bahwa perangkat lunak permainan catur tradisional, yang umumnya menggunakan pencarian kekerasan, termasuk komputer biru dalam, adalah membangun pohon pencarian untuk semua hasil yang mungkin (setiap hasil adalah buah di pohon) dan melakukan pencarian melalui, sesuai kebutuhan. Metode ini juga memiliki kelayakan tertentu dalam hal catur, catur, dll, tetapi tidak dapat dilakukan untuk Go, karena setiap 19 garis Go yang berputar, kemungkinan jatuhnya sangat besar sehingga komputer tidak dapat membangun buah pohon ini (terlalu banyak) untuk melakukan pencarian melalui. AlphaGo menggunakan metode yang sangat cerdas, yang menyelesaikan masalah ini dengan sempurna.

Dia juga menjelaskan bahwa satu unit paling mendasar dari jaringan saraf mendalam mirip dengan neuron di otak manusia, dengan banyak lapisan yang terhubung seolah-olah itu adalah jaringan saraf otak manusia.

Jaringan strategi ini digunakan untuk menghasilkan strategi permainan. Dalam permainan catur, catur tidak berpikir tentang apa yang seharusnya terjadi pada dirinya sendiri, tetapi tentang apa yang akan terjadi pada pemain terbaik manusia. Dengan kata lain, catur akan memprediksi di mana langkah berikutnya akan terjadi, berdasarkan keadaan saat ini dari catur yang masuk, dan mengajukan beberapa cara yang paling sesuai dengan pemikiran manusia.

Namun, jaringan strategi tidak tahu apakah langkahnya itu baik atau buruk, hanya tahu apakah langkahnya sama dengan manusia, saat itu jaringan harus dinilai untuk berperan.

Dia mengatakan: "Jaringan nilai tangkas akan mengevaluasi situasi seluruh piringan untuk setiap kemungkinan yang mungkin, dan kemudian memberikan angka menang tangkas". Nilai-nilai ini akan diteruskan ke algoritme pencarian pohon Monte Carlo, yang dengan mengulangi proses seperti di atas, akan menduga jalan yang memiliki angka menang paling tinggi.

AlphaGo menggunakan kedua alat ini untuk menganalisis situasi dan menilai kelebihan dan kekurangan dari setiap strategi berikutnya, seperti halnya pemain manusia yang menilai situasi saat ini dan menyimpulkan situasi di masa depan. Dengan menggunakan algoritma pencarian pohon Monte Carlo, mereka dapat menentukan di mana kemungkinan menang di masa depan akan lebih tinggi.

Namun, tidak ada keraguan bahwa algoritma Monte Carlo adalah salah satu inti dari AlphaGo.

Dua Eksperimen Kecil Akhirnya, lihatlah dua eksperimen kecil dari algoritma Monte Carlo.

• 1.计算圆周率pi。

Prinsip: Pertama gambarkan sebuah persegi, gambarkan lingkaran di dalamnya, kemudian gambar titik acak di dalam persegi ini, atur titik yang jatuh di dalam lingkaran sekitar P, maka P = luas lingkaran / luas persegi. P = ((Pi)RR) / ((2R*2R) = Pi/4, yaitu Pi = 4P

Langkah-langkah: 1. Letakkan pusat lingkaran di titik awal, dan buat lingkaran dengan R sebagai radius, maka luas lingkaran 1/4 dari kuadrat pertama adalah PiRR/4 2. Buat persegi panjang yang mengelilingi lingkaran 1/4, koordinatnya adalah ((0,0) ((0,R) ((R,0) ((R,R), maka luas persegi panjangnya adalah RR 3. Mengambil titik (x, y), sehingga 0 <= X <= R dan 0 <= Y <= R, yaitu titik di dalam kuadrat 4. Menggunakan rumus XX+YYTentukan apakah titik R berada dalam lingkaran 1/4. 5. Tentukan bahwa semua titik (misalnya, jumlah percobaan) adalah N, dan jumlah titik (misalnya, titik yang memenuhi langkah 4) yang berada di dalam lingkaran 1/4, adalah M.

Jadi kita bisa mengatakan bahwa P adalah M/N, jadi Pi adalah 4 kali N/M.Gambar 1

M_C ((10000) berjalan dengan hasil 3.1424

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

# Pada interval [-2,2] menghasilkan sebuah angka secara acak, mencari y yang sesuai, dan mencari yang terbesar yang dianggap sebagai nilai terbesar pada fungsi pada [-2,2]Gambar 2

Setelah 1000 kali simulasi, ditemukan nilai maksimum 185.12292832389875 ((sangat akurat)

Jika Anda melihat di sini, Anda mengerti. Anda dapat menulis kode dengan tangan. Diarsipkan dari WeChat