O Estado de São Paulo – Fernando Reinach*

Todos os anos os editores da revista Science escolhem o que consideram as grandes descobertas do ano. É uma oportunidade para ficar sabendo de descobertas importantes que não foram divulgadas pela imprensa.

Neste ano, em décimo colocado, elegeram o trabalho de matemáticos canadenses que, depois de 18 anos, ‘resolveram’ o problema do jogo de damas. A boa notícia é que essa descoberta não diminuirá em nada o prazer de jogar damas.

O jogo de damas é um jogo de complexidade média; muito mais complicado do que o jogo da velha, onde cada jogador coloca peças em um quadrado três por três tentando obter três peças alinhadas, mas muito mais simples do que o jogo de xadrez, onde diferentes peças têm movimentos peculiares e o número de posições possíveis em um tabuleiro é enorme.

No jogo de damas, o tabuleiro é o mesmo do xadrez, com oito quadrados de cada lado. O jogo só ocorre nos quadrados de uma mesma cor e cada jogador inicia com 12 peças idênticas organizadas em três fileiras. Os movimentos ocorrem na diagonal e as peças do adversário podem ser ‘comidas’ se for possível saltá-las, aterrissando no quadrado seguinte. O jogo é complexo. Foi calculado que o número total de possíveis configurações no tablado é de 500 bilhões de bilhões (500 quintilhões).

No caso do jogo da velha, qualquer criança aprende, após alguns meses de prática, que jogando corretamente é sempre possível forçar um empate. Em outras palavras, é impossível ganhar de um jogador habilidoso. A vitória só ocorre se um jogador errar. Quando uma criança aprende que isso é possível, a felicidade é enorme. A descoberta significa que o jogo está resolvido, ou seja, a receita para a vitória (ou empate) é conhecida. No caso do xadrez, os matemáticos ainda estão longe de saber se será possível um dia resolver o jogo. No máximo, conseguem programar computadores que jogam um pouco melhor que os melhores humanos. Nesse caso, o computador simplesmente ‘imita’ os mecanismos mentais dos jogadores e não é programado a partir da solução para o problema do jogo.

O que os cientistas canadenses conseguiram demonstrar é que, no caso do jogo de damas, existe uma solução para o problema e, se um dos jogadores for programado para jogar de acordo com essa solução, o máximo que o outro jogador pode obter é um empate.

Em outras palavras, é impossível vencer o programa que eles desenvolveram: o jogo de damas foi reduzido a uma versão complexa do jogo da velha.

Para isso, eles estudaram os 39 trilhões de configurações possíveis com dez peças ou menos. Analisar todas as possibilidades teóricas ainda está fora da capacidade dos maiores computadores atuais. Com esses dados e algumas deduções sobre os possíveis movimentos iniciais, eles conseguiram demonstrar que sempre é possível forçar um empate. Na prática, nenhum humano vai conseguir empatar com o computador, pois, para isso, é necessário não cometer nenhum erro. Dada a complexidade do jogo, vamos sempre cometer erros e o jogo vai sempre terminar em vitória do computador. Empate, somente quando um computador jogar contra outro.

Mas a grande descoberta é que, ao contrário do que ocorre com o jogo da velha, a solução do problema é tão complexa que nunca nenhum de nós vai se deparar com outro ser humano capaz de jogar utilizando a solução descoberta pelos canadenses. Portanto nada muda nas calçadas, nas praças e nos botequins.

Mais informações em: Game over. Science, vol. 318, pág. 1.848, 2007.

*Biólogo – fernando@reinach.com