AI membenci ketidakpastian. Namun untuk menavigasi dunia kita yang tidak dapat diprediksi, perlu belajar membuat pilihan dengan informasi yang tidak sempurna — seperti yang kita lakukan setiap hari.
DeepMind saja tertusuk dalam memecahkan teka-teki ini. Triknya adalah menjalin teori permainan ke dalam strategi algoritmik yang secara longgar didasarkan pada otak manusia yang disebut pembelajaran penguatan mendalam. Hasilnya, DeepNash, menggulingkan pakar manusia dalam permainan papan yang sangat strategis bernama Stratego. Gim yang terkenal sulit untuk AI, Stratego membutuhkan banyak kekuatan kecerdasan manusia: pemikiran jangka panjang, menggertak, dan menyusun strategi, semua tanpa mengetahui bidak lawan Anda di papan.
“Tidak seperti catur dan Go, Stratego adalah permainan informasi yang tidak sempurna: pemain tidak dapat secara langsung mengamati identitas bidak lawan mereka,” DeepMind menulis dalam posting blog. Dengan DeepNash, "sistem kecerdasan buatan (AI) yang bermain game telah maju ke perbatasan baru."
Ini tidak semua kesenangan dan permainan. Sistem AI yang dapat dengan mudah menggerakkan keacakan dunia kita dan menyesuaikan "perilaku" mereka suatu hari nanti dapat menangani masalah dunia nyata dengan informasi terbatas, seperti mengoptimalkan arus lalu lintas untuk mengurangi waktu perjalanan dan (mudah-mudahan) memadamkan kemarahan di jalan sebagai self-driving mobil menjadi semakin hadir.
“Jika Anda membuat mobil self-driving, Anda tidak ingin berasumsi bahwa semua pengemudi lain di jalan sangat rasional, dan akan berperilaku optimal,” tersebut Noam Brown di Meta AI, yang tidak terlibat dalam penelitian.
Kemenangan DeepNash datang menyusul kemajuan AI lainnya bulan ini, di mana algoritma belajar bermain Diplomasi—sebuah permainan yang membutuhkan negosiasi dan kerja sama untuk menang. Saat AI mendapatkan penalaran yang lebih fleksibel, menjadi lebih umum, dan belajar menavigasi situasi sosial, itu juga dapat memicu wawasan ke dalam proses saraf dan kognisi otak kita sendiri.
Temui Strategi
Dalam hal kerumitan, Stratego adalah monster yang sama sekali berbeda dibandingkan dengan catur, Go, atau poker—semua game yang sebelumnya dikuasai AI.
Permainan ini pada dasarnya menangkap bendera. Setiap sisi memiliki 40 buah yang dapat mereka tempatkan di posisi mana pun di papan. Setiap bidak memiliki nama dan pangkat numerik yang berbeda, seperti "marshal", "umum", "pramuka", atau "mata-mata". Potongan peringkat yang lebih tinggi dapat menangkap yang lebih rendah. Tujuannya adalah untuk menghilangkan oposisi dan merebut bendera mereka.
Stratego sangat menantang untuk AI karena pemain tidak dapat melihat lokasi bidak lawan mereka, baik selama penyiapan awal maupun selama permainan. Tidak seperti catur atau Go, yang menampilkan setiap bagian dan gerakan, Stratego adalah permainan dengan informasi terbatas. Pemain harus "menyeimbangkan semua hasil yang mungkin" setiap kali mereka membuat keputusan, jelas penulis.
Tingkat ketidakpastian ini sebagian menjadi alasan mengapa Stratego telah mengalahkan AI selama berabad-abad. Bahkan algoritme permainan-permainan yang paling sukses, seperti AlphaGo dan AlfaZero, mengandalkan informasi lengkap. Stratego, sebaliknya, memiliki sentuhan Texas Hold 'em, game poker yang sebelumnya ditaklukkan DeepMind dengan algoritme. Tapi strategi itu goyah untuk Stratego, sebagian besar karena lamanya permainan, yang tidak seperti poker, biasanya mencakup ratusan gerakan.
Jumlah potensi permainan yang dimainkan sangat mencengangkan. Catur memiliki satu posisi awal. Stratego memiliki lebih dari 1066 kemungkinan posisi awal—jauh lebih banyak daripada semua bintang di alam semesta. Pohon permainan Stratego, jumlah dari semua gerakan potensial dalam permainan, berjumlah 10 yang mengejutkan535.
“Kerumitan dari jumlah kemungkinan hasil di Stratego berarti algoritme yang bekerja dengan baik pada permainan informasi sempurna, dan bahkan algoritme yang berfungsi untuk poker, tidak berfungsi,” tersebut penulis studi Dr. Julien Perolat di DeepMind. Tantangannya adalah "apa yang membuat kami bersemangat," katanya.
A Beautiful Mind
Kompleksitas Stratego berarti bahwa strategi biasa untuk mencari gerakan gameplay tidak mungkin dilakukan. Dijuluki pencarian pohon Monte Carlo, sebuah "pendekatan pendukung untuk game berbasis AI", teknik ini merencanakan rute potensial — seperti cabang di pohon — yang dapat menghasilkan kemenangan.
Sebaliknya, sentuhan ajaib untuk DeepNash datang dari ahli matematika John Nash, yang diperankan dalam film tersebut A Beautiful Mind. Seorang perintis dalam teori permainan, Nash memenangkan Hadiah Nobel untuk karyanya di Ekuilibrium Nash. Sederhananya, di setiap permainan, pemain dapat memanfaatkan serangkaian strategi yang diikuti oleh semua orang, sehingga tidak ada satu pemain pun yang memperoleh keuntungan dengan mengubah strategi mereka sendiri. Di Statego, ini menghasilkan permainan zero-sum: keuntungan apa pun yang diperoleh pemain akan mengakibatkan kerugian bagi lawannya.
Karena kerumitan Stratego, DeepNash mengambil pendekatan tanpa model untuk algoritme mereka. Di sini, AI tidak mencoba memodelkan perilaku lawannya dengan tepat. Seperti bayi, ia memiliki semacam batu tulis kosong untuk dipelajari. Pengaturan ini sangat berguna pada tahap awal permainan, “ketika DeepNash hanya mengetahui sedikit tentang bidak lawannya,” membuat prediksi “sulit, jika bukan tidak mungkin,” kata penulis.
Tim kemudian menggunakan pembelajaran penguatan mendalam untuk menggerakkan DeepNash, dengan tujuan menemukan keseimbangan Nash permainan. Ini adalah pasangan yang dibuat di surga: pembelajaran penguatan membantu memutuskan langkah terbaik selanjutnya di setiap langkah permainan, sementara DeepNash menyediakan strategi pembelajaran secara keseluruhan. Untuk mengevaluasi sistem, tim juga merekayasa "tutor" menggunakan pengetahuan dari game untuk menyaring kesalahan nyata yang mungkin tidak masuk akal di dunia nyata.
Praktek Membuat Sempurna
Sebagai langkah pembelajaran pertama, DeepNash bermain melawan dirinya sendiri dalam 5.5 miliar game, sebuah pendekatan populer dalam pelatihan AI yang disebut self-play.
Ketika satu pihak menang, AI mendapat penghargaan, dan parameter jaringan saraf tiruannya saat ini diperkuat. Pihak lain—AI yang sama—menerima penalti untuk meredam kekuatan jaringan sarafnya. Ini seperti melatih pidato untuk diri sendiri di depan cermin. Seiring waktu, Anda menemukan kesalahan dan tampil lebih baik. Dalam kasus DeepNash, itu mengarah ke keseimbangan Nash untuk gameplay terbaik.
Bagaimana dengan kinerja yang sebenarnya?
Tim menguji algoritme tersebut melawan bot elit Stratego lainnya, beberapa di antaranya memenangkan Kejuaraan Dunia Stratego Komputer. DeepNash menghancurkan lawan-lawannya dengan tingkat kemenangan sekitar 97 persen. Saat dilepaskan melawan Gravon — platform online untuk pemain manusia — DeepNash mengalahkan lawan manusianya. Setelah lebih dari dua minggu pertandingan melawan para pemain Gravon pada bulan April tahun ini, DeepNash naik ke posisi ketiga di semua pertandingan peringkat sejak 2002.
Ini menunjukkan bahwa bootstrap data permainan manusia ke AI tidak diperlukan untuk DeepNash untuk mencapai kinerja tingkat manusia—dan mengalahkannya.
AI juga menunjukkan beberapa perilaku menarik dengan penyiapan awal dan selama bermain game. Misalnya, alih-alih menetapkan posisi awal tertentu yang "dioptimalkan", DeepNash terus-menerus menggeser bidak untuk mencegah lawannya menemukan pola dari waktu ke waktu. Selama bermain game, AI memantul di antara gerakan yang tampaknya tidak masuk akal — seperti mengorbankan bidak peringkat tinggi — untuk menemukan bidak lawan yang peringkatnya lebih tinggi saat melakukan serangan balik.
DeepNash juga bisa menggertak. Dalam satu permainan, AI memindahkan bidak berpangkat rendah seolah-olah bidak berpangkat tinggi, memikat lawan manusia untuk mengejar bidak dengan kolonel berpangkat tinggi. AI mengorbankan pion, tetapi pada gilirannya, memikat bidak mata-mata lawan yang berharga untuk menyergap.
Meskipun DeepNash dikembangkan untuk Stratego, itu dapat digeneralisasikan ke dunia nyata. Metode inti berpotensi menginstruksikan AI untuk mengatasi masa depan kita yang tidak dapat diprediksi dengan lebih baik menggunakan informasi yang terbatas—dari kerumunan dan kontrol lalu lintas hingga menganalisis gejolak pasar.
“Dalam menciptakan sistem AI yang dapat digeneralisasikan yang kuat dalam menghadapi ketidakpastian, kami berharap dapat membawa kemampuan pemecahan masalah AI lebih jauh ke dalam dunia kita yang tidak dapat diprediksi secara inheren,” kata tim tersebut.
Gambar Kredit: Derek Bruff / Flickr
