Algoritmo de Dios

El algoritmo de Dios 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. Pero hay un rompecabezas llamado Pyraminx Duo donde hay una tabla donde se soluciona el rompecabezas con el algoritmo de Dios para cada una de sus 324 combinaciones totales y cualquier persona que entienda la tabla puede resolverlo con el algoritmo de Dios.​

Alcance

Definición

La noción 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 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.

Solución

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.​

En lugar de pedir una solución completa, se puede pedir de manera equivalente un solo movimiento 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 solo movimiento del problema se puede convertir en un algoritmo para el problema original invocándolo repetidamente mientras se aplica cada movimiento informado a la configuración actual, hasta que se alcanza uno final. Por el contrario, cualquier algoritmo para el problema original puede convertirse en un algoritmo para la versión de un solo movimiento truncando su salida a su primer movimiento.

Ejemplos

Cubo de Rubik.

Los acertijos más conocidos que encajan en esta descripción son los acertijos mecánicos como el cubo de Rubik, las Torres de Hanói y el juego del 15. También se cubre el juego para una persona del solitario Senku, así como muchos acertijos de lógica, como el problema de los misioneros y caníbales. Estos tienen en común que se pueden modelar matemáticamente como un grafo dirigido, en el que las configuraciones son los vértices y los movimientos los arcos.

Rompecabezas mecánicos

n-Puzzles

El juego del 15 se puede resolver en 80 movimientos de una sola ficha​ o 43 movimientos de varias fichas​ en el peor de los casos. Para su generalización el n- rompecabezas, el problema de encontrar una solución óptima es NP-hard.​ Por lo tanto, se desconoce si existe un algoritmo de Dios práctico para este problema, pero parece poco probable.

Torres de Hanói

Para las Torres de Hanói, se conoce el algoritmo de un Dios para cualquier número de discos. El número de movimientos es exponencial en el número de discos ($2^{n}-1$).​

Cubo de Rubik

Richard Korf publicó en 1997 un algoritmo para determinar el número mínimo de movimientos para resolver el cubo de Rubik.​ Si bien se sabía desde 1995 que 20 era un límite inferior en el número de movimientos para la solución en el peor de los casos, se demostró en 2010 a través de extensos cálculos por computadora que ninguna configuración requiere más de 20 movimientos.​ Por tanto, 20 es un límite superior marcado en la longitud de las soluciones óptimas. El matemático David Singmaster había "conjeturado precipitadamente" que este número era 20 en 1980.​

Se han encontrado números para el cubo de tres colores, cuyo número total de configuraciones es:

$2^{11}\cdot 3^{7}\cdot C_{12}^{4}\cdot (C_{8}^{4})^{2}=10\ 863\ 756\ 288\ 000$

En marzo-abril de 2012, se descubrió que el número de Dios para el cubo de tres colores opuestos es 15 FTM, 17 QTM o 14 STM (según la métrica STM, la rotación de cualquier capa intermedia también se considera un movimiento).​

Juegos sin resolver

Sin embargo, 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¹⁵⁴ para el ajedrez​ y 10¹⁸⁰ (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¹⁹ 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. Deep Blue, por ejemplo, buscaba solo 11 movimientos hacia delante (contando un movimiento de cada jugador como dos movimientos), reduciendo el espacio de búsqueda a solo 10¹⁷.​ Después de esto, evaluó la ventaja de cada posición de acuerdo con las reglas derivadas del juego y la experiencia humanos.

Incluso esta estrategia no es posible con el go. Además de tener muchísimas más posiciones para evaluar, nadie hasta ahora ha construido con éxito 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 son propensos a cometer errores elementales​ por lo que incluso para una mirada limitada hacia el futuro con el objetivo limitado a encontrar la posición interina más fuerte, un algoritmo de Dios no ha sido posible para el go.

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, Schaeffer et al. demostró que esto era así calculando una base de datos de todas las posiciones con diez o menos piezas. Por lo tanto, Schaeffer 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²⁰ posiciones​ e incluso menos, 3.9×10¹³, en la base de datos de Schaeffer,​ es un problema mucho más fácil de descifrar y es 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 Hanói ya resuelto puede tener un número arbitrario de piezas, y el número de posiciones aumenta exponencialmente como $3^{n}$. Sin embargo, el algoritmo de solución es aplicable a problemas de cualquier tamaño, y dado que el tiempo de ejecución del algoritmo es $O(2^{n})$ el problema es NP-hard.​

Véase también

• Máquina oráculo
• Pyraminx
• Regla del fin del mundo

Bibliografía

• Baum, Eric B., What is Thought?, MIT Press, 2004 ISBN 0262025485.
• Davis, Darryl N.; Chalabi, T.; Berbank-Green, B., "Artificial-life, agents and Go", in Mohammadian, Masoud, New Frontiers in Computational Intelligence and its Applications, pp. 125–139, IOS Press, 2000 ISBN 9051994761.
• Fraser, Rober (ed); Hannah, W. (ed), The Draught Players' Weekly Magazine, vol. 2, Glasgow: J H Berry, 1885.
• David Joyner (2002). Adventures in Group Theory. Johns Hopkins University Press. ISBN 0-8018-6947-1. (requiere registro). 
• Moore, Cristopher; Mertens, Stephan, The Nature of Computation, Oxford University Press, 2011 ISBN 0191620807.
• Rothenberg, Gadi, Catalysis, God's Algorithm, and the Green Demon, Amsterdam University Press, 2009 ISBN 9056295896.
• Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, "Checkers is solved", Science, vol. 317, no. 58444, pp. 1518–1522, 14 September 2007.
• Singmaster, David, Notes on Rubik's Magic Cube, Penguin, 1981 ISBN 0-907395-00-7.
• Singmaster, David, "The educational value of the Hungarian 'Magic Cube'", Proceedings of the Fourth International Congress on Mathematical Education, celebrada en Berkeley, California, 10–16 de agosto de 1980, pp. 307–312, Birkhauser Boston Inc, 1983 ISBN 978-0-8176-3082-9.

• Datos: Q951050