El problema del ángel es una cuestión de la teoría combinatoria de juegos propuesta por John Horton Conway . El juego se conoce comúnmente como el juego de Ángeles y demonios . [1] El juego es jugado por dos jugadores llamados el ángel y el diablo. Se juega en un tablero de ajedrez infinito (o equivalentemente los puntos de una celosía 2D ). El ángel tiene un poder k (un número natural 1 o superior), especificado antes de que comience el juego. El tablero comienza vacío con el ángel en un cuadrado. En cada turno, el ángel salta a un cuadrado vacío diferente al que se puede llegar como máximo kmovimientos de un rey del ajedrez , es decir, la distancia desde la casilla inicial es como máximo k en la norma infinita . El diablo, a su vez, puede agregar un bloque en cualquier cuadrado que no contenga al ángel. El ángel puede saltar sobre casillas bloqueadas, pero no puede aterrizar sobre ellas. El diablo gana si el ángel no puede moverse. El ángel gana sobreviviendo indefinidamente.
El problema del ángel es: ¿puede un ángel con un poder suficientemente alto ganar?
Debe existir una estrategia ganadora para uno de los jugadores. Si el diablo puede forzar una victoria, entonces puede hacerlo en un número finito de movimientos. Si el diablo no puede forzar una victoria, siempre hay una acción que el ángel puede realizar para evitar perder y una estrategia ganadora es siempre elegir ese movimiento. De manera más abstracta, el "conjunto de pagos" (es decir, el conjunto de todas las jugadas en las que gana el ángel) es un conjunto cerrado (en la topología natural en el conjunto de todas las jugadas), y se sabe que tales juegos están determinados . Por supuesto, para cualquier juego infinito, si el jugador 2 no tiene una estrategia ganadora, el jugador 1 siempre puede elegir un movimiento que lo lleve a una posición en la que el jugador 2 no tenga una estrategia ganadora, pero en algunos juegos, simplemente jugar para siempre. no confiere una victoria al jugador 1, por lo que pueden existir juegos indeterminados.
Conway ofreció una recompensa por una solución general a este problema ($ 100 por una estrategia ganadora para un ángel de poder suficientemente alto y $ 1000 por una prueba de que el diablo puede ganar independientemente del poder del ángel). Primero se avanzó en dimensiones superiores. A finales de 2006, el problema original se resolvió cuando aparecieron pruebas independientes que demostraban que un ángel puede ganar. Bowditch demostró que un 4-ángel (es decir, un ángel con poder k = 4) puede ganar [2] y Máthé [3] y Kloster [4] dieron pruebas de que un 2-ángel puede ganar.
Estrategias básicas y por qué no funcionan
Se pueden derrotar muchas estrategias de escape intuitivas para el ángel. Por ejemplo, si el ángel trata de huir de los bloques cercanos, el diablo puede hacer una herradura gigante muy al norte, luego empujar al ángel hacia la trampa comiendo repetidamente el cuadrado justo al sur del ángel. Si el ángel trata de evitar trampas colocadas muy lejos, el diablo puede hacer una pequeña herradura hacia el norte y luego empujar al ángel hacia la trampa comiendo los cuadrados del extremo sur.
Parece que el Ángel debería poder ganar moviéndose hacia arriba lo más rápido que pueda, combinado con zigzags ocasionales hacia el este u oeste para evitar trampas obvias. Esta estrategia se puede derrotar al notar que las posibles posiciones futuras de este ángel se encuentran en un cono, y el diablo puede construir una pared a través del cono en la distancia de cierta manera, de modo que cuando el ángel finalmente llegue a la distancia, el diablo haya creó un muro impenetrable, y dado que el ángel insiste en moverse hacia el norte, el ángel no puede moverse en absoluto.
Historia
El problema se publicó por primera vez en el libro de 1982 Winning Ways de Berlekamp, Conway y Guy, [5] bajo el nombre de "el ángel y el devorador de cuadrados". En dos dimensiones, algunos de los primeros resultados parciales incluyeron:
- Si el ángel tiene el poder 1, el diablo tiene una estrategia ganadora (Conway, 1982). (Según Conway, este resultado en realidad se debe a Berlekamp ). Esto se puede leer en la sección 1.1 del artículo de Kutz. [6]
- Si el ángel nunca disminuye su coordenada y, entonces el diablo tiene una estrategia ganadora (Conway, 1982).
- Si el ángel siempre aumenta su distancia del origen, entonces el diablo tiene una estrategia ganadora (Conway, 1996).
En tres dimensiones, se demostró que: [ cita requerida ]
- Si el ángel siempre aumenta su coordenada y, y el diablo solo puede jugar en un plano, entonces el ángel tiene una estrategia ganadora. [7]
- Si el ángel siempre aumenta su coordenada y, y el diablo solo puede jugar en dos planos, entonces el ángel tiene una estrategia ganadora.
- El ángel tiene una estrategia ganadora si tiene un poder de 13 o más.
- Si tenemos un número infinito de demonios, cada uno jugando a distancias entonces el ángel aún puede ganar si tiene suficiente poder. (Al "jugar a distancia"queremos decir que el diablo no puede jugar dentro de esta distancia del origen). [ dudoso ]
Finalmente, en 2006 (poco después de la publicación del libro Mathematical Puzzles de Peter Winkler , que ayudó a publicitar el problema del ángel) surgieron cuatro pruebas independientes y casi simultáneas de que el ángel tiene una estrategia ganadora en dos dimensiones. De Brian Bowditch prueba trabaja para el 4-ángel, mientras que Oddvar Kloster prueba y de András Máthé prueba de trabajo para el 2-ángel. La demostración de Péter Gács funciona solo para una constante mucho mayor. Las pruebas de Bowditch y Máthé han sido publicadas en Combinatorics, Probability and Computing . La prueba de Kloster se ha publicado en Theoretical Computer Science .
Más preguntas sin resolver
En 3D, dado que el ángel siempre aumenta su coordenada y , y que el diablo está limitado a tres planos, se desconoce si el diablo tiene una estrategia ganadora.
Bocetos de prueba
Prueba de "guardián"
La prueba, que muestra que en una versión tridimensional del juego un ángel de alto poder tiene una estrategia ganadora, hace uso de "guardianes". Por cada cubo de cualquier tamaño, hay un guardián que vigila ese cubo. Los guardianes deciden en cada movimiento si el cubo que están vigilando es inseguro, seguro o casi seguro. Es necesario elegir las definiciones de "seguro" y "casi seguro" para garantizar que esto funcione. Esta decisión se basa puramente en la densidad de puntos bloqueados en ese cubo y el tamaño de ese cubo.
Si el ángel no recibe órdenes, simplemente se mueve hacia arriba. Si algunos cubos que está ocupando el ángel dejan de ser seguros, entonces el guardián del más grande de estos cubos recibe instrucciones para que el ángel salga por uno de los bordes de ese cubo. Si un guardián recibe instrucciones de escoltar al ángel fuera de su cubo hasta una cara en particular, el guardián lo hace trazando un camino de subcubos que están a salvo. Los guardianes de estos cubos reciben instrucciones de escoltar al ángel a través de sus respectivos subcubos. El camino del ángel en un subcubo dado no se determina hasta que el ángel llega a ese cubo. Incluso entonces, el camino solo se determina de manera aproximada. Esto asegura que el diablo no pueda simplemente elegir un lugar en el camino lo suficientemente lejos y bloquearlo.
Se puede demostrar que la estrategia funciona porque el tiempo que le toma al diablo convertir un cubo seguro en el camino del ángel en un cubo inseguro es más largo que el tiempo que le toma al ángel llegar a ese cubo.
Esta prueba fue publicada por Imre Leader y Béla Bollobás en 2006. [8] Martin Kutz publicó una prueba sustancialmente similar en 2005. [6] [9]
La prueba de 2 ángeles de Máthé
Máthé [3] presenta al diablo simpático, que nunca destruye una casilla que el ángel podría haber elegido ocupar en un turno anterior. Cuando el ángel juega contra el buen diablo, concede la derrota si el diablo logra confinarlo a una región delimitada finita del tablero (de lo contrario, el ángel podría saltar de un lado a otro entre dos casillas y nunca perder). La prueba de Máthé se divide en dos partes:
- muestra que si el ángel gana contra el buen diablo, entonces el ángel gana contra el verdadero diablo;
- da una estrategia ganadora explícita para el ángel contra el buen diablo.
En términos generales, en la segunda parte, el ángel gana contra el buen diablo pretendiendo que todo el semiplano izquierdo está destruido (además de los cuadrados realmente destruidos por el buen diablo) y tratando los cuadrados destruidos como las paredes de un laberinto. , que luego bordea mediante una técnica de "mano en la pared". Es decir, el ángel mantiene su mano izquierda en la pared del laberinto y corre junto a la pared. Entonces se demuestra que un buen diablo no puede atrapar a un ángel que adopta esta estrategia.
La prueba de la primera parte es por contradicción y, por lo tanto, la prueba de Máthé no arroja inmediatamente una estrategia ganadora explícita contra el diablo real. Sin embargo, Máthé comenta que su prueba podría, en principio, adaptarse para dar una estrategia tan explícita.
Prueba de 4 ángeles de Bowditch
Brian Bowditch define [2] una variante (juego 2) del juego original con los siguientes cambios de reglas:
- El ángel puede regresar a cualquier casilla en la que ya haya estado, incluso si el diablo posteriormente intentó bloquearla.
- Un k-diablo debe visitar un cuadrado k veces antes de que se bloquee.
- El ángel se mueve hacia arriba, hacia abajo, hacia la izquierda o hacia la derecha en un cuadrado (un movimiento de duque).
- Para ganar, el ángel debe trazar un camino tortuoso (definido a continuación).
Un camino tortuoso es un camino dónde es un arco semi-infinito (un camino que no se auto-interseca con un punto inicial pero sin punto final) y son bucles disjuntos por pares con la siguiente propiedad:
- dónde es la longitud del i-ésimo bucle.
(Estar bien definido debe comenzar y terminar en el punto final de y debe terminar en el punto de partida de .)
Bowditch considera una variante (juego 1) del juego con los cambios 2 y 3 con un diablo 5. Luego muestra que una estrategia ganadora en este juego producirá una estrategia ganadora en nuestro juego original para un 4-ángel. Luego continúa mostrando que un ángel que juega un 5-demonio (juego 2) puede lograr una victoria usando un algoritmo bastante simple.
Bowditch afirma que un ángel de cuatro puede ganar la versión original del juego imaginando un ángel fantasma jugando a un demonio de cinco en el juego 2.
El ángel sigue el camino que tomaría el fantasma pero evitando los bucles. Por lo tanto, como el camino Es un arco semi-infinito en el que el ángel no regresa a ninguna casilla en la que haya estado anteriormente y, por lo tanto, el camino es un camino ganador incluso en el juego original.
Ver también
- El problema del chófer homicida , otro juego matemático que enfrenta a un adversario poderoso y maniobrable contra un enemigo altamente ingenioso pero menos poderoso.
Referencias
- ↑ John H. Conway, The angel problem , en: Richard Nowakowski (editor) Games of No Chance , volumen 29 de MSRI Publications , páginas 3-12, 1996.
- ^ a b Brian H. Bowditch , "El juego del ángel en el avión", Combin. Probab. Computación. 16 (3): 345-362, 2007.
- ^ a b András Máthé, "El ángel del poder 2 gana", Combin. Probab. Computación. 16 (3): 363-374, 2007
- ^ O. Kloster, Una solución al problema de los ángeles. Ciencias de la Computación Teórica , vol. 389 (2007), núm. 1-2, págs. 152-161
- ^ Berlekamp, Elwyn R .; Conway, John H .; Guy, Richard K. (1982), "Capítulo 19: El rey y el consumidor", Formas ganadoras para sus juegos matemáticos, Volumen 2: Juegos en particular , Academic Press, págs. 607–634.
- ^ a b Martin Kutz, El problema del ángel, juegos posicionales y raíces de dígrafos, Tesis doctoral FU Berlín, 2004
- ^ B. Bollobás e I. Líder, El ángel y el diablo en tres dimensiones. Revista de teoría combinatoria, Serie A. vol. 113 (2006), núm. 1, págs. 176-184
- ^ B. Bollobás e I. Líder, El ángel y el diablo en tres dimensiones. Revista de teoría combinatoria, Serie A. vol. 113 (2006), núm. 1, págs. 176-184
- ^ Martin Kutz, Ángel de Conway en tres dimensiones, Theoret. Comp. Sci. 349 (3): 443–451, 2005.
enlaces externos
- El problema del ángel de John H Conway
- Sitio del problema del ángel de Kloster