El problema del ángel es una cuestión de la teoría de juegos combinatorios propuesta por John Horton Conway . El juego se conoce comúnmente como el juego de los ángeles y los 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 red 2D ). El ángel tiene una potencia k (un número natural 1 o superior), especificado antes de que comience el juego. El tablero comienza vacío con el ángel en una casilla. En cada turno, el ángel salta a una casilla vacía diferente a la que se puede llegar con como máximo k movimientos de un rey de ajedrez , es decir, la distancia desde la casilla de inicio es como máximo k en la norma del infinito . El diablo, en su turno, puede agregar un bloque en cualquier casilla individual que no contenga al ángel. El ángel puede saltar sobre casillas bloqueadas, pero no puede aterrizar en ellas. El diablo gana si el ángel no puede moverse. El ángel gana sobreviviendo indefinidamente.
El problema de los ángeles es: ¿puede un ángel con suficiente poder 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, entonces siempre hay una acción que el ángel puede tomar para evitar perder y una estrategia ganadora para él es siempre elegir ese movimiento. Más abstractamente, 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 lleve a una posición en la que el jugador 2 no tenga una estrategia ganadora, pero en algunos juegos, simplemente jugar eternamente 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). El progreso se hizo primero en dimensiones superiores. A fines de 2006, el problema original se resolvió cuando aparecieron pruebas independientes, que mostraban que un ángel puede ganar. Bowditch demostró que un ángel de 4 (es decir, un ángel con poder k = 4) puede ganar [2] y Máthé [3] y Kloster [4] dieron pruebas de que un ángel de 2 puede ganar.
El problema se publicó por primera vez en el libro Winning Ways de 1982 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:
En tres dimensiones, se demostró que:
Finalmente, en 2006 (poco después de la publicación del libro de Peter Winkler Mathematical Puzzles , 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. La prueba de Brian Bowditch funciona para el ángel de 4, mientras que la prueba de Oddvar Kloster y la prueba de András Máthé funcionan para el ángel de 2. Además, Peter Gacs tiene una supuesta prueba Archivado el 4 de marzo de 2016 en Wayback Machine que requiere un ángel mucho más fuerte; los detalles son bastante complejos y no han sido revisados por una revista para verificar su precisión. Las pruebas de Bowditch y Máthé se han publicado en Combinatorics, Probability and Computing . La prueba de Kloster se ha publicado en Theoretical Computer Science .
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.
Oddvar Kloster descubrió un algoritmo constructivo para resolver el problema con un ángel 2. Este algoritmo es bastante simple y también óptimo, ya que, como se señaló anteriormente, el diablo tiene una estrategia ganadora contra un ángel 1.
Comenzamos dibujando una línea vertical inmediatamente a la izquierda de la posición inicial del ángel, hacia abajo y hacia arriba . Esta línea representa el camino que tomará el ángel, que se actualizará después de cada uno de los movimientos del diablo, y divide las casillas del tablero en un "conjunto izquierdo" y un "conjunto derecho". Una vez que una casilla se convierte en parte del conjunto izquierdo, permanecerá así durante el resto del juego, y el ángel no realizará ningún movimiento futuro a ninguna de estas casillas. Cada vez que el diablo bloquea una nueva casilla, buscamos todas las posibles modificaciones del camino de modo que movamos una o más casillas del conjunto derecho que el diablo ha bloqueado al conjunto izquierdo. Solo haremos esto si el camino aumenta en longitud en no más del doble del número de casillas bloqueadas movidas al conjunto izquierdo. De tales caminos calificados, elegimos uno que mueva la mayor cantidad de casillas bloqueadas al conjunto izquierdo. El ángel da dos pasos por este camino, manteniendo el camino a su izquierda cuando avanza (por lo que si el diablo no estuviera bloqueando casillas, el ángel viajaría hacia el norte indefinidamente). Tenga en cuenta que al girar en el sentido de las agujas del reloj alrededor de una esquina, el ángel no se moverá ni un paso, porque los dos segmentos que tocan la esquina tienen la misma casilla a su derecha.
Máthé [3] introduce al diablo amable, que nunca destruye una casilla que el ángel podría haber elegido ocupar en un turno anterior. Cuando el ángel juega contra el diablo amable, admite la derrota si el diablo logra confinarlo en una región finita y delimitada del tablero (de lo contrario, el ángel podría simplemente saltar de un lado a otro entre dos casillas y nunca perder). La prueba de Máthé se divide en dos partes:
En términos generales, en la segunda parte, el ángel gana contra el diablo amable al pretender que todo el semiplano izquierdo está destruido (además de todos los cuadrados que el diablo amable realmente destruyó), y al tratar los cuadrados destruidos como las paredes de un laberinto, que luego rodea mediante una técnica de "mano en la pared". Es decir, el ángel mantiene su mano izquierda en la pared del laberinto y corre a lo largo de la pared. Entonces se demuestra que un diablo amable no puede atrapar a un ángel que adopta esta estrategia.
La prueba de la primera parte se realiza por contradicción, y por lo tanto la prueba de Máthé no arroja inmediatamente una estrategia explícita para ganar contra el diablo real. Sin embargo, Máthé señala que su prueba podría, en principio, adaptarse para dar una estrategia explícita de ese tipo.
Brian Bowditch define [2] una variante (juego 2) del juego original con los siguientes cambios de reglas:
Un camino tortuoso es un camino donde es un arco semiinfinito (un camino que no se autointersecta con un punto de inicio pero ningún punto final) y son bucles disjuntos por pares con la siguiente propiedad:
(Para estar bien definido debe comenzar y terminar en el punto final de y debe terminar en el punto inicial de .)
Bowditch analiza una variante (juego 1) del juego con los cambios 2 y 3 con un diablo de 5. Luego demuestra que una estrategia ganadora en este juego dará como resultado una estrategia ganadora en nuestro juego original para un ángel de 4. Luego continúa demostrando que un ángel que juega con un diablo de 5 (juego 2) puede lograr una victoria utilizando un algoritmo bastante simple.
Bowditch afirma que un ángel 4 puede ganar la versión original del juego imaginando a un ángel fantasma interpretando a un diablo 5 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 semiinfinito, el ángel no regresa a ninguna casilla en la que haya estado anteriormente, por lo que el camino es un camino ganador incluso en el juego original.
La prueba, que muestra que en una versión tridimensional del juego un ángel poderoso tiene una estrategia ganadora, hace uso de "guardianes". Para 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. Las definiciones de "seguro" y "casi seguro" deben elegirse 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 no se le dan órdenes al ángel, simplemente se mueve hacia arriba. Si algunos cubos que el ángel está ocupando dejan de ser seguros, entonces se le ordena al guardián del cubo más grande de estos que haga que el ángel salga por uno de los bordes de ese cubo. Si se le ordena a un guardián que escolte al ángel fuera de su cubo hacia una cara en particular, el guardián lo hace trazando un camino de subcubos que sean todos seguros. Luego se le ordena a los guardianes en estos cubos que escolten 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 garantiza 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 tarda el diablo en convertir un cubo seguro en el camino del ángel en un cubo inseguro es mayor que el tiempo que tarda el ángel en llegar a ese cubo.
Esta prueba fue publicada por Imre Leader y Béla Bollobás en 2006. [8] Una prueba sustancialmente similar fue publicada por Martin Kutz en 2005. [6] [9]
