Kemudian saya hanya duduk di sana dan mengagumi AlphaZero versus Stockfish . Dan sekarang saya kembali ke topik sehubungan dengan tugas mengoptimalkan jaringan saraf, yang terkadang harus dilakukan di tempat kerja (sayangnya, kurang dari yang kami inginkan). Bagi saya, tugas-tugas ini bisa terkait erat, jadi saya ingin membuat ide-ide saya sistematis.
Catur adalah permainan dengan informasi yang lengkap, berdasarkan pencacahan varian (serta checker, go, dll).
Masalahnya, bagaimanapun, adalah pohon variasi dalam catur tumbuh cukup cepat (meskipun secara signifikan lebih lambat daripada di Go). Misalnya, dengan papan penuh keping dalam posisi tenang, setiap sisi memiliki sekitar 10 kelanjutan yang wajar. Jadi, hanya dalam 3 gerakan hitam putih (6 setengah gerakan) kita bisa mendapatkan satu juta posisi dari yang satu ini. Juga, mari kita pertimbangkan bahwa rata-rata permainan antara orang-orang berlangsung selama 40-50 gerakan (antar komputer - 80-100). Dengan demikian, kita akan sampai pada kesimpulan bahwa penghitungan lengkap pohon varian tidak mungkin dilakukan untuk sebagian besar posisi, yang berarti kita harus fokus pada pemotongan sebagian dari pohon pencarian, baik lebar maupun dalam. Sekarang mari kita lihat bagaimana manusia dan mesin menangani masalah ini. Saya akan mulai dengan sedikit gambaran sejarah.
"Catur Protein".
Catur telah dikenal sekitar 1400 tahun, tetapi turnamen besar pertama di dalamnya mulai diadakan pada pertengahan abad ke-19. Itu adalah saat pertempuran terbuka dan romantis. Lawan mencoba dengan cepat memasukkan bidak ke dalam pertempuran, membuka posisi dan memulai serangan terhadap raja. Tidak ada yang secara khusus mempertimbangkan konsesi material dan posisi. Namun yang cukup mengejutkan, tokoh antagonis catur romantis, Wilhelm Steinitz, menjadi juara dunia resmi pertama .
Dia meletakkan dasar untuk permainan posisi . Sebagian besar berkat Steinitz, kami mulai beroperasi dengan konsep seperti "struktur bidak", "kotak kuat dan lemah", "bidak baik dan buruk". Inilah yang memperkenalkan catur elemen strategi berdasarkan keuntungan jangka panjang. Steinitz mengembangkan pendekatan posisi dan tanpa henti menghukum lawan-lawannya karena pengorbanan materi dan kelemahan posisi. Emmanuel Lasker , yang menggantikannya di takhta catur, berbicara dengan sangat baik tentang juara pertama : " Bakat Steinitz sebagai pemain praktis lebih rendah daripada bakat Blackburn atau Zukertort, yang bagaimanapun dia kalahkan, karena dia adalah pemikir hebat, tetapi sebenarnya tidak ."Steinitz merumuskan prinsip dasar penilaian posisi dan rencana permainan yang dihasilkan dalam bahasa tingkat tinggi (dalam hal ini, Jerman).
Karena itu, dia membuatnya tersedia untuk dipelajari oleh orang lain . Ini telah membentuk apa yang kami sebut pendekatan manusia terhadap catur. Kami sangat serius dalam memangkas pohon variasi dalam catur berdasarkan prinsip posisi. Beberapa gerakan dibuang karena mengarah ke posisi yang buruk di cakrawala yang diperhitungkan. Beberapa karena mereka mengarah pada konsesi jangka panjang, yang lain karena tidak memiliki tujuan. Hasilnya, kami menghitung sebagian kecil dari kemungkinan opsi.
Pemahaman lebih lanjut tentang catur pada dasarnya merupakan pengembangan dari ide-ide yang ditetapkan oleh juara pertama. Konsep seperti blokade, pencegahan, dominasi muncul. Pemain catur mulai mempelajari prinsip-prinsip bermain posisi tipikal yang timbul dari berbagai bukaan (rantai tertutup, pion terisolasi, dll). Dengan satu atau lain cara, posisi yang dekat dengan keseimbangan material dipelajari. Tapi ada juga pengecualian - misalnya, Mikhail Tal muda bermain dengan gaya berbeda. Ia menciptakan posisi tajam yang tidak seimbang dengan pelanggaran rasio material (kemudian Garry Kasparov juga memperagakan permainan serupa). Tidak terbiasa dengan permainan seperti itu, lawan melewati satu demi satu. Tal menjadi juara dunia pada tahun 1960, tetapi kalah dalam pertandingan ulang setahun kemudian. Pada paruh kedua abad kedua puluh, fokus penelitian bergeser ke awal permainan - pembukaan. Dengan tangan ringan dari Mikhail Botvinnik (juara dunia ke-6) dan Garry Kasparov (ke-13), para pecatur mulai mencurahkan sebagian besar waktunya untuk melatih variasi pembukaan tertentu. Semakin banyak menggunakan komputer dalam proses ini. Akibatnya, banyak variasi dalam bukaan populer yang dikembangkan hingga posisi di mana hasil permainan telah ditentukan sebelumnya. Hal ini mengarah pada pelemahan catur tertentu, serta kebutuhan untuk menghafal sejumlah besar variasi agar tidak dikalahkan dalam pembukaan. Tak heran, belakangan ini bandul berayun ke arah berlawanan. Juara dunia saat iniMagnus Carlsen lebih suka bercita-cita untuk tidak mendapatkan keuntungan di akhir pembukaan, tetapi posisi bermain yang tidak "diretas" oleh mesin komputer. Beratnya perjuangan dibawa ke tahap-tahap akhir permainan (permainan tengah, permainan akhir).
"Catur Silikon".
Seperti yang dikatakan Aleksandr Kronrod dengan tepat , catur adalah "lalat buah" dari kecerdasan buatan. Studi mereka dimulai dengan munculnya komputer pertama dan menarik para perintis seperti Alan Turing dan Claude Shannon.... Adalah Shannon yang mengemukakan perkiraan pertama dari nilai bidak catur "Raja = 200, Ratu = 9, Benteng = 5, Uskup = 3, Ksatria = 3, Pion = 1". Anehnya, penilaian sederhana inilah yang menentukan perkembangan pemrograman catur selama 70 tahun ke depan. Shannon juga memprediksikan pembagian program catur menjadi "fast" (brute force) dan "smart" (pintar). Program "Cepat" sepenuhnya membahas semua kemungkinan opsi hingga kedalaman tertentu, mengevaluasi posisi menggunakan fungsi evaluasi sederhana (seperti rasio material) dan memilih langkah terbaik menggunakan prinsip minimax... Program "pintar" menggunakan algoritme yang lebih kompleks dan memvariasikan kedalaman penelusuran dengan cara yang sama seperti yang dilakukan manusia. Juara dunia ke-6 Mikhail Botvinnik terlibat dalam pembuatan algoritme semacam itu di tahun-tahun terakhir hidupnya. Namun, tidak banyak berhasil, seperti banyak pembuat program "pintar" lainnya. Karena dalam prediksi ketiganya, Shannon salah - program "pintar" terus-menerus gagal dalam pertarungan melawan program "cepat". Alasannya adalah bahwa brute force diparalelkan dan dioptimalkan dengan sangat baik. Dan perkiraan sederhana Shannon ternyata cukup stabil dan kuat. Seperti yang diketahui para pecatur, keunggulan posisi apa pun cepat atau lambat akan berubah menjadi materiil. Sementara prinsip-prinsip penilaian posisi memungkinkan formalisasi jauh lebih buruk.
Mereka membutuhkan perhitungan berurutan yang rumit dan tidak dioptimalkan dengan baik. Akibatnya, seiring dengan peningkatan kinerja komputer, program "cepat" mulai mendominasi. Beginilah cara utama catur komputer dibentuk, yang sangat berbeda dari catur manusia - menerobos ke kedalaman tertentu menggunakan pemotongan alfa-beta (dan beberapa heuristik lainnya) dan estimasi posisi menurut Shannon. Juga, program mulai secara aktif mengembangkan dan menggunakan dasar pembukaan (ketika permainan belum jauh dari posisi awal) dan permainan akhir (ketika jumlah bidak kecil dan pohon variasi dapat dihitung sepenuhnya). Dan kinerja komputer tumbuh sepanjang waktu, dan pemrogram juga tidak berdiam diri, terus-menerus mengoptimalkan mesin. Pada 11 Mei 1997, sebuah peristiwa yang membuat zaman terjadiKomputer Deep Blue mengalahkan juara dunia Garry Kasparov dalam 6 pertandingan pertandingan.
Segera setelah itu, IBM menutup proyek yang tidak pernah murah ini. Chip yang mempercepat kalkulasi catur diciptakan khusus untuk Deep Blue ! Namun, bahkan tanpa mereka, keunggulan komputer atas seseorang sudah jelas. Deep Fritz , Deep Junior , Rybka , Komodo , Stockfish mulai menghancurkan grandmaster terkemuka, bahkan memberi mereka materi di depan ... Namun, di antara mereka sendiri, mereka bermain dengan berbagai keberhasilan - hasil kejuaraan dunia antar program dapat ditemukan di sini .
Semuanya berubah ketika pencipta AlphaZero, setelah mengalahkan juara dunia di game of go, Li Sedol , akhirnya belajar catur. Hasilnya fenomenal - setelah 4 jam bermain dengan diri saya sendiriAlphaZero mengalahkan StockFish dengan memenangkan 28 game dan menggambar 72. Setelah setahun, DeepMind melakukan eksperimen yang lebih bersih , memungkinkan Stockfish untuk menggunakan buku pembuka dan akhir game. Meski demikian, hasil +155 -6 = 839 tidak diragukan lagi siapa pemain terkuat di dunia saat ini.
Mari kita pahami bagaimana mengatur keajaiban baru ini. (Sudah ada keseluruhan buku untuk mereka yang ingin menggali lebih dalam skrip python ). Algoritma utama adalah pencarian pohon Monte Carlo... Ini, tentu saja, berlebihan, yang membuat AlphaZero mirip dengan program catur lainnya. Namun kata Monte Carlo tidak boleh menyesatkan - penelusuran dikontrol oleh jaringan neural (untuk Go, lapisannya terdiri dari 80, saya tidak tahu yang mana di sini) dan difokuskan secara sempit. AlphaZero memangkas pohon gaya kasar untuk pertimbangan posisi, seperti yang dilakukan manusia! Dibandingkan dengan Stockfish, Alphazero memiliki opsi yang hampir 1000 kali lebih sedikit... Dia menyekop lebih sedikit "sampah", tetapi menghitung opsi terkuat yang paling mungkin lebih dalam dan lebih akurat. Oleh karena itu, ia menang bahkan dengan waktu yang lebih sedikit atau pada perangkat keras yang lebih lemah. Dan yang paling penting adalah AlphaZero "mempelajari" catur secara eksklusif berdasarkan "pengalamannya sendiri". Dia tidak memiliki informasi a priori. "Pemahamannya" tidak tercemar oleh "penilaian Shannon". Dia memiliki pemahaman uniknya sendiri tentang visi catur dan gaya bermain, yang seringkali mengabaikan keseimbangan materi (seperti Tal muda!).
Kesimpulan apa yang dapat kita tarik dari eksperimen luar biasa ini?
- Dia dengan tegas membantah semua pertimbangan tentang pelemahan catur. Penampilan seorang pemain yang bermain dengan gaya yang belum pernah ada sebelumnya dan menunjukkan keunggulan total atas pesaing menunjukkan bahwa kemungkinan permainan masih jauh dari habis.
- . 4 (« ») ! – ( -) . . . AlphaZero () .
- – ? – , , .. , . AlphaZero – – –. ? , , . , . . . . SkyNet akan menjadi sedikit lebih jauh dan sedikit lebih menyeramkan ... Sementara itu, saya akan berterima kasih atas tautan, artikel, dan ide tentang cara mengatasi masalah ini.
PS. Tapi Anda akan menonton pertandingan . Saya mendapat kesenangan yang tak tertandingi.