Problema sobre un ángel y un demonio

El problema del ángel y el demonio es un problema de teoría de juegos propuesto por Conway en 1982. [1] .

Redacción

Reglas del juego

Dos jugadores están jugando , llamados un ángel y un demonio. El juego tiene lugar en un tablero de ajedrez sin fin . El ángel tiene "fuerza" k (es un número natural 1 o más), que se establece antes de que comience el juego. Al comienzo del juego, el ángel se para en una de las celdas. Con cada movimiento, el ángel se mueve a otra celda libre, a la que se puede llegar en un máximo de k movimientos del rey. El diablo, a su vez, puede bloquear una celda que no tenga un ángel. El Ángel puede saltar sobre espacios bloqueados, pero no puede aterrizar en ellos. El diablo gana si el ángel no puede moverse. El ángel gana si vive indefinidamente.

Pregunta

¿Puede un ángel ganar si tiene suficiente poder?

Más precisamente, es necesario encontrar una estrategia ganadora para uno de los jugadores. Si el diablo puede ganar, debe hacerlo en un número finito de movimientos. Si el diablo no puede ganar, entonces siempre hay una acción que el ángel puede tomar para evitar perder, y la estrategia ganadora es elegir ese movimiento. Es decir, el conjunto de movimientos que conducen a la victoria del ángel está cerrado en la topología natural en el conjunto de todos los movimientos, y se sabe que tales juegos son deterministas .

Historia

El problema fue publicado por primera vez en 1982 en Winning Ways por Berlekamp , Conway y Guy [2] bajo el título "The Angel and the Square Eater".

Conway anunció una recompensa por la solución general del problema ($100 por una estrategia ganadora para un ángel con fuerza suficiente y $1,000 por probar que el diablo puede ganar sin importar la fuerza del ángel).

Para el caso bidimensional, aquí hay algunos resultados preliminares:

Si la fuerza del ángel es 1, entonces el diablo tiene una estrategia ganadora. (Según Conway, este resultado se debe a Alvin Berlekamp ).
Si el ángel nunca reduce las coordenadas, entonces el diablo tiene una estrategia ganadora (Conway, 1982).
Si el ángel siempre aumenta la distancia desde la celda central, entonces el diablo tiene una estrategia ganadora (Conway, 1996).

Para un tablero tridimensional, se ha probado que:

Si el ángel siempre aumenta la distancia desde el cuadrado central y el diablo puede jugar en el mismo plano, entonces el ángel tiene una estrategia ganadora.
Si el ángel siempre aumenta las coordenadas y el diablo solo puede jugar en dos planos, entonces el ángel tiene una estrategia ganadora.
Un ángel tiene una estrategia ganadora si su poder es 13 o superior.
Si hay un número infinito de demonios y todos juegan a distancia , entonces el ángel aún puede ganar si tiene un poder lo suficientemente grande. (Por "jugar a distancia " nos referimos a la restricción de que el diablo no puede jugar a una distancia menor del cuadro de inicio). $d_{1}<d_{2}<d_{3}<\cdots$ $d$

Finalmente, en 2006 (poco después de la publicación de Mathematical Puzzles de Peter Winkler , que popularizó este problema), se presentaron cuatro pruebas independientes y casi idénticas de que un ángel tiene una estrategia ganadora en un tablero plano. La demostración de Bowditch [3] funciona con el funcionan con el ángel de poder 2.[4]André Matede demostraciónKloster y laOddvarmientras que,ángel Las demostraciones de Bowditch y Mate se publicaron en Combinatorics, Probability and Computing (editores Bolobas y Leader ). La prueba de Kloster se publica en Theoretical Computer Science .

Bocetos de evidencia

Prueba "Guardia"

Una prueba que muestra que una versión 3D del juego con un ángel de suficiente fuerza tiene una estrategia ganadora utiliza "guardias". Para cualquier cubo de cualquier tamaño, hay un guardia que vigila el cubo. Antes de cada movimiento, el guardia decide si el cubo que está observando es peligroso, seguro o casi seguro. Las definiciones de "seguro" y "casi seguro" deben aclararse: esta decisión se basa únicamente en la densidad de los puntos de bloqueo en el cubo y el tamaño del cubo.

Si el movimiento del ángel no está predeterminado, simplemente nos movemos hacia arriba. Si algunos cubos que deja el ángel son seguros, entonces se le indica al guardia del cubo más grande que se asegure de que el ángel salga del cubo por una de las caras del cubo. Si se le indica al guardia que acompañe al ángel hacia afuera hasta cierto borde, el guardia lo hace construyendo un camino a través de los subcubos seguros. Los guardias de estos cubos tienen instrucciones de escoltar al ángel a través de sus subcubos. El camino de un ángel en un subcubo no se define hasta que el ángel entra en ese cubo. Aun así, el camino está más o menos definido. La estrategia asegura que el diablo no pueda elegir un punto en el camino del ángel lo suficientemente lejos como para bloquearlo.

Se puede comprobar que la estrategia funciona porque el tiempo que tarda el diablo en convertir un cubo seguro en el camino del ángel en uno peligroso es más largo que el tiempo que tarda el ángel en llegar al cubo.

Esta prueba fue publicada por Lider [ y Bolobas en 2006 [5] . Una prueba similar fue publicada por Martin Kutz en 2005 [6] [7] .

Prueba de Mate para un ángel con fuerza 2

Mate [4] introdujo un demonio discreto , nunca destruyendo una celda que un ángel había ocupado previamente. Si un ángel está jugando contra un demonio con tacto, se supone que el demonio gana si restringe el movimiento del ángel a un área limitada (de lo contrario, ¡el ángel simplemente salta de un lado a otro en dos cuadrados y nunca pierde!).

Mate dio una estrategia ganadora explícita para un ángel contra un demonio con tacto y mostró que si un ángel gana contra un demonio con tacto, entonces un ángel gana contra un demonio real.

En la primera parte, el ángel se gana al demonio discreto al suponer que todo el semiplano izquierdo está destruido (además de todas las células destruidas por el demonio), y trata las células destruidas como las paredes de un laberinto, que es anulada de acuerdo con la regla de la "mano izquierda". Es decir, el ángel sostiene su mano izquierda en la pared del laberinto y camina a lo largo de la pared. Se puede probar que un diablo con tacto no puede capturar a un ángel que adopta tal estrategia.

La segunda parte se prueba por contradicción y, por lo tanto, la prueba de Mate no da una estrategia ganadora inmediata contra el verdadero diablo. Sin embargo, Mate señala que esta prueba puede, en principio, adaptarse para obtener tal estrategia.

Prueba de Bowditch para un ángel con fuerza 4

Bodwich define [3] una variante (juego 2) del juego de apertura con los siguientes cambios de reglas:

El ángel puede volver a cualquier casilla que ya haya visitado, incluso si el diablo intentara bloquearla.
El k-diablo debe visitar la celda k veces antes de que sea bloqueada.
El ángel mueve una celda hacia arriba/abajo/izquierda/derecha.
Para ganar, el ángel debe seguir el camino circular que se describe a continuación.

Una ruta circular es una ruta donde hay un arco semi-infinito (una ruta autodesarticulada con un punto de inicio pero sin un punto final) y son bucles separados por pares con las siguientes propiedades: $\pi =\cup _{i=1}^{\infty}(\sigma _{i}\cup \gamma _{i})$ ${\displaystyle \sigma =\cup _{i=1}^{\infty}\sigma _{i))$ ${\ estilo de visualización {\ gamma _ {i}}}$

$\forall i:|\gamma _{i}|\leq i$ donde es la longitud del bucle i-ésimo. ${\ estilo de visualización | \ gamma _ {i} |}$

(Para ser completamente específico , debe comenzar y terminar en el punto final y debe terminar en el punto inicial ). ${\ estilo de visualización \ gamma _ {i}}$ $\sigma_i$ $\sigma_i$ ${\ estilo de visualización \ sigma _ {i + 1}}$

Bodwich sugiere una variante (juego 1) del juego con los cambios 2 y 3 y 5-diablo. Mostró que la estrategia ganadora en este juego daría la estrategia ganadora del juego original para un ángel de fuerza 4. También mostró que un ángel que juega contra un demonio 5 (juego 2) podría lograr una victoria usando un algoritmo bastante simple.

Bodwich afirma que un ángel de fuerza 4 puede ganar la versión original del juego imaginando un ángel fantasma jugando contra un demonio de 5 en el juego 2.

El ángel sigue el camino posible del ángel fantasma pero evita los bucles. Dado que el camino es un arco semi-infinito, el ángel no regresará a ninguna casilla que ya haya visitado y, por lo tanto, el camino será el camino ganador del juego original. $\sigma$

Variaciones y generalizaciones

En el espacio 3D, dado que el ángel siempre aumenta la coordenada y y el diablo está limitado a tres planos, se desconoce si el diablo tiene una estrategia ganadora.

Véase también

Problema del conductor asesino , otro juego de matemáticas en el que un jugador lento pero ágil intenta dejar atrás a un enemigo más rápido pero menos ágil.
Teoría de búsqueda garantizada

Notas

↑ John H. Conway. Juegos sin azar / Richard Nowakowski. - Publicaciones MSRI, 1996. - V. 29. - S. 3-12. El problema del ángel Archivado el 29 de septiembre de 2020 en Wayback Machine .
↑ Elwyn R. Berlekamp , John H. Conway y Richard K. Guy , Winning Ways for your matemático juega, volumen 2: Juegos en particular , Academic Press, 1982.
↑ 1 2 Brian H. Bowditch , El juego del ángel en el avión , Combin. probable computar 16(3):345-362, 2007.
↑ 1 2 András Máthé, El ángel del poder 2 gana , Combin. probable computar 16(3):363-374, 2007
↑ 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, El ángel de Conway en tres dimensiones, Theoret. compensación ciencia 349(3):443-451, 2005.
↑ Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, tesis doctoral archivada el 11 de diciembre de 2007 en Wayback Machine FU Berlín, 2004