Ver el código de «Algoritmo de Dios»

El '''algoritmo de Dios''' es un concepto originado en discusiones sobre formas de resolver el rompecabezas del [[cubo de Rubik]],<ref>Paul Anthony Jones, ''Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions'', Hachette UK, 2014 {{ISBN|1472116224}}.</ref> pero que también se puede aplicar a otros [[Rompecabezas (juego)|rompecabezas]] [[Combinatoria|combinatorios]] y [[juegos matemáticos]].<ref>See e.g. ''Rubik's Cubic Compendium'' by Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx, and Tamás Vekerdy (1987, Oxford University Press, {{ISBN|0-19-853202-4}}), p. 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 de vértice triviales). [Más recientemente, tres personas han encontrado el algoritmo de Dios. El número máximo de movimientos es 15 (incluidos los movimientos de cuatro vértices).]"</ref> Se refiere a cualquier algoritmo que produzca una solución con la menor cantidad de movimientos posibles, siendo la idea que solo un ser [[Omnisciencia|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.<ref>{{Cita web|url=https://www.researchgate.net/publication/387827109_Solucionar_el_Pyraminx_Duo_con_el_algoritmo_de_Dios_les_ensenaremos_como_hacer_el_algoritmo_de_Dios_del_cubo_de_Rubik_y_otros_rompecabezas_en_3_dimensiones|título=Resolver el Pyraminx Duo con el algoritmo de Dios. Le enseñaremos como resolver el cubo de Rubik y muchos otros rompecabezas en 3 dimensiones con el algoritmo de Dios.|títulotrad=Solve the Pyraminx Duo with God's algorithm. We will teach you how to solve the Rubik's cube and many other 3-dimensional puzzles with God's algorithm.|autor=Nilson Rafael Bolívar Barrios|año=2022|sitioweb=ResearchGate}}</ref>

== Alcance ==
=== Definición ===
La noción se aplica a los [[Rompecabezas (juego)|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''',<ref>{{cite news |author=Jonathan Fildes  |publisher=[[BBC News]] |title=Rubik's Cube quest for speedy solution comes to an end |url=https://www.bbc.co.uk/news/technology-10929159 |date=2010-08-11}}</ref> o, más formalmente, el valor [[minimax]].<ref name=Sing311/> 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 [[Lookup table|tabla de búsqueda]] gigante indexada por configuraciones iniciales permitiría encontrar soluciones muy rápidamente, pero requeriría una cantidad extraordinaria de memoria.<ref>Joyner, page 149</ref>

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 ==
[[Archivo:2021-01-14 18 25 51 A scrambled Rubik's Cube in the Franklin Farm section of Oak Hill, Fairfax County, Virginia.jpg|miniaturadeimagen|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 [[Acertijo de los misioneros y los caníbales|problema de los misioneros y caníbales]]. Estos tienen en común que se pueden [[Modelo matemático|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<ref>A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, [http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf The parallel search bench ZRAM and its applications], ''Annals of Operations Research'' '''90''' (1999), pp. 45–63.</ref> o 43 movimientos de varias fichas<ref>[http://cubezzz.duckdns.org/drupal/?q=node/view/223 "The Fifteen Puzzle can be solved in 43 ''moves''"]. Domain of the Cube Forum</ref> en el peor de los casos. Para su generalización el ''n-'' rompecabezas, el problema de encontrar una solución óptima es [[NP-hard]].<ref>Daniel Ratner, Manfred K. Warmuth (1986). [http://www.aaai.org/Papers/AAAI/1986/AAAI86-027.pdf "Finding a shortest solution for the N × N extension of the 15-puzzle is intractable"]. in ''Proceedings AAAI-86''. National Conference on Artificial Intelligence, 1986. pp.&nbsp;168–172.</ref> 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 {{nobr|(<math>2^n-1</math>)}}.<ref>Carlos Rueda, [https://web.archive.org/web/20040605074124/http://yupana.autonoma.edu.co/publicaciones/yupana/003/hanoi/hanoi_eng.html "An optimal solution to the Towers of Hanoi Puzzle"].</ref>

==== Cubo de Rubik ====
{{main|Soluciones óptimas para el 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]].<ref>Richard E. Korf, "[https://www.aaai.org/Papers/AAAI/1997/AAAI97-109.pdf Finding optimal solutions to Rubik's Cube using pattern databases]", ''Proc. Natl. Conf. on Artificial Intelligence'' (AAAI-97), Providence, Rhode Island, Jul 1997, pp. 700–705.</ref> 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.<ref name="GN20">[http://www.cube20.org/ "God's Number is 20"]. Cube20.org</ref> Por tanto, 20 es un [[Límite superior y límite inferior|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.<ref name=Sing311>Singmaster, p. 311, 1980</ref>

Se han encontrado números para el cubo de tres colores, cuyo número total de configuraciones es: <center><math>2^{11}\cdot 3^7\cdot C_{12}^4\cdot (C_8^4)^2=10\ 863\ 756\ 288\ 000</math></center>

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).<ref name="norskog_3color">{{cite web|url=http://cubezzz.dyndns.org/drupal/?q=node/view/248|publisher=Domain of the Cube Forum|title=Some 3-color cube results|accessdate=2013-07-29|archiveurl=https://www.webcitation.org/6JNKYRdhI?url=http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F248|archivedate=2013-09-04}}</ref>

== Juegos sin resolver ==
{{AP|Juego resuelto}}
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]].<ref>Rothenberg, p. 11</ref>  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<sup>154</sup> para el ajedrez<ref>Baum, p. 187</ref> y 10<sup>180</sup> (en un tablero de 19 × 19) para el go,<ref>Baum, p. 199</ref> 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<sup>19</sup> posiciones<ref>Singmaster, 1981</ref>).  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 (computadora)|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<sup>17</sup>.<ref>Baum, p. 188</ref>  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.<ref>Baum, p. 197|Mohammadian, p. 11</ref>  Los algoritmos de evaluación son propensos a cometer errores elementales<ref>Baum, p.197</ref> 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.<ref>Fraser & Hannah, p. 197</ref>  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.<ref>Moore & Mertens, chapter 1.3, "Playing chess with God"</ref> Sin embargo, las damas con sólo 5×10<sup>20</sup> posiciones<ref>Schaeffer ''et al.'', p. 1518</ref> e incluso menos, 3.9×10<sup>13</sup>, en la base de datos de Schaeffer,<ref>Moore & Mertens, "Notes" to chapter 1</ref> 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 <math>3^n</math>. 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 <math>O(2^n)</math> el problema es [[NP-hard]].<ref>Rueda</ref>

==Véase también==
*[[Máquina oráculo]]
*[[Pyraminx]]
*[[Regla del fin del mundo]]

==Referencias==
{{Listaref|2}}

==Bibliografía==
{{refcomienza}}
* 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.&nbsp;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.
*{{cite book |author=David Joyner |year=2002 |title=Adventures in Group Theory |publisher=Johns Hopkins University Press |isbn=0-8018-6947-1 |url-access=registration |url=https://archive.org/details/adventuresingrou0000joyn }}
* 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, [http://www.sciencemag.org/content/317/5844/1518.short "Checkers is solved"], ''Science'', vol. 317, no. 58444, pp.&nbsp;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.&nbsp;307–312, Birkhauser Boston Inc, 1983 {{ISBN|978-0-8176-3082-9}}.
{{reftermina}}


{{Control de autoridades}}
[[Categoría:Algoritmos de búsqueda]]
[[Categoría:Acertijos lógicos]]
[[Categoría:Juegos matemáticos]]
[[Categoría:Cubo de Rubik]]