Abstract:
Puzzle merupakan salah satu domain yang ideal untuk mempelajari dan mengembangkan Artificial Intelligence karena lingkungannya yang terkontrol. Sudah terdapat banyak game playing agent (GPA) yang dikembangkan untuk menyelesaikan berbagai puzzle. Beberapa contoh puzzle yang sudah dapat diselesaikan oleh GPA adalah Sudoku dan jigsaw puzzle. GPA yang dikembangkan mengimplementasikan berbagai macam teknik dan algoritma yang berbeda, beberapa contohnya seperti constraint programming, deep learning, reinforcement learning dan algoritma metaheuristik. Pada penelitian ini, dibangun sebuah GPA yang mengimplementasi Honey Badger Algorithm (HBA) dan Q-Learning untuk menyelesaikan Norinori yaitu sebuah logic puzzle yang berasal dari Jepang. HBA merupakan algoritma metaheuristik yang meniru perilaku musang madu yang dianggap cerdas dalam mencari makanan. Sementara Q-Learning merupakan algoritma reinforcement learning yang memodelkan sebuah tabel untuk menilai kualitas dari suatu aksi pada kondisi tertentu. Dilakukan analisis terhadap kedua algoritma agar dapat diaplikasikan untuk menyelesaikan Norinori. Sebelum mengimplementasikan kedua algoritma, GPA juga akan melakukan preprocessing menggunakan beberapa strategi puzzle yang ditemukan. Setelah GPA selesai dibangun, dilakukan eksperimen untuk mengetahui kemampuan serta pengaruh dari langkah-langkah dan nilai parameter yang digunakan oleh GPA. Berdasarkan hasil eksperimen yang didapatkan, GPA hanya dapat menyelesaikan sebagian dari puzzle Norinori yang digunakan pada eksperimen. Performa GPA pada puzzle dengan tingkat kesulitan normal sangat baik, mayoritas puzzle dengan tingkat kesulitan ini dapat diselesaikan. Sementara untuk puzzle dengan tingkat kesulitan hard, GPA hanya dapat menyelesaikan sebagian puzzle yang berukuran kecil. Selain itu, didapatkan bahwa langkah yang paling berpengaruh pada performa GPA adalah langkah preprocessing. Tanpa preprocessing, performa GPA mengalami penurunan yang sangat signifikan. Untuk nilai parameter, didapatkan bahwa parameter yang mengatur besar populasi (N) dan banyak iterasi (tmax) dari HBA memiliki pengaruh yang lebih besar terhadap hasil akhir dibandingkan dengan parameter lainnya.
