Perpustakaan judul masih dalam tahap pengembangan, admin siap menampung kritik dan saran
Analisis Perbandingan Algoritma Dynamic Weighting A Dan Algoritma Simplefied Memory Bounded A Untuk Mencari Langkah Optimal Dalam Penyelesaian Permanan Peg Solitaire
Fandy Agung Prasetyo NIM. (2016) | Skripsi | Teknik Informatika
Bagikan
Ringkasan
Permainan peg solitaire merupakan salah satu board game populer di dunia yang dapat dimainkan oleh satu orang pemain. Permainan asah otak ini mempunyai aturan untuk mengeksekusi beberapa kelereng menjadi satu buah kelereng dengan melewati atau menepati jalur yang tidak terisi oleh kelereng lain. Kesalahan yang sangat mungkin terjadi pada permainan ini adalah adanya dua atau tiga peg yang letaknya saling berjauhan. Hal ini terjadi karena kesalahan dalam menentukan langkah dan menyebabkan permainan tidak dapat terselesaikan. Kecerdasan buatan terdapatdua teknik pencarian yaitu pencarian buta dan pencarian terbimbing (heuristic). Algoritma yang dapat digunakan dalam pencairan terbimbing dua diantaranya adalah algoritma Dynamic Weighting A* (DWA*) dan algoritma Simplified Memory- Bounded A (SMA*). Algoritma DWA* adalah algoritma pencarian rute terpendek yang baik dan dapat memberikan solusi yang tepat dengan penggunaan memori yang kecil. Sedangkan algoritma SMA* memiliki kelebihan yaitu dapat melakukan pencarian dengan cepat dan membutuhkan memori yang lebih kecil dibandingkan dengan algoritma A*, maka dilakukan perbandingan antara algoritma DWA* dan algoritma SMA* untuk mencari langkah optimal dalam menyelesaikan permainan peg solitaire untuk menganalisis algoritma mana yang lebih baik antara algoritma DWA dan algoritma SMA. Berdasarkan hasil pengujian, untuk kasus model papan permainan dengan jumlah peg yang lebih sedikit yaitu pada papan plus, eight, dan fireplace algoritma DWA dan SMA masih dapat menemukan solusi. Akan tetapi, untuk kasus papan pyramid, arrow, dan solitaire algoritma DWA dan SMA tidak dapat menemukan solusi karena memori yang dibutuhkan melebihi kapasitas. Dilihat berdasarkan waktu penyelesaian algoritma DWA lebih unggul dalam kecepatan daripada algoritma SMA untuk menyelesaikan permainan peg solitaire untuk kasus pada papan plus, fireplace dan eight.
Ringkasan Alternatif
There are two techniques of artificial intelligence finding that a blind search and guided search (heuristic). In a guided search there are several algorithms that can be used two of which are Dynamic Weighting A * (DWA *) algorithms and Simplified Memory-Bounded A* (SMA*) algorithm. Dynamic weighting A* (DWA*) algorithms is the shortest route search algorithm is good. DWA* algorithm can provide the right solution with fast execution time and memory usage are small. While the Simplified Memory-Bounded A * (SMA *) algorithm is the shortest path search algorithm and a heuristic search. This algorithm has the advantage of able to search quickly and requires a smaller memory than the A* algorithm. Game peg solitaire is one of the popular board game in the world that can be played by one player. Peg Solitaire is played using several sets of marbles and a board with holes. In this game of marbles, or referred to as a peg, is filled so as to form a wide range of models of the game. Peg Solitaire is a brain teaser or logic using 7x7 sized board that is commonly called a board English Style. At this brain teasers have rules to execute some marbles into one of marbles to pass or keep track not occupied by other marbles. Based on test results, it can be concluded that the Dynamic Weigthing A* algorithm is superior in speed and accuracy than Simplified Memory-Bounded A* algorithms for finding an optimal step in thecompletion of Peg Solitaire game to model plus board, fireplace and eight.But for several models of other boards, such as the pyramid, arrow, andsolitaire can not find a solution because the memory used to store thepossible solutions is not sufficient.