Problema do anjo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 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[editar | editar código-fonte]

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 então o anjo ainda pode ganhar se ele é de poder grande o suficiente.

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

Questões adicionais não resolvidas[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  • 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.
Ícone de esboço Este artigo sobre enxadrismo é um esboço. Você pode ajudar a Wikipédia expandindo-o.