El algoritmo de Dios

El algoritmo de Dios es una noción que se originó en discusiones sobre formas de resolver el rompecabezas del cubo de Rubik , ^[1] pero que también se puede aplicar a otros rompecabezas combinatorios y juegos matemáticos . ^[2] Se refiere a cualquier algoritmo que produce una solución con el menor número de movimientos posibles. La alusión a la deidad se basa en la noción de que un ser omnisciente sabría un paso óptimo a partir de cualquier configuración dada.

El concepto se aplica a los rompecabezas que pueden asumir un número finito de "configuraciones", con un arsenal relativamente pequeño y bien definido de "movimientos" que pueden aplicarse a las configuraciones y luego conducir a una nueva configuración. Resolver el rompecabezas significa alcanzar 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, comenzando desde una configuración inicial arbitraria.

Un algoritmo puede considerarse capaz de resolver un rompecabezas de este tipo 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. El valor más alto de este, entre todas las configuraciones iniciales, se conoce como el número de Dios ^[3] o, más formalmente, el valor minimax ^[4] . El algoritmo de Dios, entonces, para un rompecabezas dado, es un algoritmo que resuelve el rompecabezas y produce solo soluciones óptimas.

Algunos autores, como David Joyner, consideran que para que un algoritmo pueda ser considerado correctamente como "algoritmo de Dios", también debe ser práctico , es decir, que no requiera 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. ^[5]

En lugar de pedir una solución completa, se puede pedir un único movimiento a partir de una configuración inicial pero no final, donde el movimiento es el primero de alguna solución óptima. Un algoritmo para la versión de un único movimiento del problema se puede convertir en un algoritmo para el problema original invocándolo repetidamente mientras se aplican cada movimiento informado a la configuración actual, hasta que se llega a una final; a la inversa, cualquier algoritmo para el problema original se puede convertir en un algoritmo para la versión de un único movimiento truncando su salida a su primer movimiento.

Los rompecabezas conocidos que encajan en esta descripción son los rompecabezas mecánicos como el Cubo de Rubik , la Torre de Hanoi y el rompecabezas del 15. También se cubre el juego de solitario de clavijas para una persona , así como muchos rompecabezas de lógica , como el problema de los misioneros y los caníbales . Estos tienen en común que se pueden modelar matemáticamente como un gráfico dirigido , en el que las configuraciones son los vértices y los movimientos son los arcos.

El rompecabezas de los Quince puede resolverse en 80 movimientos de una sola pieza ^[6] o 43 movimientos de varias piezas ^[7] en el peor de los casos. Para su generalización, el rompecabezas n , el problema de encontrar una solución óptima es NP - difícil ^[8], por lo que no se sabe si existe un algoritmo de Dios práctico.

En el caso del rompecabezas de las Torres de Hanoi , se conoce un algoritmo de Dios para cualquier número dado de discos. El número de movimientos aumenta exponencialmente con el número de discos ( )$Estilo de visualización 2^{n}-1$ . ^[9]

En 1997, Richard Korf publicó un algoritmo para determinar el número mínimo de movimientos necesarios para resolver el cubo de Rubik. ^[10] Si bien desde 1995 se sabía que 20 era un límite inferior para el número de movimientos necesarios para encontrar la solución en el peor de los casos, Tom Rokicki demostró en 2010 que ninguna configuración requiere más de 20 movimientos. ^[11] Por lo tanto, 20 es un límite superior preciso para la longitud de las soluciones óptimas. El matemático David Singmaster había "conjeturado precipitadamente" que este número era 20 en 1980. ^[4]

Algunos juegos muy conocidos con un conjunto muy limitado de reglas y movimientos simples bien definidos, sin embargo, nunca han tenido su algoritmo divino para una estrategia ganadora determinada. Ejemplos de ello son los juegos de mesa ajedrez y Go . ^[12] 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 5 × 10 ^{44 [13]} para ajedrez y 10 ¹⁸⁰ (en un tablero de 19 × 19) para Go, [14] es demasiado grande para permitir una solución de fuerza bruta con la tecnología informática actual (compárese con el Cubo de Rubik, ahora resuelto, con gran dificultad, a sólo unos 1000 ^{000 ).}4,3 × 10 ¹⁹ posiciones ^[15] ). 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 la partida hasta el final. Deep Blue , por ejemplo, buscó solo 11 movimientos por adelantado (contando un movimiento de cada jugador como dos movimientos), reduciendo el espacio de búsqueda a solo 10 ¹⁷ . ^[16] Después de esto, evaluó cada posición para la ventaja de acuerdo con reglas derivadas del juego y la experiencia humana.

Incluso esta estrategia no es posible con Go. Además de tener muchas más posiciones para evaluar, hasta ahora nadie ha logrado construir con éxito un conjunto de reglas simples para evaluar la fuerza de una posición de Go como se ha hecho para el ajedrez, aunque las redes neuronales entrenadas mediante aprendizaje de refuerzo pueden proporcionar evaluaciones de una posición que exceden la capacidad humana. ^[17] Los algoritmos de evaluación son propensos a cometer errores elementales ^[18], por lo que incluso para una mirada limitada hacia el futuro con el objetivo limitado a encontrar la posición provisional más fuerte, no ha sido posible un algoritmo de Dios para Go.

Por otra parte, desde hace tiempo se ha sospechado que las damas (damas) se "juegan hasta el final" por sus practicantes expertos. ^[19] En 2007, Schaeffer et al. demostraron que esto es así al calcular una base de datos de todas las posiciones con diez piezas o menos, proporcionando un algoritmo de Dios para todos los juegos finales de damas que se utilizó para demostrar que todos los juegos de damas jugados perfectamente terminan en tablas. ^[20] Sin embargo, las damas con solo5 × 10 ²⁰ posiciones ^[21] y aún menos,3,9 × 10 ¹³ , en la base de datos, ^[22] es un problema mucho más fácil de resolver, del mismo orden que el cubo de Rubik.

La magnitud del conjunto de posiciones de un rompecabezas no determina por completo si es posible un algoritmo de Dios. El rompecabezas de la Torre de Hanoi ya resuelto puede tener una cantidad arbitraria de piezas, y la cantidad de posiciones aumenta exponencialmente como . Sin embargo, el algoritmo de solución es aplicable a problemas de cualquier tamaño, con un tiempo de ejecución que escala como . ^[23]${\estilo de visualización 3^{n}}$$Estilo de visualización 2^{n}}$

• Máquina de Oracle
• Movimiento divino (juego de Go)
• Pruebas del LIBRO
• Grupo del cubo de Rubik
• Juego resuelto

• Baum, Eric B., ¿Qué es el pensamiento?, MIT Press, 2004 ISBN 0262025485 . 
• Davis, Darryl N.; Chalabi, T.; Berbank-Green, B., "Vida artificial, agentes y Go", en Mohammadian, Masoud, Nuevas fronteras en inteligencia computacional y sus aplicaciones , págs. 125–139, IOS Press, 2000 ISBN 9051994761 . 
• Fraser, Rober (ed); Hannah, W. (ed), The Draught Players' Weekly Magazine , vol. 2, Glasgow: JH Berry, 1885.
• Joyner, David (2002). Aventuras en la teoría de grupos . Johns Hopkins University Press. ISBN 0-8018-6947-1.
• Moore, Cristopher; Mertens, Stephan, La naturaleza de la computación , Oxford University Press, 2011 ISBN 0191620807 . 
• Rothenberg, Gadi, Catálisis, el algoritmo de Dios y el demonio verde , Amsterdam University Press, 2009 ISBN 9056295896 . 
• Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi; Kishimoto, Akihiro; Müller, Martin; Lake, Robert; Lu, Paul; Sutphen, Steve (14 de septiembre de 2007). "El juego de damas está resuelto" (PDF) . Science . 317 (5844): 1518–1522. Bibcode :2007Sci...317.1518S. doi :10.1126/science.1144079. ISSN  0036-8075. PMID  17641166.
• Singmaster, David, Notas sobre el cubo mágico de Rubik , Penguin, 1981 ISBN 0-907395-00-7 . 
• Singmaster, David, "El valor educativo del 'Cubo Mágico' húngaro", Actas del Cuarto Congreso Internacional sobre Educación Matemática , celebrado en Berkeley, California, del 10 al 16 de agosto de 1980, págs. 307-312, Birkhauser Boston Inc, 1983 ISBN 978-0-8176-3082-9 .