Problema del ángel

La región azul de puntos indica a dónde podría ir un ángel de poder 3.

El problema del ángel es un problema matemático de teoría de juegos propuesto por John Horton Conway que se pregunta la estrategia ganadora de un ángel y un diablo.

El ángel tiene poder k (un número natural mayor o igual que 1), el cual es fijado antes de que el juego comience. El tablero está inicialmente vacío.

En cada turno, el ángel salta a otra casilla vacía, la cual podría ser alcanzada por un máximo de k movimientos correspondientes a los del rey en ajedrez; es decir, la distancia a partir de la casilla inicial es como mucho k.

El diablo, en su turno, puede bloquear una casilla cualquiera en la que no esté el ángel. El ángel puede saltar sobre casillas bloqueadas, pero no puede terminar su turno en ellas. El diablo gana si el ángel no puede moverse. El ángel gana si puede sobrevivir indefinidamente.

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 un movimiento que el ángel puede hacer para evitar perder, y una estrategia ganadora para él sería escoger siempre este movimiento.

Historia

El problema fue publicado por primera vez en 1982, en el libro Winning Ways, por Berlekamp, Conway y Guy,5​ bajo el nombre de "the angel and the square-eater" (el ángel y el comecasillas). En dos dimensiones, los primeros resultados parciales incluyeron:

1. Si el ángel tiene poder 1, el diablo tiene una estrategia ganadora (Conway, 1982). (Según Conway, este resultado es en realidad debido a Berlekamp.)
2. Si el ángel nunca disminuye su coordenada Y, entonces el diablo tiene una estrategia ganadora (Conway, 1982).
3. Si el ángel siempre aumenta su distancia desde el origen, entonces el diablo tiene una estrategia ganadora (Conway, 1996).