Você teria coragem de jogar o jogo mais complexo feito pela humanidade?

Não é segredo pra ninguém que sou apaixonado por jogos e tem algo nos problemas mentalmente exigentes que me atrai de um jeito particular. Por isso quero contar uma história que une duas paixões: o meu jogo de cartas favorito e um dos resultados mais perturbadores da ciência da computação dos últimos anos.

Spoiler: o jogo que jogo nos fins de semana é, formalmente, o jogo computacionalmente mais complexo já criado pela humanidade.

🎴 Um pouco de contexto

Magic: The Gathering foi criado em 1993 por Richard Garfield, matemático e PhD em combinatória. A primeira edição, apelidada de Alpha, trouxe 295 cartas. Era um experimento pois ninguém imaginava que ele estava plantando a semente de algo que sobreviveria 30 anos e seria estudado em departamentos de Ciência da Computação no mundo inteiro.

Richard Garfield - Criador do Magic

📖 É realmente tao complexo assim?

PDF MagicCompRules atualizado em 2026-04-17

O livro de regras oficial do Magic, o Comprehensive Rules, mantido pela Wizards of the Coast, tem 309 páginas na versão mais recente (abril de 2026). Sem o menor exagero é um documento jurídico-técnico que define cada interação possível do jogo, com sub-regras numeradas no estilo "704.5k", "704.5m", "704.5n". Curiosidade: o documento pula as letras "l" e "o" propositalmente, pra não confundir com os números "1" e "0".

Esse documento é a prova circunstancial de que estamos lidando com um sistema lógico-formal disfarçado de jogo. Documentação de software de avião comercial costuma ser menor. E é exatamente essa complexidade que abre a porta pro que vem a seguir.

🔗 Você pode ler o documento completo em: https://magic.wizards.com/en/rules

🧠 O paper que mostrou para o mundo a complexidade

Em 2019, três pesquisadores:

• Alex Churchill (Cambridge)
• Stella Biderman (Georgia Tech)
• Austin Herrick (Wharton/UPenn)

publicaram no arXiv um artigo que respondeu a uma pergunta aberta há mais de uma década na teoria computacional dos jogos:

"Magic: The Gathering is Turing Complete" (arXiv:1904.09828)

Eles fizeram o que muitos consideravam impossível: embutiram uma Máquina de Turing Universal (a (2,18) de Rogozhin) dentro de uma partida real de Magic, usando 60 cartas legais em torneio do formato Legacy. O teorema central:

"Determinar o vencedor de uma partida de Magic em que todos os movimentos restantes são forçados é indecidível."

Isso coloca o jogo na mesma classe do Halting Problem de Turing o problema fundador da ciência da computação, provado insolúvel por Alan Turing em 1936.

🔧 Como eles fizeram

A ideia, em linguagem humana, é mais simples do que parece:

Cada carta vira uma "peça" de um computador.

Algumas cartas funcionam como memória (guardam o estado da computação). Outras funcionam como circuitos lógicos (executam um "se isso, então aquilo"). E as criaturas em jogo viram uma "fita" onde os dados ficam armazenados, exatamente como a fita de uma Máquina de Turing tradicional.

O truque genial: em Magic, algumas cartas podem reescrever o texto de outras cartas durante a partida. Existem cartas que literalmente trocam palavras em outras cartas no meio do jogo. É como se, jogando dominó, você pudesse pegar uma peça e mudar o número dela enquanto a cadeia ainda está caindo. Foi assim que os pesquisadores conseguiram "programar" 36 instruções diferentes da Máquina de Turing usando cartas comuns.

Uma vez montado o tabuleiro, nenhum dos dois jogadores precisa tomar qualquer decisão, as interações entre as cartas são obrigatórias e cascateiam automaticamente, executando o "programa" como um relógio mecânico. Cada 3 ou 4 turnos avança um passo da computação.

O detalhe mais surpreendente: todas as cartas usadas são reais e legais em torneio. O paper inclui um decklist completo de 60 cartas (abaixo) que, em teoria, você poderia registrar num torneio Legacy oficial.

Tabela retirada diretamente do Paper das cartas utilizadas

Imagem das cartas montadas como deck e seu valor atual 🔗https://www.ligamagic.com.br/?view=dks/deck&id=10025474

🤖 Por que isso é relevante pra Inteligência Artificial?

Compare com os jogos que a IA já dominou:

• ♟️ Xadrez (Deep Blue, 1997) -> informação perfeita, espaço finito
• 🀄 Go (AlphaGo, 2016) -> informação perfeita, espaço astronômico
• 🃏 Poker (Pluribus, 2019) -> informação imperfeita, regras fixas
• 🎴 Magic -> informação imperfeita + estocasticidade + 20.000 cartas + regras que modificam as próprias regras

Chatterjee & Ibsen-Jensen (2016) já tinham mostrado que apenas verificar se um bloqueio (uma das varias mecanicas do jogo) é legal em Magic é coNP-completo. Agora sabemos que o jogo inteiro é não-computável.

Pra abordagens de aprendizagem por reforço, isso não é uma questão de "jogar mais GPUs no problema":

Existem cenários em que avaliar o próximo estado do jogo é matematicamente impossível — independente do quanto você escale o modelo.

É o stress test definitivo pra qualquer algoritmo de tomada de decisão sob incerteza

Busca simples de numero de cartas jogaveis

🏰 E isso tudo era só o aquecimento

Tudo o que foi citado acima como o paper de 2019, a indecidibilidade, a comparação com Halting Problem foi provado em um cenário de 60 cartas, 1v1, com no máximo 4 cópias da mesma carta no deck.

O modo de jogo mais popular hoje se chama Commander:

• 100 cartas no baralho (em vez de 60)
• Apenas 1 cópia de cada carta permitida (singleton)
• 4 jogadores simultaneamente em formato free-for-all
• 30.968 cartas legais hoje, com cerca de 2.000 cartas novas lançadas por ano

Mesa real num ponto inicial do jogo

A interação entre 4 jogadores com decks únicos transforma o jogo num sistema multi-agente parcialmente observável de complexidade combinatória explosiva. Cada turno é uma negociação social + um cálculo de teoria dos jogos + uma execução de regras que podem ter exceções aninhadas três níveis de profundidade.

🎯 Fechamento

Este é o jogo computacionalmente mais complexo conhecido pela humanidade. E dificilmente será batido porque, como demonstram Churchill, Biderman e Herrick, a complexidade não está na quantidade de cartas, mas no fato de que as cartas reescrevem as regras do jogo dinamicamente. É uma propriedade matemática estrutural.

Tudo isso é só a ponta do iceberg de 30 anos de Magic. Teoria dos jogos, busca por jogadas ótimas, profundidade combinatória, otimização sob incerteza. Cada um desses tópicos rende artigos científicos por ano em conferências de IA do mundo inteiro. Mas o que mais me anima não é isso. É lembrar que o jogo computacionalmente mais complexo já estudado pela humanidade é o mesmo que eu jogo casualmente nos meus fins de semana, com amigos, por pura paixão. A complexidade que vira paper em Cambridge é a mesma que vira risada numa mesa de sexta à noite e isso, pra mim, é o melhor dos dois mundos.

📚 Referências:

• Churchill, A., Biderman, S., & Herrick, A. (2019). Magic: The Gathering is Turing Complete. arXiv:1904.09828
• Demaine, E. & Hearn, R. (2009). Games, Puzzles, and Computation. CRC Press
• Chatterjee, K. & Ibsen-Jensen, R. (2016). The complexity of deciding legality of a single step of Magic: The Gathering. ECAI 2016
• Auger, D. & Teytaud, O. (2012). The frontier of decidability in partially observable recursive games. IJFCS