PASSEIO ALEATÓRIO

Damas

Por Nuno Crato

SAIU NA REVISTA SCIENCE um artigo em que Jonathan Schaeffer e outros sete investigadores da Universidade de Alberta, no Canadá, revelavam ter resolvido o Jogo das Damas. É uma notícia importante. O jogo é simples, mas até agora não se sabia se tinha ou não solução. Conseguiu provar-se que sim — se ambos os contendores não cometerem falhas, o jogo termina sempre em empate.

Passa-se pois com as Damas algo semelhante ao jogo do galo, que se torna fastidioso para jogadores que conheçam a estratégia óptima. O Jogo de Damas, contudo, é muito mais complexo. Tem 500 milhões de milhões de milhões de posições possíveis. Os investigadores, apesar de terem estudado o problema durante duas décadas e de terem usado centenas de computadores a trabalhar em paralelo, tiveram de seguir uma estratégia de ataque muito subtil. Estudaram os 39 milhões de milhões de casos em que há dez ou menos peças sobre o tabuleiro e determinaram quais as posições que desembocariam num empate se ambos os jogadores seguissem estratégias óptimas. Mostraram depois que, seguindo ambos os jogadores estratégias óptimas desde o começo do jogo, eram sempre conduzidos a uma das posições de dez peças que desembocavam num empate. Problema resolvido!

Isto não significa, contudo, que o jogo das Damas se tenha tornado tão fácil que não mereça a pena ser jogado. Não. As posições são tantas e os movimentos tão complicados que continua a ser impossível a um jogador não cometer falhas. O que pode ser em breve possível é construir um programa de computador que nunca perca neste jogo. Algo que continua a não ser possível no xadrez. Esperemos.

«Expresso» de 28 de Julho de 2007