Comparison of search algorithms in strategy video game problems
Comparación de los algoritmos de búsqueda en problemas de videojuegos de estrategia
Autor
Castillo, José
Morán, Jayson
Lan, Ashley
Béliz Osorio, Nicholas
Metadatos
Mostrar el registro completo del ítemResumen
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.