Problema do anjo
De Wikipedia, a enciclopédia encyclopedia
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?
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Julho de 2018) |
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 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.