Problema do anjo

O problema do Anjo é uma questão na Teoria dos Jogos proposta por John Conway. O jogo é comumente referido como o jogo dos Anjos e Diabos. É jogado por dois jogadores chamados o anjo e o diabo. Ele é jogado num tabuleiro de xadrez infinito (ou equivalentemente aos pontos de um reticulado 2D). O anjo tem poder k {\displaystyle k} (o número natural 1 ou maior). O tabuleiro de xadrez inicia-se vazio com o anjo na origem. A cada rodada, o anjo salta para um quadrado vazio diferente no máximo k {\displaystyle k} quadrados de distância, ou seja, um quadrado que poderia ser alcançado por no máximo k {\displaystyle k} movimentos do rei de xadrez. (A distância do quadrado inicial é no máximo k {\displaystyle k} na norma de infinidade). O demônio, na sua vez, pode adicionar um bloco a qualquer quadrado que não contenha um anjo. O anjo pode pular sob os quadrados obstruídos, mas não pode aterrissar neles. O demônio ganha se o anjo ficar incapaz de se mover. O anjo ganha se sobreviver indefinidamente. O problema do Anjo é: Pode um anjo com poder suficientemente grande ganhar? A resposta é desconhecida, e Conway ofereceu uma recompensa para a solução geral deste problema($100 para a estratégia de vencer do anjo com poder suficientemente grande para ganhar, e $1000 para a prova de que o demônio pode ganhar independentemente do poder do anjo). O progresso, entretanto, foi feito em dimensões elevadas, com algumas provas bonitas. Deve existir uma estratégia para que um dos jogadores ganhe. Se o diabo pode forçar uma vitória, então ele pode fazer isso num número finito de movimentos. Se o diabo não pode forçar uma vitória, então existe sempre uma ação que o anjo pode fazer para evitar perder e uma estratégia para ganhar...