Super Mario Bros. é um jogo bem mais difícil do que se imagina

Esqueça os traumas com equações diferenciais, a inabilidade com projeções geométricas ou a língua estranha dos logaritmos. O problema mais impossível que você enfrentou não estava nos livros de matemática, mas sim nos videogames. Pode ligar para seus professores de matemática e contar a novidade: Super Mario Bros. pode ser tão difícil quanto resolver os complexos problemas da computação estudados pelas competentes cabeças do MIT, Instituto de Tecnologia de Massachusetts (EUA).

É o que aponta um estudo desenvolvido por três professores de ciências da computação: Erik Demaine, que também ensina engenharia elétrica no MIT; Giovanni Viglietta, pesquisador da Universidade de Ottawa e pós-doutor em engenharia elétrica; e Aaron Williams, da Bard College. O trabalho mostra que o nível de complexidade dos problemas a serem resolvidos no game desenvolvido pela Nintendo pode ser tão complicado, em sua estrutura, quanto aqueles do chamado PSPACE – “conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço”, segundo a teoria da complexidade computacional. Em termos leigos: uma parada pra lá de difícil.

LEIA: 16 artistas criam imagens inspiradas no mundo de Super Mario Bros

O PSPACE contém problemas que não só requerem um tempo inimaginável para serem resolvidos por computadores, como também, no caso dos mais espinhosos, levam um tempo exponencial para serem verificados. Isso significa que, mesmo que o computador precise apenas checar se as respostas para determinado problema estão corretas – coisa que, com questões menos complexas, é uma tarefa rápida – pode levar teoricamente alguns quintilhões de anos no caso dos PSPACE. Matematicamente, jogos de videogame não são muito diferentes dos modelos computacionais do mundo real, e as ferramentas utilizadas para provar resultados de complexidade em um podem ser adaptadas para o outro. E é a complexidade da estrutura desses problemas possíveis dentro do jogo que interessa aos pesquisadores.

Demaine e Viglietta, que já investigam o jogo há alguns anos, agora estenderam sua análise de forma a considerar qualquer situação arbitrária possível. Na versão padrão do jogo de plataforma com rolagem lateral, Mario atravessa o terreno partindo do lado esquerdo da tela – enquanto luta contra monstros, o pequeno encanador deve completar várias tarefas; a fase termina quando Mario atinge um mastro. Para fazer os testes, os pesquisadores alteram alguns parâmetros do jogo convencional, fazendo com que toda a fase a ser completada apareça na tela de uma só vez, obrigando o computador a continuar lembrando dos monstrinhos presentes em todas as posições da fase (na versão padrão, os personagens fora do quadro são esquecidos pelo computador). Testando uma série de variáveis possíveis, eles mostraram que Super Mario Bros. pertence mesmo à classe dos problemas PSPACE – ou seja, eles dariam uma baita dor de cabeça até ao Pensador Profundo, o super-computador de O Guia do Mochileiro das Galáxias.

LEIA: Fã cria fase ultradifícil para o game Super Mario

O objetivo do novo estudo não é argumentar que o joguinho da sua infância é impossível de ser resolvido (ou seja, infelizmente você não é um gênio se conseguiu zerar o game). A ideia é mostrar que é possível construir problemas de nível PSPACE a partir das matérias-primas do mundo de Super Mario. Os professores usam esses exemplos dentro da sala de aula de maneira didática para tornar as classes ultra-avançadas em algo menos doloroso e apresentar uma forma divertida para se explorar as limitações dos algoritmos mais avançados.

O trabalho será apresentado na 8ª edição da conferência internacional Fun with Algorithms (“diversão com algoritmos”, em português), que será realizada neste mês na Itália, e os experts em teorias da computação avançadas podem conferir o estudo completo aqui.