NEAT aplicado a Tetris

Abstract

Este proyecto busca entrenar una Inteligencia Artificial (IA) para jugar Tetris usando el algoritmo NeuroEvolution of Augmenting Topologies (NEAT). Este algoritmo consiste en la implementación de una red neuronal añadiendo conceptos de los algoritmos genéticos para el ajuste de pesos y creación de nuevas neuronas y conexiones. Esto permite entrenar modelos que descubran una estructura mínima para aprender a resolver el problema en cuestión. Este proyecto es un ejemplo simple de un problema. Si consigue aprender a resolver el Tetris se puede pasar a problemas más complejos que se puedan asemejar a problemas de la vida real a resolver. Se ha desarrollado una versión simple de Tetris para que el agente pueda hacer los mismos movimientos que los de un jugador. El agente se ha entrenado usando distintas entradas (tablero completo o altura columnas) y varias modalidades para las salidas (movimientos individuales cada fotograma o posiciones determinadas y posteriormente realizar los movimientos para llegar a esas posiciones) con la esperanza de que alguna combinación mostrase una mejoría significativa y así poder seguir el entrenamiento de la IA con la mejor de esas combinaciones de entradas/salidas. A pesar de que los resultados del aprendizaje no han sido totalmente satisfactorios, sí que se detecta una mejoría desde la táctica inicial (generalmente soltar todas las piezas en el mismo lugar) a una estrategia de juego ligeramente más compleja (colocar las piezas en tres columnas: izquierda, derecha y centro). Aunque no haya logrado aprender a hacer líneas de forma continua es posible que pueda aprender con suficientes generaciones, ya que una red neuronal convencional es capaz de aprenderlo. Recapitulando, se considera que tiene el potencial para aprenderlo con suficiente tiempo y además, si lo consigue, sería mucho más eficiente que el resto de IA que juegan Tetris puesto que suelen usar algoritmos de árboles de decisión (muy exigentes computacionalmente). Abstract: This project is an attempt to train an Artificial Intelligence (AI) to play Tetris using the NeuroEvolution of Augmenting Topologies (NEAT) algorithm. This algorithm basically mixes traditional neural networks with genetic algorithms methods used to adjust the weight of each connection as well as generate new connection and neurons. This allows NEAT to train for problems that do not have a determined solution and also find the minimum topology of the neural network that is able to learn and solve the problem. This project would be a simple problem for the AI to solve. If it succeeds in doing so, it could go on to more complex ones that are similar to real life problems. To train this AI, a simple version of Tetris was programmed, modified so our agent could make the same moves as any player would. Training was done using different metrics as inputs (full Tetris board or column heights) and different ways to define the outputs (individual movements each frame or predetermined positions to which the movements are calculated) in the hope that at least one of the input/output combinations would show significant improvements over the others so that training could be focused on that combination alone. In spite of all the tries with these different ways to train the AI, it did not succeed in playing Tetris effectively. It just learnt to stack the pieces to the sides and the center, showing at least some improvement in its tactics to get higher scores. However, this does not mean NEAT cannot learn to play Tetris, it means it might need more generations to do so. Because a conventional neural network can learn to play Tetris, NEAT must be able to do it as well. In summary, it is thought that it has the potential to learn to play that given enough time and it would be much more efficient than the other kind of AIs that play Tetris. Those usually use algorithms based on decision trees, which inherently require much computation power to be applied in execution time.