Comparison of search algorithms in strategy video game problems

Revista de Iniciación Científica

View Publication Info
 
 
Field Value
 
Title Comparison of search algorithms in strategy video game problems
Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
 
Creator Castillo, José
Morán, Jayson
Lan, Ashley
Béliz Osorio, Nicholas
 
Description Strategy games have always been very liked by people. Games such as chess and checkers, to mention a few that are widely played, have created rivalry between players and have even become sports played by professionals. With the rise of artificial intelligence, a new window opens to test whether computers can outperform humans. From these ideas, algorithms have emerged that seek to solve problems through different strategies. In this article, the minimax and alpha-beta algorithms, their definition, functionality and complexity were studied. These algorithms were implemented in the emulation of the Lara Croft Go game, which was programmed in the Java language using the NetBeans IDE. The application consists of a game where a human faces an AI that was programmed with both algorithms and is defined by different factors, who is the best solving the game. Data collection is defined by the movements that each algorithm makes to complete the levels and the number of states it generates in the search for the solution. Based on the data collected during the execution of the algorithms, it is shown that the most efficient algorithm in finding the solution of the implemented levels is the Alpha-Beta search algorithm, since it generates fewer states, therefore, it evaluates less nodes and reaches a solution in less time than the Minimax search algorithm.
Los juegos de estrategia siempre han sido muy gustados por las personas. Juegos como el ajedrez y las damas, por mencionar algunos muy jugados. Han creado rivalidad entre jugadores y hasta se han convertido en deportes jugados por profesionales. Con el surgir de la inteligencia artificial se abre una nueva ventana para probar si las computadoras pueden superar a los humanos. De estas ideas han surgido algoritmos que buscan solucionar problemas a través de diferentes estrategias. En este artículo se estudiaron los algoritmos de minimax y alfa-beta, su definición, funcionalidad y complejidad. Estos algoritmos se implementaron en la emulación del juego de Lara Croft Go, que fue programado en el lenguaje de Java utilizando el IDE de NetBeans. La aplicación consiste en un juego donde un humano se enfrenta a una IA que fue programada con ambos algoritmos y se define por diferentes factores, quien es el mejor resolviendo el juego. La recolección de los datos es definida por los movimientos que realice cada algoritmo para completar los niveles y la cantidad de estados que genere en la búsqueda de la solución. Basados en los datos recopilados durante la ejecución de los algoritmos, se demuestra que el algoritmo más eficiente en la búsqueda de la solución de los niveles implementados es el algoritmo de búsqueda Alfa-Beta, ya que genera menos estados, por lo tanto, evalúa menos nodos y llega a una solución en un tiempo menor que el algoritmo de búsqueda Minimax.
 
Publisher Universidad Tecnológica de Panamá
 
Date 2020-12-15
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
 
Format application/pdf
text/html
 
Identifier https://revistas.utp.ac.pa/index.php/ric/article/view/2897
10.33412/rev-ric.v6.2.2897
 
Source Revista de Iniciación Científica; Vol. 6 Núm. 2 (2020): Revista de Iniciación Científica; 60-66
2413-6786
2412-0464
 
Language spa
 
Relation https://revistas.utp.ac.pa/index.php/ric/article/view/2897/3609
https://revistas.utp.ac.pa/index.php/ric/article/view/2897/3636
 
Rights Derechos de autor 2020 Creative Commons Reconocimiento-NoComercial-CompartirIgual 4.0.
http://creativecommons.org/licenses/by-nc-sa/4.0/
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library