Saat ini, Anda mungkin pernah mendengar tentang bot yang memainkan video game pada level manusia super. Bot ini dapat diprogram secara eksplisit, bereaksi terhadap masukan yang ditetapkan dengan keluaran yang ditetapkan, atau "belajar" dan "berkembang", bereaksi dengan cara yang berbeda terhadap masukan yang sama dengan harapan menemukan respons yang optimal.
Beberapa contoh terkenal adalah:
- AlphaZero, bot Catur yang menjadi pemain terhebat di dunia dengan pelatihan 24 jam
- AlphaGo, bot Go yang terkenal mengalahkan pemain kelas dunia Lee Sedol dan Ke Jie
- MarI/O, bot Super Mario yang dapat belajar sendiri untuk mempercepat level Mario mana pun
Permainan ini rumit, dan melatih mesin ini memerlukan kombinasi cerdas antara algoritme rumit, simulasi berulang, dan waktu. Saya ingin fokus pada MarI/O dan mengapa kami tidak bisa menggunakan pendekatan serupa untuk mengalahkan permainan Pokemon (tonton video di tautan di atas jika Anda belum terbiasa dengan cara kerjanya).
Ada 3 perbedaan utama antara Mario dan Pokemon yang bertanggung jawab atas hal ini:
- Jumlah Tujuan
- Faktor Percabangan
- Optimasi Global vs Lokal
Mari kita bandingkan permainan menggunakan masing-masing faktor ini.
Jumlah Tujuan
Cara mesin belajaradalah dengan mengoptimalkan beberapa jenis fungsi tujuan. Baik itu memaksimalkan fungsi “reward” atau “fitness” (dalam Reinforcement Learning dan Genetic Algorithms) atau meminimalkan “cost function” (Dalam Supervised Learning), tujuannya serupa: mencapai skor terbaik.
Mario mempunyai satu tujuan: mencapai akhir level. Sederhananya, semakin jauh Anda bergerak ke kanan sebelum mati, semakin baik kinerja Anda. Ini adalah fungsi tujuan tunggal Anda, dan kemampuan model Anda dapat diukur secara langsung dengan satu angka ini.
Pokemon memiliki… banyak. Mari kita coba mengidentifikasi tujuan kita. Apakah untuk mengalahkan Elite 4? Untuk menangkap semua Pokemon? Latih tim terkuat? Apakah semuanya di atas atau ada yang lain sama sekali? Mengajukan pertanyaan ini saja sudah aneh, karena jawabannya mungkin merupakan kombinasi subjektif pribadi dari semuanya.
Kita tidak hanya harus menentukan tujuan akhir, tetapi juga seperti apa kemajuannya, sehingga setiap unit tindakan berhubungan dengan imbalan atau kerugian berdasarkan banyak kemungkinan pilihan pada satu waktu.
Ini membawa kita ke topik berikutnya.
Faktor Percabangan
Sederhananya, faktor cabang adalah berapa banyak pilihan yang dapat Anda buat pada setiap langkah. Dalam Catur, rata-rata faktor percabangan adalah 35; di Go, jumlahnya 250. Untuk setiap langkah tambahan di masa depan, Anda memiliki (faktor percabangan)^(langkah) sejumlah pilihan untuk dievaluasi.
Di Mario, Anda bisa ke kiri, kanan, melompat, atau tidak melakukan apa pun. Jumlah pilihan yang harus dievaluasi mesin kecil. Dan, semakin kecil faktor percabangannya, semakin jauh bot mampu melihat masa depan, secara komputasi.
Pokemon adalah game dunia terbuka, yang berarti Anda memiliki banyak pilihan pada waktu tertentu. Bergerak ke atas, bawah, kiri, atau kanan bukanlah ukuran yang berguna untuk menghitung faktor percabangan. Sebaliknya, kami melihat tindakan bermakna berikutnya. Apakah tindakan selanjutnya akan berperang, berbicara dengan NPC, atau pergi ke area lokal berikutnya di kiri, kanan, atas atau bawah? Jumlah pilihan yang mungkin berkisar dari besar hingga sangat besar seiring kemajuan Anda dalam permainan.
Membangun mesin yang dapat menentukan rangkaian pilihan terbaik mengharuskannya mempertimbangkan tujuan jangka pendek dan jangka panjangnya, yang membawa kita ke topik akhir.
Optimasi Lokal vs Global
Optimalisasi lokal dan global dapat dipikirkan secara spasial dan kronologis. Tujuan jangka pendek dan wilayah geografis terdekat dianggap bersifat lokal, sedangkan tujuan jangka panjang dan wilayah yang relatif lebih luas seperti kota atau bahkan keseluruhan peta dianggap global.
Memecah setiap run menjadi bagian-bagian penyusunnya dapat menjadi cara untuk menguraikan masalah Pokemon menjadi potongan-potongan kecil. Mengoptimalkan secara lokal untuk berpindah dari titik A ke titik B di satu area adalah hal yang mudah, namun menentukan tujuan mana yang merupakan titik B terbaik adalah masalah yang jauh lebih sulit. Algoritme serakah gagal di sini karena langkah-langkah pengambilan keputusan yang optimal secara lokal belum tentu mengarah pada optimal global.
Peta Mario berukuran kecil dan linier. Peta Pokemon berukuran besar, rumit, dan non-linier. Prioritas utama Anda berubah seiring waktu untuk mencapai sasaran tingkat tinggi, dan menerjemahkan tujuan global menjadi masalah pengoptimalan lokal yang diprioritaskan bukanlah tugas yang mudah. Ini bukanlah sesuatu yang dapat ditangani oleh model kami saat ini.
Satu hal terakhir
Dari sudut pandang bot, Pokemon bukan hanya satu permainan. Bot adalah spesialis, dan bot yang membantu Anda bergerak di sekitar peta tidak berdaya membantu ketika Anda bertemu dengan NPC yang ingin bertempur. Dari sudut pandang mereka, ini adalah dua tugas yang sangat berbeda.
Saat berperang, setiap giliran menghadirkan puluhan pilihan. Memilih gerakan mana yang akan digunakan, Pokemon mana yang akan ditukar, dan kapan menggunakan item yang berbeda merupakan masalah optimasi yang rumit. Setelah melihat-lihat, saya menemukan artikel ini di mana seseorang menjelaskan prosesnya dalam membangun simulator pertempuran. Ini dipikirkan dengan matang dan sangat rumit, dan masih tidak mempertimbangkan penggunaan item, sebagai faktor kunci untuk menentukan hasil pertempuran.
Sejauh ini, kita harus bersukacita karena kita bisa membuat bot yang lebih baik dalam permainan kita daripada kita. Sejauh ini, permainan-permainan ini rumit secara matematis, tetapi obyektifnya sederhana. Seiring dengan semakin majunya AI, kami akan menciptakan mesin yang mampu memecahkan masalah dunia nyata yang semakin berdampak, melalui pembelajaran mereka sendiri terhadap masalah pengoptimalan yang kompleks. Yakinlah bahwa masih ada hal-hal yang membuat kita lebih baik, termasuk permainan masa kecil kita — setidaknya untuk saat ini. Terima kasih sudah membaca!
