Algoritmo de Dios para niños
El algoritmo de Dios es una idea que surgió al hablar sobre cómo resolver el cubo de Rubik de la manera más rápida. También se puede aplicar a otros rompecabezas y juegos matemáticos que tienen muchas combinaciones posibles.
Este concepto se refiere a cualquier método o conjunto de pasos que encuentra la solución a un rompecabezas usando la menor cantidad de movimientos posibles. La idea es que solo una mente con conocimiento perfecto podría saber el mejor paso en cualquier situación. Sin embargo, para un rompecabezas llamado Pyraminx Duo, existe una tabla que muestra cómo resolverlo con el algoritmo de Dios para cada una de sus 324 combinaciones. Cualquiera que entienda la tabla puede usar este algoritmo.
Contenido
¿Qué es el algoritmo de Dios?
Entendiendo los rompecabezas
Esta idea se usa para rompecabezas que tienen un número limitado de "formas" o "estados" en los que pueden estar. También tienen un conjunto pequeño y claro de "movimientos" que se pueden aplicar para cambiar de un estado a otro. Resolver un rompecabezas significa llegar a un "estado final" específico, que puede ser uno solo o parte de un grupo de estados. Para resolverlo, se aplica una serie de movimientos desde el estado inicial.
La solución perfecta
Un algoritmo se considera que resuelve un rompecabezas si, al darle un estado inicial, te da una secuencia de movimientos que te llevan al estado final. Si el rompecabezas no se puede resolver desde ese estado, el algoritmo lo indicaría. Una solución es "óptima" si la secuencia de movimientos es la más corta posible. A esta cantidad mínima de movimientos se le llama el número de Dios. El algoritmo de Dios, entonces, es un método que resuelve el rompecabezas y siempre encuentra las soluciones más cortas.
Algunas personas creen que para que un algoritmo sea realmente un "algoritmo de Dios", también debe ser práctico. Esto significa que no debe necesitar una cantidad enorme de memoria o tiempo para funcionar. Por ejemplo, usar una tabla gigante con todas las soluciones sería muy rápido, pero requeriría muchísima memoria.
En lugar de buscar la solución completa, a veces solo se busca el primer movimiento óptimo desde un estado que no es el final. Un algoritmo que encuentra este primer movimiento se puede usar repetidamente para resolver todo el rompecabezas.
Ejemplos de rompecabezas
Los rompecabezas más conocidos que encajan en esta descripción son los mecánicos, como el cubo de Rubik, las Torres de Hanói y el juego del 15. También se incluyen juegos para una persona como el solitario Senku y muchos rompecabezas de lógica, como el problema de los misioneros y caníbales. Todos estos se pueden representar como un grafo dirigido, donde los estados son puntos y los movimientos son las conexiones entre ellos.
Rompecabezas mecánicos populares
El juego del 15
El juego del 15 se puede resolver en un máximo de 80 movimientos si se mueve una ficha a la vez, o 43 movimientos si se pueden mover varias fichas. Para versiones más grandes de este rompecabezas, encontrar la solución más corta es un problema muy difícil de resolver con computadoras. Por eso, no se sabe si existe un algoritmo de Dios práctico para este tipo de rompecabezas, y parece poco probable.
Las Torres de Hanói
Para las Torres de Hanói, se conoce el algoritmo de Dios para cualquier número de discos. El número de movimientos necesarios crece muy rápido a medida que se añaden más discos.
El Cubo de Rubik
En 1997, Richard Korf publicó un algoritmo para encontrar el número mínimo de movimientos para resolver el cubo de Rubik. Desde 1995 se sabía que se necesitaban al menos 20 movimientos en el peor de los casos. En 2010, con cálculos de computadora muy extensos, se demostró que ninguna configuración del cubo requiere más de 20 movimientos. Así, 20 es el número máximo de movimientos para una solución óptima. El matemático David Singmaster ya había pensado en 1980 que este número era 20.
Para el cubo de tres colores, que tiene muchísimas combinaciones posibles (más de 10 billones), se han encontrado números específicos para el algoritmo de Dios. En 2012, se descubrió que el número de Dios para el cubo de tres colores opuestos es 15 movimientos (si se cuenta cada giro de cara), 17 movimientos (si se cuentan giros de 90 grados) o 14 movimientos (si se cuenta la rotación de cualquier capa intermedia como un movimiento).
Juegos sin solución óptima
Algunos juegos muy conocidos con reglas simples y movimientos claros aún no tienen un algoritmo de Dios que determine la mejor estrategia para ganar. Ejemplos de esto son el ajedrez y el go. Ambos juegos tienen un número de posiciones que aumenta muy rápidamente con cada movimiento. El número total de posiciones posibles es gigantesco (aproximadamente 10154 para el ajedrez y 10180 para el go en un tablero de 19x19). Esto es demasiado grande para que las computadoras actuales puedan encontrar todas las soluciones posibles. En comparación, el cubo de Rubik, que ya se resolvió con dificultad, tiene "solo" unas 4.3x1019 posiciones.
Por lo tanto, no es posible encontrar el algoritmo de Dios para estos juegos probando todas las posibilidades. Aunque se han creado computadoras de ajedrez que pueden vencer a los mejores jugadores humanos, no calculan el juego hasta el final. Por ejemplo, Deep Blue solo analizaba 11 movimientos hacia adelante, lo que reducía el espacio de búsqueda a "solo" 1017 posiciones. Después de eso, evaluaba qué tan buena era cada posición basándose en reglas y experiencia humanas.
Esta estrategia es aún más difícil con el go. Además de tener muchas más posiciones que evaluar, nadie ha logrado crear un conjunto de reglas simples para evaluar la fuerza de una posición de go, como se ha hecho con el ajedrez. Los algoritmos de evaluación para el go suelen cometer errores básicos, por lo que incluso para mirar un poco hacia el futuro y encontrar la posición intermedia más fuerte, un algoritmo de Dios no ha sido posible para el go.
Por otro lado, las damas, que se parecen un poco al ajedrez, se sospechaba desde hace tiempo que sus expertos las "jugaban" de forma perfecta. En 2007, Schaeffer y su equipo demostraron que esto era cierto al calcular una base de datos de todas las posiciones con diez o menos piezas. Así, Schaeffer tiene un algoritmo de Dios para todas las fases finales de las damas y lo usó para demostrar que todos los juegos de damas jugados perfectamente terminarán en empate. Sin embargo, las damas, con "solo" 5x1020 posiciones y aún menos (3.9x1013) en la base de datos de Schaeffer, es un problema mucho más fácil de resolver y es del mismo tamaño que el cubo de Rubik.
El tamaño del conjunto de posiciones de un rompecabezas no es lo único que determina si es posible un algoritmo de Dios. El rompecabezas de la Torre de Hanói, que ya está resuelto, puede tener un número ilimitado de piezas, y el número de posiciones crece muy rápido. Sin embargo, el algoritmo de solución se puede aplicar a problemas de cualquier tamaño.
Véase también
En inglés: God's algorithm Facts for Kids
- Máquina oráculo
- Pyraminx
- Regla del fin del mundo
