Hispanopedia Wiki
Articulo de referencia

El algoritmo de Dios

El algoritmo divino del cubo de Rubik es una noción que surge de las discusiones sobre cómo resolver el rompecabezas del cubo de Rubik , [ 1 ] pero que también puede aplicarse a...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo divino del cubo de Rubik es una noción que surge de las discusiones sobre cómo resolver el rompecabezas del cubo de Rubik , [ 1 ] pero que también puede aplicarse 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 (es decir, el solucionador no debería necesitar más que este número). La alusión a la divinidad se basa en la idea de que un ser omnisciente conocería el paso óptimo para cualquier configuración dada.

Alcance

Definición

Este concepto se aplica a rompecabezas que pueden tener un número finito de configuraciones, con un conjunto relativamente pequeño y bien definido de movimientos que pueden aplicarse a las configuraciones y, posteriormente, conducir a una nueva. Resolver el rompecabezas significa alcanzar una configuración final específica, una configuración singular o una de un conjunto de configuraciones. Para resolver el rompecabezas, se aplica una secuencia de movimientos, partiendo de una configuración inicial arbitraria.

Solución

Se puede considerar que un algoritmo resuelve un 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. El valor más alto de este valor, entre todas las configuraciones iniciales, se conoce como el número de Dios [ 3 ] o, más formalmente, el valor minimax [ 4 ] . Por lo tanto, el algoritmo de Dios, para un rompecabezas dado , es un algoritmo que lo resuelve y produce únicamente soluciones óptimas.

Algunos autores, como David Joyner, consideran que para que un algoritmo pueda denominarse propiamente "el algoritmo de Dios", también debe ser práctico , es decir, que no requiera cantidades extraordinarias de memoria ni de tiempo. Por ejemplo, usar 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 solicitar una solución completa, se puede pedir, de forma equivalente, un único movimiento a partir de una configuración inicial, pero no final, donde dicho movimiento sea 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 y aplicando cada movimiento reportado a la configuración actual, hasta alcanzar la configuración final; a la inversa, cualquier algoritmo para el problema original se puede convertir en un algoritmo para la versión de un solo movimiento truncando su resultado al primer movimiento.

Ejemplos

Algunos rompecabezas conocidos que se ajustan a esta descripción son los mecánicos, como el Cubo de Rubik , la Torre de Hanoi y el rompecabezas de las 15 piezas . También se incluye el solitario de clavijas para una persona , así como muchos rompecabezas de lógica , como el problema de los misioneros y los caníbales . Todos ellos tienen en común que pueden modelarse matemáticamente como un grafo dirigido , donde las configuraciones son los vértices y los movimientos son los arcos.

Rompecabezas mecánicos

n - Rompecabezas

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

Torres de Hanói

Para el rompecabezas de las Torres de Hanoi , se conoce un algoritmo divino para cualquier número dado de discos. El número de movimientos aumenta exponencialmente con el número de discos (2norte−1{\displaystyle 2^{n}-1}) . [ 9 ]

Cubo de Rubik

Un cubo de Rubik desordenado

En 1997 , Richard E. Korf publicó un algoritmo para determinar el número mínimo de movimientos necesarios para resolver el cubo de Rubik. [ 10 ] Si bien se sabía desde 1995 que 20 era un límite inferior para el número de movimientos necesarios para 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 ]

Juegos sin resolver

Algunos juegos muy conocidos con un conjunto muy limitado de reglas y movimientos simples y 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 el ajedrez y 10 180 (en un tablero de 19×19) para el 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, con solo unos4,3 × 10 19 posiciones [ 15 ] ). En consecuencia, no es posible determinar por fuerza bruta el algoritmo de Dios para estos juegos. Si bien se han construido computadoras de ajedrez capaces de vencer incluso a los mejores jugadores humanos, no calculan el juego 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 17 . [ 16 ] Después de esto, evaluó cada posición para obtener ventaja según 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 que evaluar, nadie ha logrado construir 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 por refuerzo pueden proporcionar evaluaciones de una posición que superan la capacidad humana. [ 17 ] Los algoritmos de evaluación son propensos a cometer errores elementales [ 18 ] por lo que incluso para una anticipación limitada con el objetivo de encontrar la posición intermedia más fuerte, no ha sido posible un algoritmo divino para el Go.

Por otro lado, se sospecha desde hace tiempo que las damas (damas) son "jugadas hasta el final" por sus expertos. [ 19 ] En 2007, Schaeffer et al. demostraron esto calculando una base de datos de todas las posiciones con diez o menos piezas, proporcionando un algoritmo divino para todos los finales de partidas de damas que se utilizó para demostrar que todas las partidas de damas jugadas perfectamente terminan en tablas. [ 20 ] Sin embargo, las damas con solo5 × 10 20 posiciones [ 21 ] e incluso menos,3,9 × 10 13 , 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 completamente si es posible un algoritmo divino. El rompecabezas de la Torre de Hanoi, ya resuelto, puede tener un número arbitrario de piezas, y el número de posiciones aumenta exponencialmente a medida que3norte{\displaystyle 3^{n}}Sin embargo, el algoritmo de solución es aplicable a problemas de cualquier tamaño, con un tiempo de ejecución que escala como2norte{\displaystyle 2^{n}}. [ 23 ]

Véase también

Notas

  1. ↑ Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions , Hachette UK, 2014 ISBN 1472116224.
  2. ^ Véase, por ejemplo, el Compendio cúbico de Rubik de Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx y Tamás Vekerdy ​​(1987, Oxford University Press, ISBN 0-19-853202-4), pág. 207: "...el Pyraminx es mucho más simple que el Cubo Mágico... Nicholas Hammond ha demostrado que el Algoritmo de Dios tiene como máximo 21 movimientos (incluidos los cuatro movimientos triviales de vértice). [Más recientemente, tres personas han encontrado el Algoritmo de Dios. El número máximo de movimientos es 15 (incluidos los cuatro movimientos de vértice).]"
  3. ↑ Jonathan Fildes (11 de agosto de 2010). "La búsqueda de una solución rápida para el cubo de Rubik llega a su fin" . BBC News .
  4. 1 2 Singmaster, pág. 311, 1980
  5. ↑ Joyner, página 149
  6. ↑ A. Brüngger, A. Marzetta, K. Fukuda y J. Nievergelt, El banco de búsqueda paralelo ZRAM y sus aplicaciones , Annals of Operations Research 90 (1999), pp. 45–63.
  7. ↑ Norskog, Bruce; Davidson, Morley (8 de diciembre de 2010). "El rompecabezas de los quince se puede resolver en 43 movimientos " . Domain of the Cube Forum . Consultado el 15 de marzo de 2022 .
  8. ↑ Daniel Ratner, Manfred K. Warmuth (1986). "Encontrar la solución más corta para la extensión N × N del rompecabezas de 15 piezas es intratable" . En Actas de la AAAI-86 . Conferencia Nacional sobre Inteligencia Artificial, 1986. págs. 168–172.
  9. ↑ Rueda, Carlos (agosto de 2000). "Una solución óptima al rompecabezas de las Torres de Hanoi" . Universidad Autónoma de Manizales . Manizales , Colombia . Archivado desde el original el 5 de junio de 2004 . Consultado el 15 de marzo de 2022 .
  10. ↑ Richard E. Korf , " Encontrar soluciones óptimas para el cubo de Rubik utilizando bases de datos de patrones ", Actas de la Conferencia Nacional sobre Inteligencia Artificial (AAAI-97), Providence, Rhode Island, julio de 1997, págs. 700–705.
  11. ↑ Rokicki, Tomas; Kociemba, Herbert; Davidson, Morley; Dethridge, John (2010). "El número de Dios es 20" . Cube20.org . Consultado el 15 de marzo de 2022 .
  12. ↑ Rothenberg, pág. 11
  13. ↑ John Tromp. "Clasificación de posiciones de ajedrez" . GitHub .
  14. ↑ Baum, pág. 199
  15. ↑ Singmaster, 1981
  16. ↑ Baum, pág. 188
  17. ↑
  18. ↑ Baum, pág. 197
  19. ↑ Fraser y Hannah, pág. 197
  20. ↑ Moore y Mertens, capítulo 1.3, "Jugando al ajedrez con Dios"
  21. ^ Schaeffer y col. , pag. 1518
  22. ↑ Moore y Mertens, "Notas" al capítulo 1
  23. ↑ Rueda

Referencias

  • 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). "Checkers Is Solved" (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 de 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.