Jurnal Mantik Penusa
Volume 19 No 1 Juni 2016
ISSN 2088-3943
IMPLEMENTASI ALGORITMA SIMPLE HILL CLIMBING PADA APLIKASI GAME TTS (TEKA – TEKI SILANG) Paska Marto Hasugian Program Studi Teknik Informatika STMIK Pelita Nusantara , Jl Iskandar Muda No 1 Medan, Sumatera Utara, Indonesia
[email protected] Abstrak Seiring dengan perkembangan ilmu pengetahuan dan teknologi, maka salah satu cara untuk mencapai tujuan tersebut adalah dengan optimasi. Optimasi adalah pencarian nilai-nilai variable yang dianggap optimal untuk mencapai hasil yang diinginkan. Masalah optimasi adalah dengan cara memaksimumkan pengisian ruang-ruang kosong. Untuk memecahkan masalah optimasi tersebut, tentunya diperlukan algoritma yang handal. Kajian ini bertujuan untuk membuat sebuah aplikasi optimasi yaitu pembuatan teka-teki silang dengan menggunakan algoritma simple hill climbing. Algoritma Simple Hill Climbing adalah salah satu metode dari sekian banyak metode kecerdasan buatan untuk menyelesaikan permasalahan optimasi. Karena algoritmanya yang cukup sederhana, metode Hill Climbing telah banyak diterapkan dalam berbagai aplikasi. Disamping itu metode hill climbing juga mengefisienkan penggunaan memori yang besar. Dengan menggunakan Algoritma Simple Hill Climbing, maka aplikasi ini bertujuan untuk mempermudah dalam membuat teka-teki silang dengan pertanyaan-pertanyaan yang dapat ditentukan sendiri oleh pengguna. Kata Kunci : Simple Hill Climbing, TTS I. PENDAHULUAN Seiring dengan perkembangan ilmu pengetahuan dan teknologi, maka salah satu cara untuk mencapai tujuan tersebut adalah dengan optimasi. Optimasi adalah pencarian nilai-nilai variable yang dianggap optimal untuk mencapai hasil yang diinginkan. Masalah optimasi adalah dengan cara memaksimumkan pengisian ruang-ruang kosong. Untuk memecahkan masalah optimasi tersebut, tentunya diperlukan algoritma yang handal. Teka-teki silang merupakan sebuah permainan untuk mengasah otak. Teka-teki silang dapat dimanfaatkan dalam bidang pendidikan untuk menguji kemampuan anak didik, sehingga pertanyaan-pertanyaan yang digunakan disesuaikan dengan kebutuhan saja. Tapi akan sulit apabila jumlah pertanyaan yang digunakan banyak, karena untuk membuat sebuah teka-teki silang dari sekumpulan pertanyaan, kita harus mencoba kombinasi yang mungkin dari kata yang ada sampai terbentuk sebuah TTS. Semakin banyak jumlah pertanyaan, maka semakin banyak kombinasi yang harus dicoba. TTS merupakan permainan yang memberikan pembelajaran. Metode Hill Climbing adalah salah satu metode dari sekian banyak metode kecerdasan buatan untuk menyelesaikan permasalahan optimasi. Karena algoritmanya yang cukup sederhana, metode Hill Climbing telah banyak diterapkan dalam berbagai aplikasi. Disamping itu
metode hill climbing juga mengefisienkan penggunaan memori yang besar. Teka-teki silang merupakan permainan klasik. Selain digunakan untuk menghilangkan rasa jenuh, TTS juga bermanfaat untuk mengasah kemampuan otak dan penambah pengetahuan. Dalam optimasi, penerapan algoritma Simple Hill Climbing digunakan untuk mendapatkan suatu pola penyusunan kata dalam ruang-ruang kosong yang paling optimal. Untuk mengetahui optimal atau tidaknya pengisian ruang kosong tersebut, dilakukan dengan melihat banyaknya kombinasi kata yang dapat dibuat atau dapat juga dilihat dari banyaknya sisa ruang kosong teka-teki silang tersebut. Jadi, semakin banyak dan baik kombinasi kata yang dibuat untuk mengisi ruang-ruang kosong, maka semakin optimal pengisian tersebut. Solusi ini dapat diatasi apabila membuat teka-teki silang dilakukan secara otomatis dengan computer II. TEORI Dasar penyelesaian permasalahan dengan mengikuti langkah berikut ini : 1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal. 2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada
138 Junal Manajemen dan Informatika Komputer Pelita Nusantara
Jurnal Mantik Penusa
Volume 19 No 1 Juni 2016
operator baru yang akan diaplikasikan pada keadaan sekarang 3. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. 4. Evaluasi keadaan baru tersebut: a. Jika keadaan baru merupakan tujuan, keluar. b. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. c. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi. Pada simple hill climbing ini, ada 3 masalah yang mungkin, yaitu: 1. Algoritma akan berhenti kalau mencapai nilai optimum lokal. 2. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi. 3. Tidak diizinkan untuk melihat satupun langkah sebelumnya Fungsi Heuristik yang digunakan adalah jumlah kotak yang menempati posisi benar. Kriteria yang dipakai adalah jumlah benar yang paling besar yang dipilih. Crossover atau pindah silang adalah proses pembentukan kromosom anak (offspring). Crossover bertujuan menambah keanekaragaman string dalam satu populasi dengan penyilangan antar-string yang diperoleh dari reproduksi sebelumnya. Algoritma ini paling banyak dipakai orang karna algoritma ini sangat mudah digunakan.
pertanyaan yang akan ditampilkan pada pengguna tersebut diperoleh dari database secara acak oleh program. Teka-teki silang yang telah dibuat dapat disimpan dalam bentuk sebuah file yang memungkinkan pengguna untuk memainkan kembali teka-teki silang tersebut pada waktu yang lain. Pertanyaan-pertanyaan yang akan digunakan dalam teka-teki silang disimpan dalam database. Database yang berisi pertanyaan-pertanyaan tersebut dapat diupdate sehingga koleksi pertanyaan yang tersimpan dapat bertambah. Dengan demikian, pengguna dapat bermain teka-teki silang dengan pertanyaan yang lebih bervariasi. Teka-teki silang yang dibentuk merupakan kumpulan jawaban dari pertanyaan yang digunakan. Jawaban-jawaban pertanyaan disusun sedemikian rupa sehingga saling berpotongan satu sama lain. Untuk membentuk sekumpulan jawaban pertanyaan menjadi teka-teki silang digunakan sebuah papan matriks berdimensi dua. Papan matriks dapat dianalogikan seperti sebuah papan catur. Setiap kotak (cell) berada pada koordinat x,y. Pada papan matriks ini nantinya jawaban dari pertanyaan akan diletakkan untuk dibentuk menjadi sebuah teka-teki silang. Setiap huruf dari jawaban akan menempati satu cell pada papan matriks. Aplikasi menerima masukan dari pengguna berupa jumlah pertanyaan, permintaan update, pilihan load game dan jawaban pengguna. Jumlah pertanyaan merupakan jumlah dari pertanyaan yang akan digunakan dalam permainan teka-teki silang. Permintaan update digunakan pengguna untuk meng-update database pertanyaan. Sedangkan, pilihan load game digunakan untuk memainkan teka-teki silang yang telah disimpan sebelumnya dalam bentuk file dengan ekstensi .tts. Selain menerima masukan dari pengguna, aplikasi juga memberikan keluaran kepada pengguna berupa teka-teki silang dan jawaban yang benar dari TTS tersebut. Analisa Penyelesaian Algoritma Simple Hill Climbing
Gambar 1. Algoritma Simple Hill Climbing dengan 4 operator III. Analisa dan Hasil 1. Analisa Teka-teki silang dengan menggunakan algoritma Simple Hill Climbing yang akan dibangun dalam penelitian ini diharapkan dapat menghasilkan tekateki silang dengan jumlah pertanyaan yang ditentukan sendiri oleh pengguna. Pertanyaan-
ISSN 2088-3943
Ruang keadaan : Misalkan : x = baris = [1.2,3] y = kolom = [1,4,7] Aturan / Opreator : Posisi kotak kosong (x,y) x = baris kotak kosong y = kolom kotak kosong 1. Gerakkan kotak kosong ke atas : if x > 1 then ( x-1, y) 2. Gerakkan kotak kosong kebawah then ( x+1, y) 3. Gerakkan kotak kosong kekanan : if y < 3 then ( x, y +1)
: if x < 3
139 Junal Manajemen dan Informatika Komputer Pelita Nusantara
Jurnal Mantik Penusa
Volume 19 No 1 Juni 2016
4.
Gerakkan kotak kosong kekiri then ( x, y -1) Fungsi Heuristik
: if y >1
Fungsi heuristik yang digunakan adalah jumlah kotak yang menempati posisi benar, kriteria yang dipakai adalah jumlah benar yang paling besar yang dipilih. A
I
R
N G
P
I
I E
M
K A
A
B
N U
N
G I
A S
I
S
ISSN 2088-3943
U
N
Gambar 2 Contoh Kasus Mendatar Menurun 1. Water (Inggris) 1. Bilangan 2. Panas 3. Mau 5. Melebar, Membesar 4. Kasihan 6. Air Susu Ibu 7. Matahari (Inggris) Tabel 1 : Keadaan Awal A
I
R
O
G
A
S
N
O
O
I
O
O
-1
G
E
M
B
U
N
G
K
O
O
A
O
O
-1
A
S
I
O
S
U
N
Aturan : Nilai = 0 Mendatar 1. If (1,1) = “A” And (1,2) = “I” And (1,3) = “R” Then Nilai = +1 2. If (1,5) = “A” And (1,6) = “P” And (1,7) = “I” Then Nilai = +1 3. If (3,1) = “G” And (3,2) = “E” And (3,3) = “M” And (3,4) = “B” And (3,5) = “U” And (3,6) = “N” And (3,7) = “G” Then Nilai = +1 4. If (5,1) = “A” And (5,2) = “S” And(5,3) =”I” Then Nilai = +1 5. If (5,5) = “S” And (5,6) = “U” And(5,7) =”N” Then Nilai = +1 Menurun 1. If (1,1) = “A” And (2,1) = “N” And (3,1) = “G” And (4,1) = “K” And (5,1) = “A” Then Nilai = +1 2. If (1,4) = “I” And (2,4) “B” And (3,4) = “A” Then Nilai = +1 3. If (1,7) = “I” And (2,7) = “N” And (3,7) = “G” And(4,7) = “I” And (5,7) = “N” Then Nilai = +1 Nilai = 6 2. Hasil Pada hasil penelitian diungkapkan tersaji aplikasi permainan dengan penerapan hill climbing
Tabel 2 Keadaan Goal I
N
N
G
O O I O O Tabel 3 Ruang Keadaan E M B U N
G
Gambar 3 Hasil TTS
K
O
O
A
O
O
I
I
O
S
U
N
IV. KESIMPULAN Algoritma simple hill climbing dapat digunakan untuk membuat teka-teki silang. Seperti TTS pada umumnya, karakter yang digunakan untuk mengisi kotak TTS hanya karakter huruf A sampai Z. TekaTeki Silang yang dibuat adalah teka-teki silang dalam bentuk yang dikenal sekarang ini. Pertanyaan dibagi menjadi dua kategori, yaitu mendatar dan menurun. Jawaban pertanyaan mendatar tidak boleh tersusun bersambung dengan jawaban pertanyaan mendatar,
A
R
O
A
S
A
P
I
1,1
1,2
1,3
1,4
1,5
1,6
1,7
2,1
2,2
2,3
2,4
2,5
2,6
2,7
3,1
3,2
3,3
3,4
3,5
3,6
3,7
4,1
4,2
4,3
4,4
4,5
4,6
4,7
5,1
5,2
5,3
5,4
5,5
5,6
5,7
Junal Manajemen dan Informatika Komputer Pelita Nusantara
140
Jurnal Mantik Penusa
Volume 19 No 1 Juni 2016
dan jawaban pertanyaan menurun tidak boleh tersusun bersambung dengan jawaban pertanyaan menurun. Dari hasil pengujian diatas dapat dilihat bahwa waktu komputasi yang diperlukan untuk membuat teka-teki silang sebanding dengan jumlah soal yang digunakan.
[3] Hafni Syaeful Sulun dan Renaldi Munir, “Jurnal Teka-Teki Silang”, 2010.
V. REFERENSI [1] T.Sujono, Edy Mulyanto, Vincent Suhartono, “Kecerdasan Buatan”, Penerbit Andi Yogyakarta, 2010.
ISSN 2088-3943
[4] Herlawati, 2011, Menggunakan UML, Bandung, Penerbit Informatika [5] Prahasta Eddy, 2009, Sistem Informasi Geografis, Bandung, Penerbit Informatik [6] Munir, Rinaldi, 2010. Matematika Diskrit Edisi Ketiga, Bandung : Informatika Bandung.
[2] Thiang, Hendry Khoswsanto, Felix Pasila, Hendra Thelly, “Jurnal Simple Hill Climbing, 2008.
141 Junal Manajemen dan Informatika Komputer Pelita Nusantara
