Optimalisasi Penyelesaian Permainan pada Game Puzzle 8 dengan Perbandingan Algoritma A* dan Greedy

Abstract

Perkembangan game yang pesat serta beragam menjadikan game sebagai salah satu hiburan penghilang stress untuk manusia. Ada beberapa game yang diciptakan untuk mengasah kemampuan penggunanya namun ada pula game yang diciptakan hanya sebatas hiburan ringan. Game yang terlalu sulit untuk diselesaikan, bukan tidak mungkin akan membuat penggunanya malah menjadi stres dan berhenti memaikan permainan. Game yang cukup menguras pikiran salah satunya adalah game puzzle 8, yang mana pemain ditutuntut untuk mampu menyelesaikan permainan dengan menyusun setiap kotak permainan sehingga dapat tersusun secara berurut. Banyak metode yang dapat digunakan untuk membantu menyelesaikan permainan puzzle 8. Salah satunya adalah algoritma A-star. A-star digunakan untuk menyelesaikan permainan secara optimal dengan menggunakan fungsi heuristik. Yang mana heuristik merupakan salah satu teknik yang mengembangkan efisiensi dalam pencarian. Pembuatan proyek ini adalah untuk mengimplementasikan algoritma A-star dalam permainan puzzle 8 dengan menggunakan bahasa pemrograman Java. Dalam pengujian aplikasi algoritma A-star memiliki langkah yang lebih sedikit dibandingkan dengan algoritma Greedy, namun waktu yang dibutuhkan algoritma A-star lebih lama. Hal ini disebabkan karena A-star melakukan perhitungan biaya sebanyak dua kali, tetapi algoritma Greedy hanya satu kali. Setelah dilakukan pengujian dapat disimpulan bahwa algoritma A-star memberikan langkah optimal dalam penyelesaian puzzle 8 dilihat dari faktor jumlah langkah untuk menyelesaikan permainan.
Kata Kunci—Game, A-star, Penyelesaian, Optimal.

The development of a fast and diverse game makes the game as one of the stress relievers for humans. There are some games that are created to hone the ability of users, but there are also games that are created only limited to mild entertainment. Games that are too difficult to solve, it is not impossible that it will make users event stress and stop playing the game. One of the games that is enough to drain the mind is puzzle 8, where players are required to be able to cpmplete the game by arranging each game box so that they can be arranged in order. Many methods can be used to help solve puzzle 8 games. One of them is the A-star algorithm. A-star is used to finish the game optimally by using heuristic function. Which heuristics is one technique that develops efficiency in search. The making of this project is to implement the A-star algorithm in puzzle 8 using the Java programming language. In testing the A-star algorithm application has fewer steps compared to the Greedy algorithm, but the time required for the A-star algorithm is longer. This is because A-star calculates costs twice, but the Greedy algorithm is only one time. After testing it can be concluded that the S-star algorithm provides optimal steps in solving puzzle 8 viewed from the number of steps to complete the game.
Keywords—Game, A-star, Completion, Optimal.