Analysis of A* Algorithm Optimization and Breadth First Search in the Water Teapot Game

  • Bonifacius Indriyono Information System, Dian Nuswantoro University http://orcid.org/0000-0001-8805-9047
  • Widyatmoko Information System, Universitas Dian Nuswantoro
Abstract views: 118 , PDF downloads: 153
Keywords: Artificial Intelligence, Water Teapot Game, A* Algorithm Optimization, Breadth First Search Algorithm

Abstract

Artificial Intelligence (AI) is a branch of computer science that focuses on learning how computers can work or perform as well as humans or even better than humans. The development of artificial intelligence can be used as a benchmark for technological developments. Many problems can be solved using this artificial intelligence concept. One of them is a water jug ​​logic game. The water jugs problem is a game requiring converting a situation into another desired situation using a certain set of operations. The objective of this game is for players to develop their deductive reasoning skills by figuring out how to move x litters of water from one teapot to another. To accomplish this, they will refer to the beginning value that has to be filled in each teapot and the end value that needs to be filled in each teapot. Using the A* algorithm and the Breadth-First Search (BFS) algorithm, which both fall under the umbrella of artificial intelligence, it is possible to find a solution to this issue. The A* algorithm is a Best First Search algorithm that combines Uniform Cost Search and Greedy Best-First Search, while the Breadth-First Search algorithm is a graph search algorithm that performs a wide search at each level. This study analyzed the effectiveness of the A* and BFS algorithms in solving the water jug ​​logic problem, both from the number of steps and the time required for completion. The results of the tests were carried out, and it is known that the BFS algorithm is more effective than the A* algorithm because the BFS algorithm can provide a number of alternative solutions to the water jug ​​logic problem with various conditions.

References

Wijaya,E., "Analysis of the Use of the Breadth First Search Algorithm in the Concept of Artificial Intelligence", TIME Journal, Vol. II No 2, p. 18-26, 2013, ISSN : 2337 – 3601

Dedi, N, Sri, W. "Development of Learning Media for Tracking Systems in Artificial Intelligence Subjects Based on Mutimedia". Journal of Informatics Engineering. 2014; Vol. 2 No. 1; p. 738-748.

Muclisin, R. Artificial intelligence. Yogyakarta: Graha Ilmu. 2019.

Suyanto. Artificial Intelligence: Search, Reasoning, Planning and Learning. Bandung : Informatika. 2014.

Widodo, B. AI For Beginners. Yogyakarta : Andi Offset. 2014.

Harianja, F., "Application of the A* Algorithm to Optimization Problems for Dynamic Water Solution Search". Pelita Informatika Journal, Vol. IV, No. 3, August, 2013, ISSN : 2301-9425

Siagian, E.R., "Water Jug Simulation Software Using the Breadth First Search Method". Pelita Informatika Journal, Vol. 6, No. 2, Oct, 2017, ISSN 2301-9425, p. 206-209.

Parlaungan, T.F.,; Tugimin, I.," Software for Searching for Solutions to Water Bottle Problems (Waterjug Problem) Using the Breadth First Search (BFS) Algorithm". Journal of Information and Communication Technology. Vol. 2 No. 1, Oct, 2021, ISSN: 2252-4517.

Man, Y.K., "Solving the General Two Water Jugs Problem via an Algorithmic Approach". Proceedings of the International MultiConference of Engineers and Computer Scientists. IMECS. Vol I, March., 2015.

Saxena, D., et al., "A Cognitive Approach to solve Water Jugs Problem". International Journal of Computer Applications. Vol124, No.17, August ,2015 .

Man, Y.K., "A Non-heuristic Approach to the General Two Water Jugs Problem". Journal of Communication and Computer 10. July, 2013, p. 904-908.

Sukardi., Competency Education Research Methodology and Practice. Jakarta: PT Bumi Aksara. 2011.

Sugiyono. Quantitative, Qualitative and R&D Research Methods. Bandung : Alfabeta. 2013.

Suharsimi, A. Research Procedure A Practice Approach Revised Edition. Jakarta : Rineka Cipta. 2010.

Zai, et al, "Shortest Route Simulation of Tourism Locations in Nias Using Breadth First Search and Tabu Search Methods.", InFact Journal, Vol. 2 No. 1. 2016

Wahyuni, E., et al., "Three-dimensional Explosion Crack Modeling For Serious Games", National Seminar on Information Technology and Multimedia. STMIK AMIKOM Yogyakarta.. ISSN : 2302-3805. P. 13-1-13.6. 2013

Alkindi, U., et al.," Implementation of the Breadth First Search Algorithm in Pacman to Regulate Character Movement.", Journal of Computer Research (JURIKOM), Vol. 5 No. 6. 2018

Sutojo, et al, Artificial Intelligence. Yogyakarta: Andi. 2011.

Setiawan, K., et al,." Calculating the Shortest Route Using A* Algorithm with Euclidean Distance Function.", National Seminar on Information and Communication Technology (SENTIKA). Yogyakarta. 2018

Nugraeni, R.A.., et al," Application of the A* Algorithm in Completing the Shortest Route for the Distribution of Goods.", Unnes Journal of Mathematics. Vol. 4 No. 1. p-ISSN 2252-6943 e-ISSN 2460-5859.

Hermanto, D.; Dermawan, S., "Application of the A-Star Algorithm as the Shortest Route Finder on the Hexapod Robot". National Journal of Electrical Engineering, Vol. 7, No. 2, p-ISSN: 2302-2949, e-ISSN: 2407 – 7267. 2018

Taufiq, P.J., et al.," Implementation and Analysis of the A*(Star) Algorithm to Determine Paths With Multiple Goals in Npc(Non-Playable Character) Movements". e-Proceeding of Engineering. Vol.2, No.,3. p. 7800. ISSN : 2355-9365. 2015

Nuryoso, Y.H., et al., "Application of the A* Algorithm in Searching for the Shortest Route on Angkot Routes in Sukabumi City". Journal of Bachelor of Informatics Engineering. Vol. 8, No. 1., e-ISSN 2338-5197, p. 21-35. 2020

Suyanto. Artificial Intelligence Search, Reasoning, Planning and Learning. Bandung : Informatics.2014

Pramudhita, A.C,; Muljono. "City Nearest BRT Stop Search System Application Semarang Using Android-Based A* Method". Resti Journal (System Engineering and Information Technology), Vol. 2 No.1, p.430-436. 2018.

Indriyono, B.V, ;Widyatmoko, “Optimization of Breadth-First Search Algorithm forPath Solutions inMazyin Games”. International Journal of Artificial Intelligence & Robotics (IJAIR). Vol 3, No. 2, e-ISSN 2686-6269, p. 58-66. 2021

Published
2022-07-27
How to Cite
Indriyono, B., & Widyatmoko. (2022). Analysis of A* Algorithm Optimization and Breadth First Search in the Water Teapot Game. Inform : Jurnal Ilmiah Bidang Teknologi Informasi Dan Komunikasi, 7(2), 88-95. https://doi.org/10.25139/inform.v7i2.4484
Section
Articles