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$ (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$ quadrados de distância, ou seja, um quadrado que poderia ser alcançado por no máximo $k$ movimentos do rei de xadrez. (A distância do quadrado inicial é no máximo $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 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.

Progresso feito para resolver este problema

Em duas dimensões, sabe-se que:

• Se o anjo tem poder 1, o diabo tem uma estratégia de vitória (Conway, 1982).
• Se o anjo nunca diminui sua coordenada de y, então o diabo tem uma estratégia de vitória (Conway, 1982).
• Se o anjo sempre aumenta sua distância da origem, então o diabo tem uma estratégia de vitória (Conway, 1996).

Em três dimensões, sabe-se que:

• Se o anjo aumentar sempre sua coordenada de y, e o diabo puder somente jogar em um plano, então o anjo tem uma estratégia de vitória.
• Se o anjo aumentar sempre sua coordenada de y, e o diabo puder somente jogar em dois planos, então o anjo tem uma estratégia de vitória.
• O anjo tem uma estratégia de vitória se ele tem poder 13 ou mais
• Se nós temos um número infinito de diabos, cada um jogando a distâncias $d_{1}<d_{2}<d_{3}<\dots$ então o anjo ainda pode ganhar se ele é de poder grande o suficiente.

("jogando na distância $d$", nós queremos dizer que não está permitido ao diabo jogar dentro desta distância da origem)

Questões adicionais não resolvidas

Em 3D:

• Dado que o anjo aumenta sempre sua coordenada de y, e que o diabo está limitado a 3 planos, é desconhecido se o diabo tem uma estratégia de vitória.

Esboce a prova que em 3D um anjo de poder elevado tem uma estratégia de vitória

A prova desta emprega guardiões. Para cada cubo de todo o tamanho há um guardião que cuida do cubo. Os guardiões decidem em cada movimento se o cubo que estão cuidando está inseguro, seguro ou quase seguro. Esta decisão é baseada puramente na densidade de pontos bloqueados nesse cubo e no tamanho desse cubo.

Se ao anjo não for dada nenhuma ordem, então ele apenas se move para cima. Se alguns cubos que o anjo está vivendo dentro cessarem de ser seguros então o guardião do maior destes cubos está instruído a arranjar para que o anjo saia por uma das bordas desse cubo.

Se um guardião for instruído a escoltar o anjo para fora de seu cubo, para uma face particular este guardião faz isso traçando um caminho de subcubos que estão todos seguros. Os guardiões nestes cubos são instruídos então a escoltar o anjo através de seus respectivos subcubos.

A prova funciona porque o tempo que o diabo demora para converter um cubo seguro no caminho do anjo para um cubo inseguro é maior do que o tempo que leva para o anjo obter esse cubo.

As definições de seguro e quase seguro precisa ser escolhida para assegurar esse trabalho.

Nota: O caminho do anjo em um subcubo dado não é determinado até que o anjo chegue nesse cubo. Mesmo assim, o caminho é determinado apenas aproximadamente. Isso assegura o diabo não pode apenas escolher um lugar no caminho suficientemente distante ao longo dele e bloqueá-lo.

Esta prova é devido ao Líder de Imre e Béla Bollobás. Uma prova que é substancialmente similar foi publicada por Martin Kutz.

Ligações externas

• The Angel problem by John H Conway

Referências

• Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your mathematical plays, volume 2: Games in Particular, Academic Press, 1982.
• John H. Conway, The angel problem, in: Richard Nowakowski (editor) Games of no chance, volume 29 of MSRI Publications, pages 3–12, 1996.