Genetic algorithms applied to videogame testing

Abstract

En los últimos años, los métodos de testeo usados en videojuegos han consistido en expandir técnicas clásicas de testeo de software, como Unit Testing por ejemplo. Sin embargo en la época moderna, la mayor parte del testeo de un juego es llevada a cabo por un grupo de testers humanos que interactúan con el software y hardware. Hay casos en que un tester logra reproducir un bug una vez pero por diversos motivos no es capaz de reproducirlo después. Esto puede ser porque el bug en partícular puede ser difícil de reproducir para un ser humano (puede requerir inputs muy precisos), o la información obtenida al reproducirlo la primera vez es muy escasa. Volver a producir este tipo de errores para un tester humano puede tomar mucho tiempo. En esta memoria se propone una técnica basada en algoritmos genéticos, una técnica perteneciente al reino de la Inteligencia Computacional, para resolver este tipo de problemas. Usaremos algoritmos genéticos para crear secuencias de inputs a correr sobre un juego, y obtener feedback del juego para computar la función de fitness. Al definir una función de fitness con datos de un juego, de modo que su valor aumente mientras más cerca esté la secuencia de inputs de reproducir el error; podemos producir una secuencia de inputs que reproduce el bug con algoritmos genéticos. Desarrollamos un grupo de codificaciones para representar secuencias de inputs junto a sus respectivas funciones de crossover y mutación. Estas codificaciones fueron probadas y comparadas en tiempos de reproducción y total de fitness obtenida al realizar una tarea simple sobre una implementación del juego Asteroids en Github. Esto llevó al desarrollo de dos codificaciones, que fueron utilizadas para reproducir bugs en dos juegos open-source. Para cada juego logramos reproducir al menos uno de los bugs que nos enfrentamos, y analizamos los resultados para obtener más información sobre ellos. Contactamos a los desarrolladores y, guiados por ellos, realizamos un análisis más profundo de los resultados para obtener más detalles sobre los bugs usando nuestro software. La información obtenida de los análisis ayudó a los desarrolladores a confirmar teorías que tenían sobre estos problemas y a parchar estos bugs. El software desarrollado en la memoria es un primer paso en la aplicación de algoritmos genéticos de esta forma en la evolución de secuencias de inputs. A través de los experimentos llevados a cabo, algunas guías fueron desarrolladas para usar esta técnica para reproducir errores. Para que las herramientas desarrolladas sean usadas en la práctica, algunas funcionalidades tienen que ser añadidas para que los desarrolladores de juegos puedan visualizar y editar los contenidos de una secuencia de inputs.