El algoritmo de Dios

 

Seguramente Ernő Rubik no imaginó “la que se iba a montar” con su juguete. Si ahora miramos hacia atrás, podemos comprobar que el cubo de Rubik, el rompecabezas que este profesor húngaro inventó en 1974 para ayudar a sus estudiantes a comprender ciertos problemas en tres dimensiones. Pero el Cubo de Rubik es el juguete más vendido de la historia. 

¿Cuál es el máximo número de movimientos que necesitaríamos para resolver un cubo de Rubik, sea cual sea la posición inicial?  Esto ha mantenido entretenidos a investigadores prácticamente desde la aparición de este rompecabezas. Existen, como ya hemos dicho, muchos tutoriales y manuales para resolver el cubo de Rubik comenzando desde cualquier posición, pero muchos de ellos nos “obligan” a realizar más movimientos de los que quizás podríamos haber hecho partiendo de la posición inicial que tengamos entre manos. 

La cosa es que Dios, si existiera, seguro que dispondría de un algoritmo de resolución (es decir, una secuencia de pasos para resolver el cubo) totalmente eficiente, un algoritmo que resolviera el cubo de Rubik en el menor número de pasos posibles. A este algoritmo se le llamó Algoritmo de Dios, y al número máximo de movimientos necesarios para resolver cualquier cubo de Rubik se le denomina el Número de Dios.

Este número de Dios, que en 1981 estaba acotado entre 18 y 52, era el Santo Grial del cubo de Rubik, el número deseado por todos los amantes del estudio de la resolución de este rompecabezas. En 1990 ya lo teníamos acotado entre 18 y 42; en 1995 entre 20 y 29; en 2008 Tomas Rokicki lo reduce a entre 20 y 22; y, por fin, en 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson y John Dethridge demostraron que el Número de Dios es exactamente 20. 

Esto significa que todo cubo de Rubik, sea cual sea la posición inicial de sus piezas, se puede resolver en, como mucho, 20 movimientos. Habrá posiciones iniciales que necesiten menos de 20 movimientos, pero no hay ninguna para la que estemos obligados a realizar más de 20. Y, además, está demostrado que este número no se puede mejorar, ya que se sabe que hay posiciones concretas que necesitan de exactamente 20 movimientos. Por tanto, esta búsqueda está completamente cerrada: el número de Dios es 20. Si queréis más información sobre esto, vale la pena acudir a Cube20.

El Algoritmo de Dios (God's algorithm, AI) es un concepto originado en discusiones sobre formas de resolver el rompecabezas del Cubo de Rubik, pero que también se puede aplicar a otros rompecabezas combinatorios y juegos matemáticos. Se refiere a cualquier algoritmo que produzca una solución con la menor cantidad de movimientos posibles, siendo la idea que solo un ser omnisciente conocería un paso óptimo de cualquier configuración dada.

La noción se aplica a los rompecabezas que pueden disponer de un número finito de "configuraciones", con un arsenal relativamente pequeño y bien definido de "movimientos" que pueden ser aplicables a configuraciones y luego conducir a una nueva configuración. Resolver el rompecabezas significa llegar a una "configuración final" designada, una configuración singular o una de una colección de configuraciones. Para resolver el rompecabezas se aplica una secuencia de movimientos, partiendo de alguna configuración inicial arbitraria.

Se puede considerar que un algoritmo resuelve tal rompecabezas si toma como entrada una configuración inicial arbitraria y produce como salida una secuencia de movimientos que conducen a una configuración final (si el rompecabezas se puede resolver a partir de esa configuración inicial, de lo contrario, indica la imposibilidad de una solución). Una solución es óptima si la secuencia de movimientos es lo más corta posible. Este recuento se conoce como el Número de Dios, o, más formalmente, el valor minimax.​ El algoritmo de Dios, entonces, para un rompecabezas dado, es un algoritmo que resuelve el rompecabezas y produce solo soluciones óptimas.

Algunos escritores, como David Joyner, consideran que para que un algoritmo se denomine correctamente "Algoritmo de Dios", también debería ser práctico, lo que significa que el algoritmo no requiere cantidades extraordinarias de memoria o tiempo. Por ejemplo, el uso de una tabla de búsqueda gigante indexada por configuraciones iniciales permitiría encontrar soluciones muy rápidamente, pero requeriría una cantidad extraordinaria de memoria.

Algunos juegos bien conocidos con un conjunto muy limitado de reglas y movimientos simples y bien definidos nunca han tenido el Algoritmo de Dios para una estrategia ganadora determinada. Algunos ejemplos son los juegos de mesa ajedrez y go. Ambos juegos tienen un número de posiciones que aumenta rápidamente con cada movimiento. El número total de todas las posiciones posibles, aproximadamente 10^154 para el ajedrez y 10^180 (en un tablero de 19 × 19) para el go, es demasiado grande para permitir una solución de fuerza bruta con la tecnología informática actual (compare el ahora resuelto, con gran dificultad, el cubo de Rubik en solo aproximadamente 4.3×10^19 posiciones, es decir más de 43 trillones de posiciones). 

En consecuencia, no es posible una determinación de fuerza bruta del algoritmo de Dios para estos juegos. Si bien se han construido computadoras de ajedrez que son capaces de vencer incluso a los mejores jugadores humanos, no calculan el juego hasta el final. El IBM Deep Blue, por ejemplo, buscaba solo 11 movimientos hacia adelante (contando un movimiento de cada jugador como dos movimientos), reduciendo el espacio de búsqueda a solo 10^17. Después de esto, evaluó la ventaja de cada posición de acuerdo con las reglas derivadas del juego y la experiencia humanos.

Por otro lado, las damas, con similitudes superficiales con el ajedrez, han sido sospechadas durante mucho tiempo de ser "jugadas" por sus expertos practicantes. En 2007, se demostró que esto era así calculando una base de datos de todas las posiciones con diez o menos piezas. Por lo tanto, tiene un Algoritmo de Dios para todos los juegos finales de damas y lo utilizó para demostrar que todos los juegos de damas perfectamente jugados terminarán en empate. Sin embargo, las damas con sólo 5×10^20 posiciones​ e incluso menos, 3.9×10^13, es un problema mucho más fácil de descifrar y es del mismo orden que el cubo de Rubik.

Web optimizada para resolver el Cubo de Rubik.