Una máquina ha descubierto el cubo de Rubik por sí sola

Otro bastión de la habilidad y la inteligencia humanas ha caído ante el ataque de las máquinas. Un nuevo tipo de máquina de aprendizaje profundo ha aprendido a resolver un cubo de Rubik sin ayuda humana.

El hito es significativo porque el nuevo enfoque aborda un problema importante en informática: cómo resolver problemas complejos cuando la ayuda es mínima.

Primero algunos antecedentes. El Cubo de Rubik es un rompecabezas tridimensional desarrollado en 1974 por el inventor húngaro Erno Rubik, cuyo objetivo es alinear todos los cuadrados del mismo color en la misma cara del cubo. Se convirtió en un juguete de mayor venta internacional y vendió más de 350 millones de unidades.

El rompecabezas también ha atraído un interés considerable por parte de informáticos y matemáticos. Una pregunta que les ha intrigado es el menor número de movimientos necesarios para resolverlo desde cualquier posición . La respuesta, comprobada en 2014, resulta ser 26.

Otro desafío común es diseñar algoritmos que puedan resolver el cubo desde cualquier posición. El propio Rubik, un mes después de inventar el juguete, ideó un algoritmo que podía hacer esto.

Pero todos los intentos de automatizar el proceso se han basado en algoritmos hechos a mano por humanos.

Más recientemente, los científicos informáticos han tratado de encontrar formas para que las máquinas resuelvan el problema por sí mismas. Una idea es utilizar el mismo tipo de enfoque que ha tenido tanto éxito con juegos como el ajedrez y el Go.

En estos escenarios, una máquina de aprendizaje profundo recibe las reglas del juego y luego juega contra sí misma. Fundamentalmente, es recompensado en cada paso de acuerdo con su desempeño. Este proceso de recompensa es muy importante porque ayuda a la máquina a distinguir el buen juego del mal juego. En otras palabras, ayuda a la máquina a aprender.

Pero esto no funciona en muchas situaciones del mundo real, porque las recompensas suelen ser raras o difíciles de determinar.

Por ejemplo, los giros aleatorios de un cubo de Rubik no pueden recompensarse fácilmente, ya que es difícil juzgar si la nueva configuración está más cerca de una solución. Y una secuencia de turnos aleatorios puede continuar durante mucho tiempo sin llegar a una solución, por lo que la recompensa del estado final solo se puede ofrecer en raras ocasiones.

En el ajedrez, por el contrario, hay un espacio de búsqueda relativamente grande, pero cada movimiento puede evaluarse y recompensarse en consecuencia. Ese no es el caso del cubo de Rubik.

Introduzca Stephen McAleer y colegas de la Universidad de California, Irvine. Estos muchachos han sido pioneros en un nuevo tipo de técnica de aprendizaje profundo, llamada iteración autodidáctica, que puede aprender a resolver un cubo de Rubik sin ayuda humana. El truco que han dominado McAleer y compañía es encontrar una manera para que la máquina cree su propio sistema de recompensas.

Así es como funciona. Dado un cubo sin resolver, la máquina debe decidir si un movimiento específico es una mejora en la configuración existente. Para hacer esto, debe ser capaz de evaluar el movimiento.

La iteración autodidáctica hace esto comenzando con el cubo terminado y trabajando hacia atrás para encontrar una configuración que sea similar al movimiento propuesto. Este proceso no es perfecto, pero el aprendizaje profundo ayuda al sistema a determinar qué movimientos son generalmente mejores que otros.

Una vez entrenada, la red utiliza un árbol de búsqueda estándar para buscar movimientos sugeridos para cada configuración.

El resultado es un algoritmo que funciona notablemente bien. Nuestro algoritmo es capaz de resolver el 100 % de los cubos revueltos aleatoriamente mientras logra una longitud de resolución media de 30 movimientos, menor o igual que los solucionadores que emplean el conocimiento del dominio humano, dicen McAleer y compañía.

Eso es interesante porque tiene implicaciones para una variedad de otras tareas con las que ha tenido problemas el aprendizaje profundo, incluidos rompecabezas como Sokoban, juegos como Montezuma's Revenge y problemas como la factorización de números primos.

De hecho, McAleer y compañía tienen otros objetivos en la mira: estamos trabajando para ampliar este método para encontrar soluciones aproximadas a otros problemas de optimización combinatoria, como la predicción de la estructura terciaria de proteínas.

No está claro si estos problemas serán tan susceptibles a este enfoque. Por lo general, no se benefician de una prueba de que se pueden resolver en un pequeño número de movimientos, como ocurre con el problema del cubo de Rubik. Eso, sin duda, funcionó a favor del equipo aquí.

McAleer y compañía argumentan que su enfoque es una forma de razonamiento sobre los problemas. Señalan que una definición de razonamiento es: manipular algebraicamente el conocimiento previamente adquirido para responder una nueva pregunta.

Dicen que esto es exactamente lo que hace su algoritmo, llamado DeepCube. Por el contrario, las máquinas convencionales de aprendizaje profundo simplemente reconocen ciertos patrones. DeepCube es capaz de aprender por sí mismo cómo razonar para resolver un entorno complejo con un solo estado de recompensa utilizando aprendizaje de refuerzo puro, dicen.

Quizás. La verdadera prueba, por supuesto, será cómo este enfoque hace frente a problemas más complejos, como el plegamiento de proteínas. Estaremos atentos para ver cómo funciona.

Ref: arxiv.org/abs/1805.07470 : Resolver el cubo de Rubik sin conocimiento humano

esconder