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 (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 quadrados de distância, ou seja, um quadrado que poderia ser alcançado por no máximo movimentos do rei de xadrez. (A distância do quadrado inicial é no máximo 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 . 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 para esse é sempre escolher esse movimento.Abstraindo mais, o "o conjunto do pay-off" (isto é, o conjunto de todos os jogos em que o anjo ganha) é um conjunto fechado (na topologia natural no conjunto de todos os jogos), e é sabido que tais jogos são determinísticos.