IMPLEMENTASI ALGORITMA DEPTH LIMITED SEARCH PADA PERMAINAN PEG SOLITAIRE

 

IMPLEMENTASI ALGORITMA DEPTH LIMITED SEARCH

PADA PERMAINAN PEG SOLITAIRE

1. Algoritma Depth Limited Search

            Algoritma Depth Limited Search memberikan batas kedalaman pada algoritma Depth First Search (Russel & Norvig, 1995). Dengan algoritma Depth Limited Search,penelusuran Depth First Search data dibatasi sehingga tidak melakukan penelusuran terlalu  dalam. Algoritma Depth Limited Search adalah sebagai berikut:

            a) Tetapkan node awal dengan kedalaman = 0 dan tentukan batas kedalaman.

            b) Cek apakah node adalah node tujuan. Jika benar maka proses berhenti, jika tidak maka lanjut ke langkah c.

            c) Cek apakah kedalaman node sama dengan batas kedalaman yang telah ditentukan. Jika benar, maka lanjutkan proses dengan menelusur hanya node – node yang berada dalam batas kedalaman yang telah ditentukan dan belum dikunjugi dengan kembali kelangkah b. Jika tidak maka lanjutkan ke langkah d.

            d) Perluas node dan kembali ke langkah b.

        Gambaran kerja algoritma Depth Limited Search dapat digambarkan dalam bentuk tree. Tree merupakan sebuah graf tidak berarah dan merupakan jaringan bersambung yang tidak memiliki untai (loop) sehingga dengan demikian dapat disimpulkan bahwa sebuah tree dapat dibentuk dari graf sederhana karena graf sederhana tidak memiliki self loop ataupun edge parallel. Tree terdiri dari sekumpulan elemen. Elemen tree adalah akar atau root dan simpul. Derajat atau degree sebuah simpul menunjukkan jumlah anak pada simpul tersebut.

2. Permainan Peg Solitaire

             Peg Solitaire merupakan sebuah permainan dengan satu orang pemain. Permainan ini terdiri dari sebuah papan permainan dengan sejumlah kelereng. Papan permainan tersebut berisi sekumpulan lubang. Lubang–lubang tersebut akan terisi penuh dengan kelereng. Pada awal permainan, lubang tengah pasti dikosongkan. Peg Solitaire ini dimainkan dengan cara :

-         -Kelereng akan melompati kelereng lain menuju lubang kosong.

-         -Kelereng yang telah dilompati akan hilang atau keluar dari permainan.

-         -Permainan akan dianggap selesai apabila hanya tersisa satu kelereng.

         Strategi yang terbaik yang dapat dilakukan agar dapat menemukan solusi pada permainan Peg Solitaire adalah mengarahkan kelereng ke lubang bagian tengah dan menyelamatkan kelereng terisolasi yang terdapat di lubang–lubang bagian pinggir. Gerakan kelereng yang diperbolehkan adalah melangkah ke kanan, melangkah ke kiri, melangkah ke atas, dan ke bawah..

3. Hasil dan Pembahasan

            Sistem yang dibangun dari hasil penelitian ini menggunakan 8 form yang terdiri dari form utama, form jenis soal, form permainan untuk inggris dan eropa serta triangular, form tampil tree untuk inggris dan eropa serta triangular, from instruksi, dan form detail. Implementasi form permainan untuk papan versi inggris dapat dilihat pada gambar di bawah ini:

 

                                                        1. Form Permainan.

            GambarStruktur data yang dikembangkan antara lain struktur data untuk papan permainan, struktur data untuk bank soal, struktur data untuk soal sendiri, struktur data untuk fitur undo, struktur data untuk menentukan apakah papan berisi kelereng atau tidak, dan struktur data untuk penelusuran solusi permainan Peg Solitaire dengan algoritma Depth Limited Search. Penelusuran solusi dilakukan untuk menemukan jalur solusi menuju sisa 1 kelereng dengan algoritma Depth Limited Search dimana batas kedalamannya adalah jumlah kelereng - 1. Berikut ini adalah satu contoh kasus penyelesaian suatu kondisi pada permainan Peg Solitaire versi inggris dengan ukuran 3 x 3 dengan menggunakan penelusuran pohon Depth Limited Search. Contoh penerapan ini menggunakan jenis soal cross yang terdiri dari 6 kelereng.

 

Gambar 2. algoritma Depth Limited Search pada papan versi inggris dengan tipe soal tanda plus.

Contoh di atas adalah contoh kasus dengan menggunakan jenis soal seperti tanda plus dimana pengerjaannya dilakukan secara manual. Berikut ini adalah hasil dari contoh kasus serupa yang dikerjakan secarlangsung oleh sistem.

.

                  Berdasarkan hasil pengujian di atas, tingkat kesulitan soal Peg Solitaire dapat digolongkan berdasarkan waktunya. Semakin lama waktu yang diperlukan sistem untuk menghasilkan pohon penelusuran dan jalur solusi untuk soal tersebut, maka soal tersebut dapat digolongkan sebagai soal yang cukup sulit. Soal digolongkan menjadi tiga level, yaitu level mudah, menengah, dan sulit. Level mudah dapat diselesaikan oleh sistem hanya dalam waktu kurang dari 1 detik. Sedangkan soal menengah dapat diselesaikan dalam waktu antara 1 sampai 59 detik. Soal sulit adalah soal yang membutuhkan waktu paling lama yaitu lebih dari satu menit. Penggolongan tingkat kesulitan soal- soal di atas dapat dilihat pada tabel berikut:

                  Berdasarkan pengujian sistem, kesulitan dari pemecahan solusi juga disebabkan oleh ukuran papan yang cukup besar sehingga membutuhkan waktu yang cukup lama untuk menelusur hingga ditemukan solusi. Selain itu, jumlah kelereng dan letak kelereng juga mempengaruhi lama atau tidaknya waktu penelusuran. Semakin acak posisi kelereng dan berjauhan satu sama lain, maka akan semakin sulit dalam melakukan penelusuran. Posisi kelereng yang tersebar berjauhan di papan berukuran besar pun semakin mempersulit penelusuran. Berdasarkan hasil pengujian di atas, juga ditemukan salah satu soal yaitu soal dengan ID 7 yang tidak menemukan goal berupa sisa 1 kelereng. Hal ini disebabkan karena saat dilakukan penelusuran terhadap kondisi tersebut, tidak ada kemungkinan perpindahan kelereng yang menghasilkan jalur solusi menuju sisa 1 kelereng. Terakhir, berdasarkan pengujian keseluruhan, ada dua kemungkinan suatu kondisi tidak berhasil menemukan solusi. Kemungkinan pertama disebabkan oleh penelusuran terhadap kondisi tersebut yaitu tidak ada kemungkinan perpindahan kelereng yang menghasilkan jalur solusi menuju sisa 1 kelereng.

 

3. Kesimpulan

a. Algoritma Depth Limited Search yang diterapkan pada sistem permainan Peg Solitaire dalam tugas akhir ini mampu menemukan solusi namun terbatas hanya pada papan inggris ukuran 3 x 3, dan papan triangular dengan ukuran 4 x 4, 5 x 5, serta 7 x 7.

b. Algoritma Depth Limited Search yang diterapkan oleh sistem ini membutuhkan waktu yang singkat untuk kasus – kasus kecil dengan jumlah kelereng kurang dari 16 dengan syarat posisi kelereng yang saling berdekatan satu sama lain atau dengan kata lain posisi kelereng tidak tersebar berjauhan namun membutuhkan waktu yang lama dalam kasus – kasus besar yaitu kasus – kasus dengan jumlah kelereng lebih dari 16 dan posisi kelereng yang tersebar berjauhan. Hal ini disebabkan oleh algoritma Depth Limited Search yang diterapkan pada sistem ini adalah algoritma Depth Limited Search murni dengan metode iteratif.

c. Algoritma Depth Limited Search membatasi kedalaman yaitu jumlah kelereng – 1.

d. Tanpa ada pembatasan level, solusi tetap dapat ditemukan.

e. Algoritma Depth Limited Search mampu menangani tidak ditemukannya solusi dengan cara mendeteksi semua posisi kereleng sehingga apabila posisi kelereng tidak memungkinkan lagi untuk dipindahkan ke posisi lain maka sistem akan berhenti bekerja.

f. Pengujian sistem yang dilakukan dengan menguji 10 soal, 9 soal berhasil diselesaikan dan 1 soal tidak berhasil diselesaikan. (R, 2011)

Daftar Pustaka:

R, G. T. (2011). IMPLEMENTASI ALGORITMA DEPTH LIMITED SEARCH.