fbpx
Wikipedia

Algoritmo de Dios

Enero 27, 2022

El algoritmo de Dios es un concepto originado 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 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.

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,[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 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.[5]​

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

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[6]​ o 43 movimientos de varias fichas[7]​ en el peor de los casos. Para su generalización el n- rompecabezas, el problema de encontrar una solución óptima es NP-hard.[8]​ 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 ( ).[9]​

Cubo de Rubik

Artículo principal: 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.[10]​ 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.[11]​ 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.[4]​

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

 

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).[12]​

Juegos sin resolver

Artículo principal: 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.[13]​ 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 10154 para el ajedrez[14]​ y 10180 (en un tablero de 19 × 19) para el go,[15]​ 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×1019 posiciones[16]​). 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 adelante (contando un movimiento de cada jugador como dos movimientos), reduciendo el espacio de búsqueda a solo 1017.[17]​ 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.[18]​ Los algoritmos de evaluación son propensos a cometer errores elementales[19]​ 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.[20]​ 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.[21]​ Sin embargo, las damas con sólo 5×1020 posiciones[22]​ e incluso menos, 3.9×1013, en la base de datos de Schaeffer,[23]​ 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  . 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   el problema es NP-hard.[24]​

Véase también

Referencias

  1. Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions, Hachette UK, 2014 ISBN 1472116224.
  2. 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).]"
  3. Jonathan Fildes (August 11, 2010). «Rubik's Cube quest for speedy solution comes to an end». BBC News. 
  4. ↑ Singmaster, p. 311, 1980
  5. Joyner, page 149
  6. A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45–63.
  7. "The Fifteen Puzzle can be solved in 43 moves". Domain of the Cube Forum
  8. Daniel Ratner, Manfred K. Warmuth (1986). "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. 168–172.
  9. Carlos Rueda, .
  10. Richard E. Korf, "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.
  11. "God's Number is 20". Cube20.org
  12. «Some 3-color cube results». Domain of the Cube Forum. Archivado desde el original el 4 de septiembre de 2013. Consultado el 29 de julio de 2013. 
  13. Rothenberg, p. 11
  14. Baum, p. 187
  15. Baum, p. 199
  16. Singmaster, 1981
  17. Baum, p. 188
  18. Baum, p. 197|Mohammadian, p. 11
  19. Baum, p.197
  20. Fraser & Hannah, p. 197
  21. Moore & Mertens, chapter 1.3, "Playing chess with God"
  22. Schaeffer et al., p. 1518
  23. Moore & Mertens, "Notes" to chapter 1
  24. Rueda

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

Enero 27, 2022
algoritmo, dios, algoritmo, dios, concepto, originado, discusiones, sobre, formas, resolver, rompecabezas, cubo, rubik, pero, también, puede, aplicar, otros, rompecabezas, combinatorios, juegos, matemáticos, refiere, cualquier, algoritmo, produzca, solución, m. El algoritmo de Dios es un concepto originado en discusiones sobre formas de resolver el rompecabezas del cubo de Rubik 1 pero que tambien se puede aplicar a otros rompecabezas combinatorios y juegos matematicos 2 Se refiere a cualquier algoritmo que produzca una solucion con la menor cantidad de movimientos posibles siendo la idea que solo un ser omnisciente conoceria un paso optimo de cualquier configuracion dada Indice 1 Alcance 1 1 Definicion 1 2 Solucion 2 Ejemplos 2 1 Rompecabezas mecanicos 2 1 1 n Puzzles 2 1 2 Torres de Hanoi 2 1 3 Cubo de Rubik 3 Juegos sin resolver 4 Vease tambien 5 Referencias 6 BibliografiaAlcance EditarDefinicion Editar La nocion se aplica a los rompecabezas que pueden asumir un numero finito de configuraciones con un arsenal relativamente pequeno y bien definido de movimientos que pueden ser aplicables a configuraciones y luego conducir a una nueva configuracion Resolver el rompecabezas significa llegar a una configuracion final designada una configuracion singular o una de una coleccion de configuraciones Para resolver el rompecabezas se aplica una secuencia de movimientos partiendo de alguna configuracion inicial arbitraria Solucion Editar Se puede considerar que un algoritmo resuelve tal rompecabezas si toma como entrada una configuracion inicial arbitraria y produce como salida una secuencia de movimientos que conducen a una configuracion final si el rompecabezas se puede resolver a partir de esa configuracion inicial de lo contrario indica la imposibilidad de una solucion Una solucion es optima si la secuencia de movimientos es lo mas corta posible Este recuento se conoce como el numero de Dios 3 o mas 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 optimas Algunos escritores como David Joyner consideran que para que un algoritmo se denomine correctamente algoritmo de Dios tambien deberia ser practico lo que significa que el algoritmo no requiere cantidades extraordinarias de memoria o tiempo Por ejemplo el uso de una tabla de busqueda gigante indexada por configuraciones iniciales permitiria encontrar soluciones muy rapidamente pero requeriria una cantidad extraordinaria de memoria 5 En lugar de pedir una solucion completa se puede pedir de manera equivalente un solo movimiento de una configuracion inicial pero no final donde el movimiento es el primero de alguna solucion optima Un algoritmo para la version de un solo movimiento del problema se puede convertir en un algoritmo para el problema original invocandolo repetidamente mientras se aplica cada movimiento informado a la configuracion actual hasta que se alcanza uno final Por el contrario cualquier algoritmo para el problema original puede convertirse en un algoritmo para la version de un solo movimiento truncando su salida a su primer movimiento Ejemplos EditarLos acertijos mas conocidos que encajan en esta descripcion son los acertijos mecanicos como el cubo de Rubik las Torres de Hanoi y el juego del 15 Tambien se cubre el juego para una persona del solitario Senku asi como muchos acertijos de logica como el problema de los misioneros y canibales Estos tienen en comun que se pueden modelar matematicamente como un grafo dirigido en el que las configuraciones son los vertices y los movimientos los arcos Rompecabezas mecanicos Editar n Puzzles Editar El juego del 15 se puede resolver en 80 movimientos de una sola ficha 6 o 43 movimientos de varias fichas 7 en el peor de los casos Para su generalizacion el n rompecabezas el problema de encontrar una solucion optima es NP hard 8 Por lo tanto se desconoce si existe un algoritmo de Dios practico para este problema pero parece poco probable Torres de Hanoi Editar Para las Torres de Hanoi se conoce el algoritmo de un Dios para cualquier numero de discos El numero de movimientos es exponencial en el numero de discos 2 n 1 displaystyle 2 n 1 9 Cubo de Rubik Editar Articulo principal Soluciones optimas para el cubo de Rubik Richard Korf publico en 1997 un algoritmo para determinar el numero minimo de movimientos para resolver el cubo de Rubik 10 Si bien se sabia desde 1995 que 20 era un limite inferior en el numero de movimientos para la solucion en el peor de los casos se demostro en 2010 a traves de extensos calculos por computadora que ninguna configuracion requiere mas de 20 movimientos 11 Por tanto 20 es un limite superior marcado en la longitud de las soluciones optimas El matematico David Singmaster habia conjeturado precipitadamente que este numero era 20 en 1980 4 Se han encontrado numeros para el cubo de tres colores cuyo numero total de configuraciones es 2 11 3 7 C 12 4 C 8 4 2 10 863 756 288 000 displaystyle 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 descubrio que el numero de Dios para el cubo de tres colores opuestos es 15 FTM 17 QTM o 14 STM segun la metrica STM la rotacion de cualquier capa intermedia tambien se considera un movimiento 12 Juegos sin resolver EditarArticulo principal 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 13 Ambos juegos tienen un numero de posiciones que aumenta rapidamente con cada movimiento El numero total de todas las posiciones posibles aproximadamente 10154 para el ajedrez 14 y 10180 en un tablero de 19 19 para el go 15 es demasiado grande para permitir una solucion de fuerza bruta con la tecnologia informatica actual compare el ahora resuelto con gran dificultad el cubo de Rubik en solo aproximadamente 4 3 1019 posiciones 16 En consecuencia no es posible una determinacion 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 adelante contando un movimiento de cada jugador como dos movimientos reduciendo el espacio de busqueda a solo 1017 17 Despues de esto evaluo la ventaja de cada posicion de acuerdo con las reglas derivadas del juego y la experiencia humanos Incluso esta estrategia no es posible con el go Ademas de tener muchisimas mas posiciones para evaluar nadie hasta ahora ha construido con exito un conjunto de reglas simples para evaluar la fuerza de una posicion de go como se ha hecho con el ajedrez 18 Los algoritmos de evaluacion son propensos a cometer errores elementales 19 por lo que incluso para una mirada limitada hacia el futuro con el objetivo limitado a encontrar la posicion interina mas 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 20 En 2007 Schaeffer et al demostro que esto era asi 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 utilizo para demostrar que todos los juegos de damas perfectamente jugados terminaran en empate 21 Sin embargo las damas con solo 5 1020 posiciones 22 e incluso menos 3 9 1013 en la base de datos de Schaeffer 23 es un problema mucho mas facil 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 Hanoi ya resuelto puede tener un numero arbitrario de piezas y el numero de posiciones aumenta exponencialmente como 3 n displaystyle 3 n Sin embargo el algoritmo de solucion es aplicable a problemas de cualquier tamano y dado que el tiempo de ejecucion del algoritmo es O 2 n displaystyle O 2 n el problema es NP hard 24 Vease tambien EditarMaquina oraculo Pyraminx Regla del fin del mundoReferencias Editar Paul Anthony Jones Jedburgh Justice and Kentish Fire The Origins of English in Ten Phrases and Expressions Hachette UK 2014 ISBN 1472116224 See e g Rubik s Cubic Compendium by Erno Rubik Tamas Varga Gerzson Keri Gyorgy Marx and Tamas Vekerdy 1987 Oxford University Press ISBN 0 19 853202 4 p 207 el Pyraminx es mucho mas simple que el Cubo Magico Nicholas Hammond ha demostrado que el algoritmo de Dios tiene como maximo 21 movimientos incluidos los cuatro movimientos de vertice triviales Mas recientemente tres personas han encontrado el algoritmo de Dios El numero maximo de movimientos es 15 incluidos los movimientos de cuatro vertices Jonathan Fildes August 11 2010 Rubik s Cube quest for speedy solution comes to an end BBC News a b Singmaster p 311 1980 Joyner page 149 A Brungger A Marzetta K Fukuda and J Nievergelt The parallel search bench ZRAM and its applications Annals of Operations Research 90 1999 pp 45 63 The Fifteen Puzzle can be solved in 43 moves Domain of the Cube Forum Daniel Ratner Manfred K Warmuth 1986 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 168 172 Carlos Rueda An optimal solution to the Towers of Hanoi Puzzle Richard E Korf 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 God s Number is 20 Cube20 org Some 3 color cube results Domain of the Cube Forum Archivado desde el original el 4 de septiembre de 2013 Consultado el 29 de julio de 2013 Rothenberg p 11 Baum p 187 Baum p 199 Singmaster 1981 Baum p 188 Baum p 197 Mohammadian p 11 Baum p 197 Fraser amp Hannah p 197 Moore amp Mertens chapter 1 3 Playing chess with God Schaeffer et al p 1518 Moore amp Mertens Notes to chapter 1 RuedaBibliografia EditarBaum 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 Bjornsson Akihiro Kishimoto Martin Muller 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 Obtenido de https es wikipedia org w index php title Algoritmo de Dios amp oldid 136782817, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos