Penyelesaian permainan Nurikabe menggunakan algoritma genetika

Abstract

Nurikabe atau dikenal juga dengan nama ’Island in the Streams’ merupakan permainan papan berukuran n x n berasal dari negara Jepang yang diciptakan oleh perusahaan bernama Nikoli pada tahun 1991. Diberikan sebuah papan yang berupa matriks berukuran n x n dengan m elemen matriks (sel) yang terisi angka, tujuan dari permainan ini adalah membuat m buah pulau yaitu kumpulan sel yang terhubung sedemikian sehingga setiap sel yang berisi angka berada di sebuah pulau dengan banyaknya sel dari pulau tersebut sesuai dengan angka tersebut. Syarat lain yang harus dipenuhi adalah setiap pulau harus terpisah dengan pulau yang lain oleh aliran sungai (kumpulan sel yang termasuk elemen pulau). Aliran sungai tidak boleh terputus dan tidak boleh berukuran 2 x 2 atau lebih. Salah satu algoritma yang dapat digunakan untuk menyelesaikan permainan ini adalah Algoritma Genetika. Algoritma Genetika adalah sebuah algoritma yang memanfaatkan salah satu teknik heuristik ’generate and test’ yang terinspirasi oleh sistem seleksi alam yang bertujuan untuk menghasilkan keturunan yang lebih baik. Sebuah kromosom pada individu mewakili satu kandidat solusi dari permainan. Pada ukuran populasi tertentu akan terdiri dari banyak individu-individu yang merupakan kandidat-kandidat solusi dari permainan yang akan diuji melalui fungsi kelayakan sehingga semakin tinggi nilai kelayakan individu yang dihasilkan melalui fungsi kelayakan maka semakin peluang tinggi individu tersebut untuk bereproduksi dan bertahan hidup ke generasi selanjutnya. Keturunan yang lebih baik adalah keturunan yang dapat mengarah pada solusi permainan dengan menggunakan operator-operator genetika seperti seleksi, perkawinan silang, dan mutasi. Tujuan dari skripsi ini adalah membuat perangkat lunak untuk menyelesaikan permainan Nurikabe dengan menggunakan algoritma genetika. Perangkat lunak sudah berhasil dikembangkan dan telah diuji fungsionalitasnya. Di samping itu, telah pula dilakukan sejumlah eksperimen untuk mengukur kualitas dari perangkat lunak. Hasil dari eksperimen adalah tingkat keberhasilan perangkat lunak dalam menyelesaikan permainan adalah 75%. Angka 75% didapat dari jumlah perhitungan persentase tertinggi tingkat keberhasilan algoritma genetika dalam menyelesaikan permainan pada ukuran papan 5 x 5 ditambah persentase tertinggi tingkat keberhasilan algoritma genetika dalam menyelesaikan permainan pada ukuran papan 7 x 7 ditambah persentase tertinggi tingkat keberhasilan algoritma genetika dalam menyelesaikan permainan pada ukuran papan 10 x 10, kemudian hasil dari penjumlahan persentase tersebut dibagi 3 karena terdapat 3 ukuran papan yang berbeda. Adanya kemungkinan bahwa perangkat lunak gagal dalam menemukan solusi dari permainan disebabkan oleh sifat acak dari algoritma genetika ini. Tingkat kegagalan ini berbanding lurus dengan ukuran papan permainan. Semakin besar ukuran grid papan permainan, maka kemungkinan algoritma genetika gagal dalam menemukan solusi dari permainan semakin besar. Tingkat keberhasilan serta kecepatan algoritma genetika dalam menyelesaikan permainan dipengaruhi oleh parameter-parameter algoritma genetika.