Problema del ángel

El problema del ángel es un problema perteneciente a la Teoría de Juegos, propuesto por John Horton Conway​ El juego se suele conocer por el nombre Ángeles y Demonios. El juego tiene dos jugadores, llamados el ángel y el diablo. Se juega sobre una tablero de ajedrez infinito (o lo que es lo mismo, los puntos de una cuadrícula bidimensional). 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, con el ángel en el origen. 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 no es mayor que k con la norma infinito). 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. El problema del ángel consiste en: ¿Puede un ángel con 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, 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. A un nivel más abstracto, el "conjunto de ganancias" (es decir, el conjunto de todas los juegos en los que el ángel gana) es un conjunto cerrado (en la topología natural de los conjuntos de todos los juegos), y se sabe que estos juegos son determinados. Conway ofreció una recompensa por una solución general a este problema (100 dólares para una estrategia ganadora con un ángel de poder suficientemente alto, y 1000 dólares para una demostración de que el diablo puede ganar cualquiera que sea el poder del ángel). Se progresó primero en dimensiones mayores que 2, con algunas bellas demostraciones. A finales de 2006, el problema se resolvió cuando aparecieron demostraciones independientes, probando que un ángel puede ganar. demostró que un 4-ángel puede ganar​ y Mathé​ y Kloster​ demostraron que un 2-ángel puede ganar.