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
https://doi.org/10.25139/inform.v7i2.4484
Abstract views: 327 , PDF downloads: 499
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
Issue
Vol. 7 No. 2 (2022)
Section
Articles

Copyright (c) 2022 Bonifacius Indriyono, Widyatmoko

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Authors who publish with Inform: Jurnal Ilmiah Bidang Teknologi Informasi dan Komunikasi agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. 

  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.

  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.