Alexey Pajitnov, 1955 —

O Desafio do Camarada Russo
Não existe uma fórmula perfeita para ganhar no game Tetris, nem mesmo com a ajuda de um computador

    Quando o engenheiro soviético Alexy Pajitnov criou o game Tetris em 1985, no final da Guerra Fria, não imaginava que alguns anos depois seu brinquedo seria quebra-cabeça eletrônico de maior sucesso no mundo capitalista. O jogo roubou horas produtivas de milhões de pessoas e foi considerado altamente viciante numa época em que os games eram mais simples. Muitos aficionados se lembram da experiência de sonhar com os bloquinhos coloridos se encaixando.
    Hoje, Tetris pode parecer banal para adolescentes acostumados a pilotar simuladores de vôo. Mas uma equipe de matemáticos dos EUA mostrou que a coisa não é bem assim. Mesmo supondo que tivéssemos tempo para pensar, não seria fácil saber o melhor lugar para encaixar cada bloco que cai na tela.
    David Liben-Nowell e colegas do MIT(Instituto de Tecnologia de Massachusetts), nos EUA, provaram que a elaboração de uma estratégia para se dar bem no Tetris envolve um dos tipos de problema mais complexos da matemática. O cálculo da solução requer um número de etapas exageradamente grande, porque não há como obter respostas diretas. É preciso testar várias. Em outras palavras, seria muito difícil um programa de computador ser infalível no jogo. É provável que um robô se saia melhor que jogadores humanos no Tetris, mas um software com fórmula 100% perfeita precisaria de soluções mais rápidas, em número de etapa menor.
    O inocente Tetris, afinal traz em si uma das questões mais misteriosas da matemática: a diferença entre problemas classificados como P(polinomial) e como NP(polinomial não-determinístico). Nos problemas P, é possível criar um algoritmo (série de regras, como as da divisão) que chega diretamente à resposta. Em NP, o computador tem de “testar” várias soluções até achar a certa, por isso demora mais. “Não-determinístico significa basicamente chute”, explica Liben-Nowell. Quando o problema tem inúmeras alternativas de resposta, mesmo que a verificação de cada uma delas seja simples, um computador pode levar anos de chute até escolher a certa.
    Na verdade, alguns matemáticos desconfiam que todo problema NP também pode ser solucionado com um algoritmo P, mas ninguém conseguiu provar isso ainda. A questão “P=NP?” é uma das mais estudadas em ciência da computação, e o felizardo que respondê-la levará o prêmio de U$ 1 milhão oferecido pelo Instituto de Matemática Clay, nos EUA. Dentro dos problemas NP, o Tetris foi classificado como do tipo NP-completo, o que dá uma qualidade especial. “Se for possível dar uma solução eficiente para um problema NP-completo, então poderíamos usar isso para dar uma solução eficiente para qualquer problema NP”, diz Liben-Nowell.
    Seria curioso se o inocente Tetris ajudasse a resolver um dos maiores enigmas da matemática, mas não parece ser essa intenção do MIT, já que existem problemas NP mais relevantes. Além disso, quando publicou seu trabalho em outubro passado, Liben-Nowell já parecia estar meio cansado: “Sonhei com algumas peças do Tetris se encaixando”.(Rafael Garcia)

(Revista Galileu Especial no. 1, Editora Globo, Abril de 2003)