ALGORITMA INTERATIVE-DEEPENING SEARCH

 

PENERAPAN ALGORITMA

INTERATIVE-DEEPENING SEARCH (IDS)

DALAM PENYELESAIAN PERMAINAN TEKA-TEKI KAKURO

 

    Artificial Intelligence (AI) atau kecerdasan buatan adalah salah satu bidang ilmu komputer yang sangat penting untuk mempelajari kecerdasan manusia. Dalam era teknologi informasi ini, AI berkembang sangat pesat. Salah satu peranan AI adalah mencari penyelesaian yang dapat dilakukan oleh manusia. Namun, dengan kelebihan dalam kecepatan perhitungannya, AI dapat menemukan solusi lebih cepat dibandingkan dengan manusia. Salah satu penyelesaian dari permainan yang dapat ditemukan dengan menggunakan ilmu AI adalah Kakuro.

    Permainan Kakuro adalah permainan teka-teki logika yang diproduksi oleh Nikoli. Kakuro merupakan permainan teka-teki logika yang sangat populer di Jepang dan muncul di hampir 100 majalah dan koran Jepang. Nikoli bahkan berhasil menjual sekitar 1 juta buku Kakuro. Cara bermain Kakuro adalah pemain harus mengisi setiap kotak yang kosong dengan angka bulat dari 1 hingga 9, dengan syarat bahwa total dari angka per baris dan kolom harus sesuai dengan nilai input pada setiap baris dan kolom. Angka tidak boleh berulang pada angka dan baris yang sama.

    Salah satu teknik pencarian yang dapat digunakan untuk mencari penyelesaian teka-teki Kakuro adalah algoritma pencarian IterativeDeepening Search (IDS). IDS melakukan pencarian secara iteratif menggunakan pencarian mendalam yang dimulai dengan batasan nol. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 dengan batasan level 1. Demikian seterusnya hingga ditemukan solusi. Teknik pencarian IDS akan dilakukan sedikit modifikasi sehingga dalam pencarian solusi, tidak melanggar aturan dari Kakuro.

PEMBAHASAN

Kecerdasan buatan berasal dari bahasa Inggris “Artificial Intelligence” (atau disingkat AI), yaitu intelligence adalah kata sifat yang berarti cerdas, sedangkan artificial artinya buatan. Kecerdasan buatan di sini merujuk pada mesin yang mampu berpikir, menimbang tindakan yang diambil, dan mampu mengambil keputusan seperti yang dilakukan oleh manusia.

Iterative Deepening Search (IDS) merupakan metode yang menggabungkan kelebihan BFS (complete dan optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori). Tetapi konsekuensinya adalah time complexity-nya menjadi tinggi. IDS melakukan pencarian secara iteratif menggunakan penelusuran Depth-Limited-Search (DLS) dimulai dengan batasan level 0. Jika belum ditemukan solusi, maka dilakukan iterasi ke-2 dengan batasan level 1. Demikian seterusnya sampai ditemukan solusi. Perhatikan gambar di bawah ini.

Metode pencarian pada IDS menggunakan metode pencarian pada DFS, yaitu pencarian pada sebuah pohon dengan menelusuri satu cabang sebuah pohon sampai menemukan solusi. Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang diinginkan). Akan tetapi, dalam metode pencarian IDS, pencarian mencoba menemukan batas kedalaman yang terbaik dengan terus menelusuri batas kedalaman satu per satu, pencarian dilakukan secara iteratif dimulai dari batasan level 0. Jika solusi belum ditemukan, maka dilakukan iterasi berikutnya dengan batasan level 1, demikian seterusnya sampai menemukan solusi. IDS melakukan pencarian berulang-ulang dengan menambah batas kedalaman setiap mengulang pencarian, dan akhirnya menemukan solusi pada penelusuran dengan batas kedalaman tertentu. Solusi ditemukan pada percabangan kiri atau kanan. Pencarian ini akan menemukan solusi lebih cepat daripada penelusuran pada DFS, jika solusi tidak berada pada node yang dalam.

    Kakuro muncul pertama sekali pada tahun 1966 di majalah teka teki Amerika Serikat pada tahun 1966. Pada saat itu, permainan teka-teki itu bernama "Cross Sums". Pada tahun 1980, seorang pria Jepang yang bernama Maki Kaji mengadakan kunjungan bisnis ke Amerika Serikat. Maki adalah seorang penggemar teka-teki, seperti orang Jepang pada umumnya. Maki sangat tertarik dengan permainan teka-teki ini, sehingga setelah kembali ke Jepang, Maki mulai membuat dan mempublikasi permainan ini di Jepang. Permainan ini dinamakan kasan kurosu, kombinasi dari kata Jepang untuk "tambah", dan kata Inggris "cross" dalam bahasa Jepang. Selanjutnya, kasan kurosu berubah nama menjadi kakuro. Maki dan perusahaannya, Nikoli berhasil menjual sekitar 1 juta buku Kakuro. Kakuro dimainkan pada sebuah tabel kotakkotak yang mirip dengan permainan teka teki silang. Di dalam kakuro, jumlah dari nilai input harus sama dengan petunjuk yang tertera di kiri atau di atas. Pemain hanya bisa memasukkan angka dari 1 hingga 9, sehingga jumlah angka sama dengan petunjuk. Tidak boleh terdapat angka yang sama pada baris dan kolom yang sama. Hanya akan ada satu solusi untuk setiap puzzle. Berikut adalah contoh permainan kakuro puzzle.

 

Pencarian jawaban Kakuro dilakukan dengan menggunakan algoritma pencarian Iterative Deepening Search (IDS). Pencarian jawaban Kakuro dengan algoritma pencarian IDS adalah sebagai berikut:

1. Pencarian dimulai dari kotak pertama, yaitu kotak-0. Apabila kotak-0 adalah kotak petunjuk, maka majukan indeks kotak dan lanjutkan pemeriksaan pada kotak-1. Kotak-1 hingga kotak-8 juga merupakan kotak petunjuk, sehingga pencarian berlanjut hingga kotak-9.
2. Pencarian dilanjutkan ke kotak-9. Kotak-9 kosong atau dianggap bernilai ’0’, tambahkan angka sekarang dengan satu = ’1’ dan uji angka ’1’ pada kotak-9. Ternyata angka ’1’ tidak menyalahi aturan, karena belum terdapat angka ’1’ pada baris pertama atau kolom pertama. Tempatkan angka ’1’ pada kotak-9.  Contoh pencarian jawaban kakuro. 
   

            

KELEBIHAN DAN KELEMAHAN

Adapun kelebihan dari sistem adalah sebagai berikut:

1. Sistem dapat digunakan untuk mencari jawaban dari permainan teka-teki Kakuro dengan menggunakan algoritma pencarian Iterative Deepening Search (IDS) sehingga pembuat soal Kakuro dapat menguji apakah soal yang telah dibuatnya mempunyai solusi atau tidak. 
2. Sistem juga dapat digunakan untuk membantu penggemar teka-teki Kakuro yang membutuhkan waktu dan tenaga yang relatif besar untuk mencari jawaban Kakuro secara manual.  
3.  Bila soal Kakuro tidak memiliki jawaban, maka sistem akan menampilkan pesan kesalahan. 
4. Sistem dapat menampilkan langkah-langkah pencarian IDS, sehingga user dapat melihat proses pencarian yang dilakukan oleh sistem.  
5. Sistem dapat mencari jawaban lebih cepat apabila digunakan pencarian cepat (sistem tidak mencatat langkah-langkah pencarian). 
6. User dapat memainkan Kakuro dengan langsung memasukkan angka pada kotak-kotak yang kosong. Apabila solusi Kakuro ditemukan, maka sistem akan menampilkan pesan. 

Adapun kelemahan dari sistem adalah sebagai berikut:

1. Sistem tidak memiliki suara dan animasi serta tidak mendukung efek 3 dimensi. 
2. Sistem tidak menyediakan permainan Kakuro dari level paling mudah hingga paling rumit. 
3. Sistem tidak dapat dijalankan secara mobile melalui web dan smartphone.

 

KESIMPULAN 

    Setelah menyelesaikan perancangan aplikasi penyelesaian permainan teka-teki Kakuro menggunakan algoritma pencarian IterativeDeepening Search (IDS), beberapa hal yang dapat disimpulkan adalah sebagai berikut: 

1. Aplikasi dapat digunakan untuk mencari jawaban dari permainan teka-teki Kakuro denganmenggunakan algoritma pencarian Iterative Deepening Search (IDS) sehingga pembuat soal Kakuro dapat menguji apakah soal yang telah dibuatnya mempunyai solusi atau tidak.  
2. Aplikasi juga dapat digunakan untuk membantu penggemar teka-teki Kakuro yang membutuhkan waktu dan tenaga yang relatif besar untuk mencari jawaban Kakuro secara manual.  
3. Bila soal Kakuro tidak memiliki jawaban, maka aplikasi akan menampilkan pesan kesalahan.
4. Aplikasi dapat menampilkan langkah-langkah pencarian IDS, sehingga user dapat melihat proses pencarian yang dilakukan oleh sistem.
5. Aplikasi dapat mencari jawaban lebih cepat apabila digunakan pencarian cepat (sistem tidak mencatat langkah-langkah pencarian).  
6. User dapat memainkan Kakuro dengan langsung memasukkan angka pada kotak-kotak yang kosong. Apabila solusi Kakuro ditemukan, maka sistem akan menampilkan pesan.
7. Aplikasi merupakan implementasi nyata dari kecerdasan buatan (artificial intelligence), terutama algoritma pencarian IDS untuk mencari penyelesaian dari suatu permasalahan, dalam hal ini soal Kakuro.  
   

DAFTAR PUSTAKA

 

https://ejurnal.stmik-budidarma.ac.id

https://setianarstn.blogspot.com/2019/10/informed-and-un-infromed-search.html

https://garudacyber.co.id/artikel/623-metode-metode-pencarian-buta-atau-blind-un-informed-search-pada-artificial-intelligence