Backtracking and k-Nearest Neighbour for Non-Player Character to Balance Opponent in a Turn-Based Role Playing Game of Anagram

Yosa Aditya Prakosa(1*), Alfa Faridh Suni(2),

(1) Universitas Negeri Semarang
(2) Teknik Elektro Fakultas Teknik Universitas Negeri Semarang
(*) Corresponding Author
DOI: https://doi.org/10.23917/khif.v8i2.16902

Abstract

Anagram is a turn-based role-playing game where two players construct words by arranging given letters. A significant aspect of playing a game is the challenge. A good challenge comes from an opponent with a close ability. In a two-player game like Anagram, the second player can be a nonhuman player called Non-Playable Character (NPC). A balanced game is more engaging. Therefore, it is imperative to insert artificial intelligence (AI) into an NPC to make it possess a balance ability. This study investigates the AI algorithm that is the most appropriate to make a balance NPC for Anagram games. We tested three scenarios: Descending AI, Random AI, and AI with k-Nearest Neighbour (k-NN). Descending AI gets an Anagram solution by selecting a word with the highest score from all possible answers. Random AI picks a word randomly from the possible answers, while AI with k-NN chooses a word closest to one of the human players. The results show that Descending AI is the best algorithm to make the strongest NPC, which always gets the highest score, followed by Random AI and AI with k-NN. However, AI with the k-NN algorithm makes the constructed NPC has the highest number of turns at an average of 18, while Descending AI gets 14 turns and Random AI has 15 turns. Looking at the remaining lives at the end of the game, AI with k-NN makes the NPC has 25 lives left, while Descending AI has 59 lives, and Random AI has 48 lives. Less remaining lives suggest that NPC containing AI with the k-NN algorithm matches closer to the human player and therefore is more suitable for Anagram NPC.

Keywords

anagram; artificial intelligence; game; non-player character

Full Text:

PDF

References

M. A. Rahman, “The Effectiveness of Anagram on Students ’ Vocabulary Size,” J. IAIN Palangkaraya, no. December, pp. 129–139, 2016.

C. T. Panagiotakopoulos and M. E. Sarris, “‘Playing with words’: Effects of an anagram solving game-like application for primary education students,” Int. Educ. Stud., vol. 6, no. 2, pp. 110–126, 2013, doi: 10.5539/ies.v6n2p110.

I. Kuswardayan, R. Rahman, and N. Suciati, “Design and Implementation of Random Word Generator using Backtracking Algorithm for Gameplay in Ambrosia Game,” Int. J. Comput. Appl., vol. 158, no. 6, pp. 27–30, 2017, doi: 10.5120/ijca2017912822.

R. D. Pertiwi, “Planning of Making the Introducing Edifice Game,” no. December, pp. 12–13, 2014.

D. Ratanajaya and H. A. Wibawa, “Implementasi Kecerdasan Buatan dalam Menentukan Aksi Karakter pada Game RPG dengan Logika Fuzzy Tsukamoto,” Khazanah Inform. J. Ilmu Komput. dan Inform., vol. 4, no. 2, p. 82, 2018, doi: 10.23917/khif.v4i2.6744.

M. I. A. Putera and D. H. Murti, “Peningkatan Kecerdasan Computer Player Pada Game Pertarungan Berbasis K-Nearest Neighbor Berbobot,” JUTI J. Ilm. Teknol. Inf., vol. 16, no. 1, p. 90, 2018, doi: 10.12962/j24068535.v16i1.a710.

M. Abdi, D. Herumurti, and I. Kuswardayan, “Analisis Perbandingan Kecerdasan Buatan pada Computer Player dalam Mengambil Keputusan pada Game Battle RPG,” JUTI J. Ilm. Teknol. Inf., vol. 15, no. 2, p. 226, 2017, doi: 10.12962/j24068535.v15i2.a671.

V. Vorachart and H. Takagi, “Evolving fuzzy logic rule-based game player model for game development,” Int. J. Innov. Comput. Inf. Control, vol. 13, no. 6, pp. 1941–1951, 2017, doi: 10.24507/ijicic.13.06.1941.

G. Grund, P. M. Nilsson, M. Larsson, O. Olsson, T. Foughman, and V. Gustafsson, “Realistic NPCs in Video Games Using Different AI Approaches,” no. June, 2016.

M. Gwon, E. Goh, C. Sohn, and A. R. B. Ai, “The VR Trip Simulator with Multi Networking of Rule-based Model,” vol. 13, no. 22, pp. 15754–15757, 2018.

E. bagus Susanto, M. K. Triawan adi cahyanto, and pd M. Reni umilasari S, “Analisis Perbandingan Algoritma Naive Bayes Dan k-NN Untuk Klasifikasi Multi Dataset,” no. 1410651097, 2019.

H. Warpefelt, The Non-Player Character: Exploring the believability of NPC presentation and behavior, no. 16. 2016.

R. D. Agustin, “Komponen Konsep dan Desain Game,” J. Ilm. Teknol. Inf. Terap., vol. III, no. 2, 2017.

E. Siswanto and A. F. Suni, “Aksi Penyerangan Non-Player Character ( NPC ) Menggunakan Metode Naïve Bayes Pada Shooter Game,” J. Teknol. Inf. dan Ilmu Komput., vol. 8, no. 6, 2021, doi: 10.25126/jtiik.202183804.

F. B. Adi, M. Hariadi, and I. K. E. Purnama, “Simulasi Perilaku Tempur Pada Sekumpulan NPC Berbasis Boid,” 2016.

M. Kopel and T. Hajas, “Implementing AI for Non-player Characters in 3D Video Games,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 10751 LNAI, no. January 2018, pp. 610–619, 2018, doi: 10.1007/978-3-319-75417-8_57.

Article Metrics

Abstract view(s): 635 time(s)
PDF: 546 time(s)

Refbacks

  • There are currently no refbacks.