Reinforcement Learning: Theoretical Foundations and Application to the Rubik’s Cube

Abstract

The techniques employed and developed in the area of reinforcement learning have been evolving since their origins at the end of the 20th century. Thanks to the various advances in this field, it has been possible to solve increasingly complicated problems. The influence of other areas of machine learning and artificial intelligence has enabled applications of reinforcement learning that initially posed great challenges due to their computational requirements. One such problem is the one we will discuss in this work, which is characterized by a large state space and a single final state. First, a theoretical introduction to the area of reinforcement learning will be given, focusing on those aspects most relevant to the solution of our problem. Then, a theoretical description of the DeepCubeA algorithm will be presented, that was designed to solve the Rubik’s 3x3x3 Cube, which has a large state space and only one final state. Finally, we will design and implement a version of the DeepCubeA algorithm, adding some relevant aspects of its previous version (DeepCube), and we will study its behavior with the Rubik’s 2x2x2 and 3x3x3 Cubes, and the Hanoi Towers.

Las técnicas utilizadas y desarrolladas en el área del aprendizaje por refuerzo han ido evolucionando desde sus inicios, a finales del siglo XX. Gracias a los distintos avances en este sector, se han podido resolver problemas cada vez más complicados. La influencia de otras áreas del aprendizaje automático y de la inteligencia artificial han permitido aplicaciones del aprendizaje por refuerzo que inicialmente suponían grandes desafíos por sus requerimientos computacionales. Uno de esos problemas es el que trataremos en este trabajo, que se caracteriza por un gran espacio de estados y un único estado final. En un primer lugar, se dará una introducción teórica al área del aprendizaje por refuerzo, centrándonos en aquellos aspectos más relevantes en la resolución de nuestro problema. Después, se expondrá una descripción teórica del algoritmo DeepCubeA que fue diseñado especialmente para resolver el cubo de Rubik 3x3x3, caracterizado precisamente por un gran espacio de estados y un único estado final. Por último, diseñaremos e implementaremos una versión del algoritmo DeepCubeA, añadiendo algunos aspectos relevantes de su version anterior (DeepCube), y estudiaremos su comportamiento con los cubos de Rubik 2x2x2 y 3x3x3, y las Torres de Hanói.