Temas acerca de Inteligencia Artificial
Foto de Usuario
JesusMayuriH

Ranking Troomes
Mensajes: 8
Registrado: 07 May 2020, 11:36

APLICACIÓN DE LOS ALGORITMOS DE BÚSQUEDA EN LOS VIDEOJUEGOS BASADOS EN IA

Mensaje por JesusMayuriH » 10 May 2021, 21:36

La presencia de la Inteligencia Artificial y la aplicación de sus técnicas han permitido desarrollarse a cada sector de la industria de diferentes maneras, ya sea en la mejora de sus procesos y automatización, como en el perfeccionamiento de nuevos diseños de sus productos. Este último, se puede ver claramente reflejado en las empresas dedicadas a construir software basado en algoritmos o modelos relacionados a este campo de estudio, como lo son las desarrolladoras de videojuegos, que han tratado de mejorar la experiencia virtual, a partir de la evolución en las reacciones de los personajes y en la inteligencia de los enemigos predeterminados manejados por el propio juego, que llegan a aprender los actos que realizan los jugadores con los que se están enfrentando.
La mayoría de los videojuegos de estrategia, siempre han tratado de incorporar los sistemas de resolución de problemas, en los que los jugadores se enfrentan a elecciones entre una serie de alternativas, que conducen a tomar decisiones sucesivas hasta que el problema quede resuelto. En los inicios de la industria, se comenzaron a implementar en los juegos con adversario, los algoritmos de búsqueda como el Minimax, el cual prueba con todas las posibles jugadas y sus posibles efectos y se toman decisiones para minimizar la pérdida máxima esperada trabajando con una función de evaluación heurística. Los primeros programas que aplicaron esto, fueron los de ajedrez, a partir de los años 50s. “Los Álamos”, el primero de ellos corría en una computadora MANIAC, y era capaz de realizar 4 jugadas en 12 minutos. Los posteriores a este proyecto, son los de Bernstein o Anderson/Cody que se corrían en computadoras IBM de esos años y cada una trataba de incorporar mayor cantidad de jugadas o mejora en los criterios de juego. En la actualidad los juegos de ajedrez ya no usan exactamente ese algoritmo, sino que se usan técnicas que lo mejoran, como es el caso de Poda Alfa-Beta, la cual usa los árboles de búsqueda aprovechando Minimax, para hacer una exploración en profundidad y guardar información en base a dos umbrales, que son útiles para determinar el valor de las mejores jugadas encontradas para cada jugador. En mejor medida tanto NegaMax y su evolución NegaScout, pueden llegar a mejorar el rendimiento en juegos de ajedrez en un 10% estimado, siendo así las versiones más compactas del Minimax.
Aplicaciones más recientes como los videojuegos basados en Pacman, es decir, que los personajes realizan movimientos de persecución, “asustado” y de dispersión a lo largo de un escenario bidimensional con cierta cantidad de celdas, también hacen uso de algoritmos de búsqueda. Para este caso trabajan con el algoritmo A*, el cual considera un punto de inicio y un punto objetivo en las celdas del juego. Este algoritmo hace cálculos de costos de movimiento, como los explicados a continuación:
G(N): costo de moverse de una celda a otra.
H(N): costo de desplazamiento desde la celda analizada al objetivo.
F(N): costo general, calculado como G(N)+H(N).
Uno de los ejemplos de este tipo de videojuegos es “Lo que quiere mi país”, galardonado como mejor proyecto en el evento CONINFO 2015, que fue creado desde cero sin el uso de frameworks, solamente con HTML, CSS y JavaScript para que corra en la web. Este juego tiene como personajes a ladrones y policías, que actúan de manera similar a los fantasmas y el Pacman del juego base. Entre otros videojuegos que usan el también los algoritmos de Pathfinding, se tiene a Warcraft y Command and Conquer, los cuales representan su escenario de movimientos en un entorno dinámico en mapas con puntos de paso, obstáculos y mallas de navegación. Los algoritmos candidatos a resolver esta búsqueda de caminos, son: Dijkstra, BFS, búsqueda voraz, A*, búsqueda iterativa en profundidad IDA* y la búsqueda jerárquica. A pesar de que ofrece un tipo de solución óptima, el más básico de todos ellos es el de Dijkstra, ya que explora una gran cantidad de nodos para realizar su propósito, y por ello genera un alto consumo de memoria, siendo así no muy eficiente. Mientras que, el A*, es uno de los más eficientes, al ofrecer una respuesta aproximada, con un regular consumo y aceptable exploración de nodos y tiempo de ejecución con buena heurística, similar al comportamiento del algoritmo Voraz.

Conclusiones

Se ha apreciado la gran cantidad de algoritmos de búsqueda usados en los diversos videojuegos, tanto en los primigenios, nacidos a la par con la Inteligencia Artificial, como en los más modernos que tratan de ofrecer una mejor experiencia de juego al usuario, mediante esta disciplina, dándole la capacidad de optimizar el comportamiento móvil de los personajes. Cada tipo de juego merece cierto algoritmo, que ofrezca las mejores oportunidades de desempeño, a nivel de usuario y de recursos de hardware, y pueden ser desarrollados con el uso de herramientas básicas como las primeras computadoras o los lenguajes de marcado y estilo elementales de una página web, hasta motores gráficos modernos.

Referencias bibliográficas

[1] Aguilar, P. (2008). IA – Algoritmos de Juegos, de la Universidad Politécnica de Catalunya.
[2] Velasco, J. (2018). Aplicación de algoritmos de búsqueda en los videojuegos.
[3] Portillo, Á., & José, E. (2016). Análisis de algoritmos en videojuegos basados en Pacman: “Lo que quiere mi país”.


Jesus Mayuri Hidalgo
Estudiante de Ingeniería de Sistemas
FIIS - UNI
Responder