Implementasi Algoritma Grey Wolf Optimizer pada permainan Light Up

Abstract

Light Up merupakan permainan papan dua dimensi yang dimainkan oleh satu pemain. Setiap petak pada papan terdiri dari warna hitam atau putih. Petak hitam dapat terdiri dari angka 0–4 atau tidak terdapat angka sama sekali. Angka pada petak hitam merujuk pada jumlah lampu yang perlu diletakkan di atas, bawah, kiri, atau kanan petak hitam tersebut. Pemain hanya dapat meletakkan lampu pada petak putih. Lampu yang diletakkan pemain menyinari setiap petak putih di posisi horizontal dan vertikal dari petak yang diletakkan lampu tetapi tidak terhalang oleh petak hitam. Permainan dinyatakan selesai hanya jika seluruh petak putih tersinari pada papan, jumlah lampu yang diletakkan di sekeliling petak hitam berangka sesuai dengan angka yang tertera pada petak hitam tersebut, dan lampu yang diletakkan tidak menyinari lampu lainnya pada papan. Algoritma Grey Wolf Optimizer (GWO) diimplementasikan dalam pencarian solusi permainan Light Up pada skripsi ini. Grey Wolf Optimizer (GWO) merupakan algoritma population based meta-heuristics yang menyimulasikan hierarki kepemimpinan dan perilaku serigala abu-abu dalam berburu di alam liar. Setiap serigala yang berada di dalam populasi memiliki posisinya masing-masing, sehingga perpindahan posisi setiap serigala memungkinkan penjelajahan ruang pencarian. Pada skripsi ini, Algoritma GWO diimplementasikan dalam dua tahap. Pada tahap pertama Algoritma GWO digunakan untuk mencari posisi peletakkan lampu di sekeliling petak hitam berangka 1 sampai 4, kemudian pada tahap kedua Algoritma GWO digunakan untuk mencari posisi peletakkan lampu di petak putih yang belum tersinari oleh lampu dari tahap pertama. Kondisi peletakkan lampu pada papan dihitung menggunakan fungsi evaluasi yang menghasilkan nilai fitness. Hukuman diberikan hanya jika kondisi peletakkan lampu pada papan melanggar aturan atau heuristik permainan. Hukuman diberikan dengan menambahkan nilai fitness. Nilai hukuman dihitung menggunakan bobot hukuman yang dapat diatur. Preprocessing sebelum tahap pertama, setelah tahap pertama, dan setelah tahap kedua dilakukan dengan memanfaatkan heuristik permainan yang ditemukan sehingga ruang pencarian solusi diperkecil. Input papan diambil melalui situs penyedia papan Light Up. Selenium digunakan untuk mengambil input papan secara otomatis dengan menggunakan web scraping. Selain digunakan untuk mengambil input papan, Selenium juga digunakan untuk menyimulasikan model dengan melakukan interaksi pada situs permainan, sehingga model dapat bermain secara otomatis pada situs permainan. Berbagai eksperimen dilakukan pada dataset input papan untuk melihat pengaruh parameter yang digunakan dan mengukur kemampuan model dalam menyelesaikan seluruh jenis papan. Hasil eksperimen menunjukkan bahwa model yang dirancang mampu menyelesaikan papan hingga ukuran 25×25 dengan tingkat kesulitan easy hanya jika preprocessing digunakan, sedangkan apabila preprocessing tidak digunakan, maka model yang dirancang mampu menyelesaikan papan hingga ukuran 14 × 14 dengan tingkat kesulitan easy.