Magic: the Gathering Turing está completo?

24

Uma pergunta muito específica, eu sei, e duvido que seja respondida por qualquer um que ainda não esteja familiarizado com as regras da Magia. Postagens cruzadas para Draw3Cards . Aqui estão as regras abrangentes para o jogo Magic: the Gathering . Veja esta pergunta para obter uma lista de todos os cartões mágicos. Minha pergunta é - o jogo Turing está completo?

Para mais detalhes, consulte a publicação em Draw3Cards .

ripper234
fonte
11
(1) Qual é a entrada? Você supõe que conhece o conteúdo e a ordem das cartas nos decks de ambos os jogadores? (2) Para analisar sua complexidade, um problema deve ter infinitamente muitas entradas possíveis. Por exemplo, não podemos dizer que o xadrez é EXP-completo (mesmo que o digamos, isso significa que a generalização do xadrez para um tabuleiro n × n é EXP-completa). Como você generaliza o jogo? (3) O jogo pode ser muito complicado para analisar sua complexidade, mas eu não sei.
Tsuyoshi Ito
11
@ Daniel: Obrigado. Na verdade, eu verifiquei também, mas não tinha certeza se alguém quer analisar o jogo em que cada carta, exceto as cartas terrestres, está restrita a no máximo 4 cópias e apenas o número de cartas terrestres pode crescer.
Tsuyoshi Ito
11
@ Daniel: Não tenho certeza se a lógica funciona dessa maneira, porque existem vários tipos diferentes de cartas terrestres. Afinal, o jogo original em si pode ser complicado o suficiente para que Turing esteja completo. O que não tenho certeza é se o autor da pergunta realmente deseja analisar o jogo em que quase todas as cartas de um baralho são necessariamente cartas de terra. Vou aguardar a resposta do solicitante.
Tsuyoshi Ito
4
@ Daniel: Isso não é uma objeção razoável! A maioria das reduções de dureza dos jogos produz algo que se parece mais com a redução do que o jogo original. (Ciclos hamiltonianos não surgem naturalmente em correntes de ar, por exemplo.)
Jeffε
11
@ Tsuyoshi - Eu acho que seria perguntar se Magic é decidível. Para que essa pergunta seja significativa, você pode assumir informações perfeitas - todas as bibliotecas e mãos são reveladas e todos os lançamentos aleatórios de moedas e similares são predeterminados. É possível determinar de todas as posições mágicas quem é o vencedor?
ripper234

Respostas:

15

Ok, tenho uma solução que evita o problema de queima de mana que encontrei. Isso é meio que um hack, já que eu preciso assumir que os jogadores podem identificar terrenos específicos, o que não acho que seja tratado nas regras. Na prática, esse é o caso, pois eles podem ser organizados em uma linha com base na ordem em que são jogados.

Primeiro, a descrição completa do problema no site Draw3Cards:

Uma resposta positiva seria composta desses componentes:

  1. Uma função computável fM da Turing Machines para decks de Magic ordenados (onde a ordem da biblioteca importa)
  2. Duas estratégias determinísticas e computáveis ​​bem definidas para jogar Magic (que não dependem do baralho). Vamos chamá-los de Estratégia TS (Estratégia de Turing) e Estratégia IS (Estratégia de Entrada).
  3. Uma maneira computável de codificar qualquer sequência de zeros e zeros como um deck de entrada mágica. Uma dessas maneiras seria pegar o número Gödel da corda e colocar o maior número de ilhas no deck de entrada.

A condição adicional que deve ser satisfeita é a seguinte: Dada a Turing Machines TM, vamos considerar o resultado do jogo Magic entre a estratégia TS jogando com o deck fM (TM) contra a estratégia TI jogando com o deck fI (I), quando as bibliotecas são não embaralhado antes do jogo começar. Este jogo deve ser ganho pelo primeiro jogador se e somente se TM (I) = verdadeiro.

Então aqui está a ideia. Temos dois jogadores, A e B. B fornecerá a entrada, enquanto A implementará diretamente uma máquina de Turing. Os decks serão compostos quase inteiramente de terra, mas também a carta Gemstone Array para anular a queima de mana. A terá 3 tipos de terra: ilhas, montanhas e florestas. A idéia básica é usar terra explorada para representar um 1 e terra inexplorada para representar um 0. Ilhas serão usadas para representar o estado da fita, Montanhas para indexar a posição atual ao longo da fita e Florestas para representar o estado interno de 24. máquina de Turing do símbolo do estado 2 (acredito que exista uma universal devido a Rogozhin).

25=32.>242m+1 1

25=32.>242m+1 1

Estratégia: A e B jogam um terreno por turno na ordem em que são sorteados. Quando cada um desenha 4 florestas, eles jogam Artefato de Pedra Preciosa. Nota A vai primeiro, então já tem uma ilha quando B empates toca seu primeiro cartão de entrada.

A e B simplesmente continuam colocando suas cartas em ordem até B esgotar suas planícies e pântanos e jogar sua primeira ilha. Em sua próxima jogada, A, por tudo que toca na sua ilha, se Bs com o Input Land era um pântano. A inicializa sua máquina de bater tocando em sua primeira Floresta e Montanha. Se ele tiver tocado um número ímpar de cartas, ele toca em seu forrest extra e usa toda essa mana para adicionar fichas ao Gemstone Array. A partir daqui, a jogada prossegue da seguinte forma: B usa sua vez para simplesmente espelhar o estado da mana de A. B toca em sua terra de entrada se a ilha de A é tocada. Da mesma forma, B toca em sua 1ª Floresta (Montanha) se for tocada em A ésima Floresta (Montanha). Como A sempre toca em um número par de cartas, o mesmo acontece com B, e a mana é usada para adicionar fichas ao Gemstone Array.

No turn de A, toda a mana de A fica inexplorada, de modo que A olha o estado da mana de B, representa o estado da mana de A no turno anterior. A aplica a regra de transição de acordo com a máquina universal (24,2) ao estado de B para obter seu novo estado.

O jogo prossegue dessa maneira até a máquina de turing parar. Nesse ponto, A coloca suas montanhas no estado reservado "terminado" (o estado todo inexplorado). Se a máquina de Turing parar em um estado aceitável, B copia o estado das montanhas de A, mas aproveita toda a terra restante, negligenciando o uso da matriz Gemstone, iniciando assim o processo de suicídio por queima de mana. No turno de A, se as montanhas de B estiverem no estado "terminado" e todas as outras terras de B forem exploradas, A simplesmente não faz nada (observe que as montanhas estão automaticamente no estado "terminado"). Se as montanhas de A estiverem no estado final, mas nada mais for explorado, B continuará o suicídio por queima de mana. Isso é repetido até que B esteja morto.

Se, no entanto, a máquina terminar no estado de rejeição, B deixa todos os cartões inexplorados. Se todas as cartas de B são inexploradas, A bate em todas as cartas, iniciando o mesmo processo de suicídio por queima de mana. Se todas as cartas que não pertencem à montanha de A forem tocadas e as montanhas não utilizadas, B deixa todas as cartas inexploradas. Isso levará A a continuar a mana queimar suicídio até que ele perca o jogo.

Isso deve satisfazer os critérios solicitados na pergunta e, portanto, quando essa ordem é permitida, acredito que o jogo seja Turing completo no sentido descrito na pergunta.

Joe Fitzsimons
fonte
2
Legal. Um pensamento extra: contanto que qualquer jogador toque mais de 1 terreno por turno, você pode usar cargas na Matriz de Pedras Preciosas para evitar queima de mana. Por exemplo, se eu precisar tocar em 3 terrenos, transformo dois mana em uma carga, gasto a carga para gerar uma mana e depois gasto as duas manas restantes para criar uma nova carga. - é claro, você já resolveu esse problema de qualquer maneira. :)
Daniel Apon
2
Aewsome! Também pode ser mais fácil para simular uma máquina de 2-counter (usando diferentes tipos de mana como os contadores) em vez de simular diretamente uma máquina de Turing: en.wikipedia.org/wiki/...
Jeffε
3
Sua redução também implica que a magia (cooperativa) com um número finito de cartões é difícil para o PSPACE.
Jeffε
3
@ Joe - não há mais mana burn no Magic. Você pode usar o Platinum Angel para evitar perder devido à falta de cards no seu cemitério.
usar o seguinte código
11
@ Joe - você perdeu meu comentário anteriormente de que o conceito de queima de mana foi completamente removido das regras. Você pode consertá-lo fazendo com que cada jogador tenha uma cópia do Fireball em seu baralho.
ripper234
7

Alex Churchill, Stella Biderman e Austin Herrick publicaram este artigo mostrando que Magic is Turing Complete

Resumo - Magic: The Gathering é um jogo de baralho popular e famoso por ser complicado sobre combate mágico. Neste artigo, mostramos que o jogo ideal na magia do mundo real é pelo menos tão difícil quanto o Problema de Parada, resolvendo um problema que está aberto há uma década [1], [10]. Para fazer isso, apresentamos uma metodologia para incorporar uma máquina de Turing arbitrária em um jogo de Magic, de modo que o primeiro jogador tenha a garantia de ganhar o jogo se e somente se a máquina de Turing parar. Nosso resultado se aplica à maneira como o Magic é jogado, pode ser alcançado usando decks legais de torneios de tamanho padrão e não depende de estocástica ou informações ocultas. Nosso resultado também é altamente incomum, pois todos os movimentos de ambos os jogadores são forçados na construção. Isso mostra que mesmo o reconhecimento de quem vencerá um jogo no qual nenhum dos jogadores tem uma decisão não trivial de tomar pelo resto do jogo é indecidível. Concluímos com uma discussão das implicações para uma teoria computacional unificada dos jogos e observações sobre a jogabilidade de tal tabuleiro em um ambiente de torneio.

DerMolly
fonte