DEPTH LIMITED SEARCH PADA PERMAINAN PEG SOLITAIRE
Abstraksi
Permainan Peg Solitaire adalah permainan single player yang terdiri dari sebuah papan dan sejumlah kelereng. Papan permainan Peg Solitaire terdiri dari banyak jenis antara lain papan jenis inggris, eropa, triangular dan masih banyak jenis papan permainan Peg Solitaire yang lain.
Pemain permainan Peg Solitaire terkadang sulit menentukan keputusan langkah yang tepat. Oleh karena itu, disediakan bantuan berupa hint yang membantu pemain saat pemain menentukan langkah. Salah satu algoritma yang dapat diterapkan pada hint permainan Peg Solitaire adalah algoritma Depth Limited Search.
Penerapan algoritma Depth Limited Search pada hint permainan Peg Solitaire di papan permainan versi inggris ukuran 3 x 3 dan triangular berukuran 4 x 4, 5 x 5, serta 7 x 7, mampu menemukan solusi yaitu sisa satu kelereng serta mampu menangani apabila tidak menemukan solusi. Penerapan algoritma Depth Limited Search pun mampu menampilkan semua perpindahan langkah hingga ditemukan sisa 1 kelereng. Hal ini dibuktikan dengan cara menguji 10 soal pada sistem. Dari hasil pengujian 10 soal pada sistem, 9 soal berhasil diselesaikan dan 1 soal gagal diselesaikan karena tidak menemukan solusi berupa sisa 1 kelereng.
1. Pendahuluan
Peg solitaire adalah salah satu permainan komputer. Permainan Peg Solitaire adalah permainan yang terdiri dari sebuah papan permainan dan sejumlah kelereng. Permainan Peg Solitaire ini memiliki tujuan untuk mencari solusi dari kondisi awal menuju kondisi akhir yaitu sisa satu kelereng. Untuk menentukan solusi permainan Peg Solitaire akan digunakan sebuah algoritma.
Algoritma yang akan digunakan untuk menemukan solusi pada permasalahan permainan Peg Solitaire adalah algoritma Depth Limited Search. Algoritma Depth Limited Search adalah algoritma blind search Algoritma ini diharapkan dapat menemukan solusi dari kondisi awal menuju kondisi akhir yaitu menyisakan satu kelereng pada papan permainan Peg Solitaire versi eropa dan inggris dengan ukuran masing – masing 3 x 3, 5 x 5 , dan 7 x 7 serta versi triangular ukuran 4 x 4, 5 x 5 , dan 7 x 7 serta mampu menangani kemungkinan solusi tidak ditemukan. Batasan masalah dalam penelitian ini antara lain papan permainan untuk implementasi algoritma hanya papan versi inggris ukuran 3 x 3 dan triangular ukuran 4 x 4, 5 x 5, serta 7 x 7, ada pengembangan soal dan soal random untuk papan versi inggris ingris ukuran 3 x 3 serta triangular 4 x 4, 5 x 5, dan 7 x 7, pemain dapat memasukkan jumlah lubang kosong dengan batas maksimal setengah dari jumlah total lubang papan, dan algoritma akan diterapkan pada menu hint untuk membantu pemain memilih langkah untuk mencapai sisa satu kelereng.
2. Landasan Teori
2.1.Kecerdasan Buatan
Kecerdasan buatan merupakan cabang teknologi yang relatif baru. Prinsip kecerdasan buatan diawali sejak muncul komputer modern antara tahun 1940-1950. Kecerdasan buatan berkembang pesat seiring dengan berkembangnya teknologi komputer yang dari hari ke hari bertambah maju.
Ada 2 bagian utama yang dibutuhkan untuk aplikasi kecerdasan buatan yaitu basis pengetahuan atau knowledge base yang berisi fakta-fakta, teori, pemikiran serta hubungan antara satu dengan lainnya dan motor inferensi atau inference engine yaitu kemampuan menarik kesimpulan berdasarkan pengalaman. Kecerdasan buatan kini telah diterapkan pada banyak bidang.
Salah satu bidang yang menerapkan kecerdasan buatan adalah permainan atau game. Game berasal dari kata bahasa inggris yang memiliki arti dasar permainan.Permainan dalam hal ini merujuk pada pengertian kelincahan intelektual atau intellectual playability. Game atau permainan juga dapat dikelompokkan berdasarkan tipenya yaitu deterministic game dan chance. Permainan catur, Othello, dan Peg Solitaire Termasuk dalam jenis permainan deterministic-perfect information karena memiliki informasi yang lengkap mengenai cara mencapai tujuan atau goal. Sedangkan jenis permainan chance adalah permainan yang memiliki banyak kemungkinan – kemungkinan secara acak, belum dapat terlihat tujuan akhirnya.
2.2. 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 dikunjungi 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.3. 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.
KESIMPULAN
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.
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.
Algoritma Depth Limited Search membatasi kedalaman yaitu jumlah kelereng –1
Tanpa ada pembatasan level, solusi tetap dapat ditemukan. Algoritma Depth Limited Search mampu menangani tidak ditemukannya solusi dengan cara mendeteksi semua posisi kelereng sehingga apabila posisi kelereng tidak memungkinkan lagi untuk dipindahkan ke posisi lain maka sistem akan berhenti bekerja.
Pengujian sistem yang dilakukan dengan menguji 10 soal, 9 soal berhasil diselesaikan dan 1 soal tidak berhasil diselesaikan.
daftar pustaka
https://www.neliti.com/id/publications/66816/implementasi-algoritma-depth-limited-search-pada-permainan-peg-solitaire
Tidak ada komentar:
Posting Komentar