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.