Penyelesaian permainan Hitori menggunakan algoritma genetika

Abstract

Hitori adalah sebuah permainan puzzle yang dimainkan pada bidang dua dimensi dengan ukuran baris dan kolom yang sama. Permainan ini diterbitkan oleh sebuah perusahaan penerbit asal Tokyo, Jepang. Permainan Hitori diperkenalkan pertama kali ke publik pada Maret 1990. Hitori dimainkan dengan mengeliminasi angka-angka dengan kemunculan lebih dari satu kali, yang terdapat pada baris maupun kolom bidang permainan. Angka-angka yang dieliminasi pun tidak boleh saling bertetangga satu sama lain, baik secara horizontal maupun vertikal (bidang orthogonal). Kemudian angka-angka yang tidak dieliminasi harus saling terhubung satu sama lain dan tidak terisolasi oleh angka-angka yang dieliminasi. Permainan Hitori berhasil diselesaikan apabila tidak terdapat angka-angka duplikat pada tiap baris dan tiap kolom permainan. Hitori merupakan permainan logika yang bersifat NP-Complete, dimana solusi dari permainan ini dapat dicari dengan menggunakan algoritma Brute Force. Algoritma genetika merupakan algoritma pencarian yang terinspirasi dari proses natural selection. Algoritma genetika dapat digunakan untuk memecahkan combinatorial optimization problems yang sulit. Algoritma genetika ini dikemukakan oleh John Holland dari Michigan University pada 1975. John Holland mengkombinasikan keberhasilan suatu struktur untuk bertahan hidup (survival of the fittest). Algoritma genetika menjalankan operasi-operasi seleksi, persilangan, mutasi, dan elitism untuk mencari kandidat solusi dari suatu permasalahan yang hendak diselesaikan. Aturan-aturan main pada permainan Hitori akan dijadikan sebagai landasan penghitungan nilai fitness pada algoritma genetika yang akan diimplementasikan. Singkatnya, semakin banyak aturan main yang dilanggar oleh sebuah kandidat solusi, maka nilai fitness untuk kandidat solusi tersebut semakin buruk/kecil. Kandidat solusi yang tidak melanggar satu pun aturan main dari permainan Hitori, ditampilkan sebagai solusi dari permainan Hitori. Pada penelitian ini dibangun sebuah perangkat lunak permainan puzzle Hitori dengan ukuran 5x5, algoritma genetika diterapkan pada perangkat lunak ini untuk mencari solusi permainan dari puzzle Hitori. Hasil pengujian atas pengimplementasian algoritma genetika dalam menyelesaikan permainan Hitori adalah sebesar 94%. Dalam penelitian ini, algoritma genetika berhasil menyelesaikan 47 soal permainan Hitori dari 50 soal permainan yang tersedia.