Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia

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 un...

Full description

Bibliographic Details
Main Authors:	Castillo, José, Morán, Jayson, Lan, Ashley, Béliz Osorio, Nicholas
Format:	Online
Language:	spa
Published:	Universidad Tecnológica de Panamá 2020
Online Access:	https://revistas.utp.ac.pa/index.php/ric/article/view/2897

id	RIC2897
record_format	ojs
spelling	RIC28972022-01-13T19:14:59Z Comparison of search algorithms in strategy video game problems Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia Castillo, José Morán, Jayson Lan, Ashley Béliz Osorio, Nicholas 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. Universidad Tecnológica de Panamá 2020-12-15 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion application/pdf text/html https://revistas.utp.ac.pa/index.php/ric/article/view/2897 10.33412/rev-ric.v6.2.2897 Revista de Iniciación Científica; Vol. 6 Núm. 2 (2020): Revista de Iniciación Científica; 60-66 2413-6786 2412-0464 spa https://revistas.utp.ac.pa/index.php/ric/article/view/2897/3609 https://revistas.utp.ac.pa/index.php/ric/article/view/2897/3636 Derechos de autor 2020 Revista de Iniciación Científica http://creativecommons.org/licenses/by-nc-sa/4.0
institution	Universidad Tecnológica de Panamá
collection	Revista de Iniciación Científica
language	spa
format	Online
author	Castillo, José Morán, Jayson Lan, Ashley Béliz Osorio, Nicholas
spellingShingle	Castillo, José Morán, Jayson Lan, Ashley Béliz Osorio, Nicholas Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
author_facet	Castillo, José Morán, Jayson Lan, Ashley Béliz Osorio, Nicholas
author_sort	Castillo, José
description	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.
title	Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
title_short	Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
title_full	Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
title_fullStr	Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
title_full_unstemmed	Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
title_sort	comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
title_alt	Comparison of search algorithms in strategy video game problems
publisher	Universidad Tecnológica de Panamá
publishDate	2020
url	https://revistas.utp.ac.pa/index.php/ric/article/view/2897
work_keys_str_mv	AT castillojose comparisonofsearchalgorithmsinstrategyvideogameproblems AT moranjayson comparisonofsearchalgorithmsinstrategyvideogameproblems AT lanashley comparisonofsearchalgorithmsinstrategyvideogameproblems AT belizosorionicholas comparisonofsearchalgorithmsinstrategyvideogameproblems AT castillojose comparaciondelosalgoritmosdebusquedaenproblemasdevideojuegosdeestrategia AT moranjayson comparaciondelosalgoritmosdebusquedaenproblemasdevideojuegosdeestrategia AT lanashley comparaciondelosalgoritmosdebusquedaenproblemasdevideojuegosdeestrategia AT belizosorionicholas comparaciondelosalgoritmosdebusquedaenproblemasdevideojuegosdeestrategia
_version_	1781402542141341696

Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia

Similar Items