pytwisty: Solucionador de cubos de Rubik – Proyecto Python

pytwisty es una implementación de Python 3 extremadamente rápida y eficiente de un solucionador para una serie de acertijos retorcidos, incluidos los acertijos del cubo de Rubik 1x2x2, 1x2x3 y 2x2x2.

Introducción

Los speedcubers modernos resuelven el cubo de Rubik utilizando secuencias de movimientos memorizadas, llamadas algoritmos, que implementan para resolver el cubo sección por sección. Cada algoritmo corresponde a una disposición diferente de pegatinas de colores en el cubo. Cuando un speedcuber detecta un arreglo que reconoce, ejecuta el algoritmo correspondiente, acercando el cubo un paso más a la solución.  

Sin embargo, los solucionadores computarizados convencionales simplemente buscan una solución óptima a partir de subconjuntos de todas las posiciones posibles de las piezas en el cubo utilizando técnicas de búsqueda complejas. El más rápido de estos es el algoritmo de Kociemba que identifica un subconjunto de 20 mil millones de posiciones. De hecho, este algoritmo también se usó para calcular la solución en el robot que tiene el récord mundial Guinness actual por la resolución más rápida de un robot. Para la experimentación, hemos comparado el solucionador 2x2x2 desarrollado por el mismo Herbert Kociemba en mi máquina con otras dos implementaciones del algoritmo de Korf y el método BFS bidireccional para resolver el cubo, los cuales también se encuentran entre los métodos de resolución más rápidos que existen. Al medir sus tiempos de resolución promedio, el solucionador de Kociemba demostró ser el más rápido entre ellos.

Por el contrario, desarrollaremos un solucionador que utilice el «enfoque humano» para resolver el rompecabezas. Específicamente, ejecuta una combinación de una versión ligeramente alterada del método capa por capa (LBL) y el método CFOP. Cuando ejecutamos un solucionador de 2x2x2 en el mismo conjunto de codificaciones aleatorias, el tiempo de resolución en promedio fue unas 350 veces más rápido que los tiempos de resolución del solucionador de Herbert Kociemba mencionado anteriormente. Usamos el módulo timeit para medir los tiempos de resolución del solucionador y el tiempo medio de resolución en segundos resultó ser del orden de 10 ^ -5 segundos, mientras que el tiempo que tomó el solucionador de Kociemba en segundos fue del orden de 10 ^ -2 sec en mi máquina en CPython.

Implementación

La razón principal detrás de la extremadamente alta velocidad y eficiencia del solucionador es que se basa en una técnica desarrollada que me gusta llamar la técnica de «Pensamiento mínimo». Esto, en términos más simples, es una técnica que minimiza el proceso de pensamiento detrás de resolver cualquier problema al reconocer el tipo de problema y usar un resultado predeterminado para saltar directamente a la solución. En cada paso de la resolución del rompecabezas, el solucionador reconoce la disposición y orientación actual de las piezas individuales del rompecabezas, y reorganiza y reorienta las piezas al estado final en el que habría resultado el algoritmo correspondiente, si se hubiera ejecutado manualmente. Así es como los speedcubers, en cada nivel de resolución del cubo de Rubik, miran la disposición del cubo y ejecutan el algoritmo correspondiente, todo sin pensar. 

Ejemplo de uso: 

Un ejemplo del uso del solucionador para resolver una mezcla aleatoria del Cubo de Rubik de 1x2x3. Aquí, «OGBYWR» es el esquema de color del cubo de Rubik del usuario y «WYBOOBGORBGRRGYW» es la combinación dada. Las instrucciones sobre cómo ingresar correctamente la alineación de color del cubo y la mezcla se pueden encontrar en PyPI o en el archivo Léame del repositorio de GitHub. El solucionador 1x2x3 genera una serie de pasos: [‘U’, ‘D’, ‘R’, ‘U’]. Cada paso tendría la forma U, D, R, L o M, cada uno de los cuales representa un giro de 180 grados de la capa superior, la capa inferior, la cara derecha, la cara izquierda y la capa intermedia, respectivamente. Cuando el usuario ejecute estos pasos en su cubo, obtendrá un cubo resuelto.

Aplicaciones

Este solucionador de cubos de Rubik es solo una de las varias aplicaciones que la técnica Minimal Thinking puede tener potencialmente en la Inteligencia Artificial moderna. Se puede usar para facilitar la parte de resolución de problemas de cada programa entrenándolo para usar resultados que ya han sido establecidos por inteligencia humana o artificial y saltando directamente a la solución sin tener que resolver todo el problema por sí solo. Aunque el «método humano» para resolver el cubo de Rubik tiene la desventaja de no proporcionar siempre la solución óptima, el aumento de 350 veces en la eficiencia del programa supera efectivamente cualquier desventaja potencial. Para los robots modernos que ejecutan cada movimiento en un cubo de Rubik físico en tan solo 10 milisegundos, ejecutar un puñado de movimientos adicionales es una tarea casi insignificante. En la mayoría de los problemas de la vida real, una solución óptima puede no ser siempre la mejor solución, especialmente cuando se genera a costa de un programa extremadamente lento y que consume demasiada memoria. Independientemente de cuánto haya avanzado la IA moderna hasta el punto en que los robots tienden a tener el potencial de «pensar» por sí mismos, incluso una pequeña interacción humana en un programa completamente autónomo puede marcar una gran diferencia en su eficiencia, como se evidencia en este ejemplo. de un solucionador de cubo de Rubik.

Enlace Github: https://github.com/prakharguptafaips/pytwisty

Enlace PyPI: https://pypi.org/project/pytwisty/