ZAP // NightCafe Studio
Com um número impressionante de posições possíveis no tabuleiro, Othello é o jogo mais complexo alguma vez resolvido.
Qualquer pessoa que alguma vez tenha jogado o Jogo do Galo provavelmente percebeu que o jogo pode sempre terminar em empate, desde que nenhum dos jogadores cometa erros.
De facto, no caso deste popular jogo, é fácil criar um algoritmo que garanta sempre a um jogador a vitória ou o empate, independentemente dos movimentos do adversário.
O Jogo do Galo é um exemplo trivial de um jogo que foi “resolvido” — em que o resultado é determinado desde o início.
Há muitos outros jogos que foram também ja resolvidos, mas outros tantos que continuam por solucionar.
Para os investigadores da Teoria dos Jogos e os cientistas de computação, a dificuldade em resolver um jogo geralmente depende do número de posições possíveis.
Por exemplo, o famoso Quatro em Linha, jogado num tabuleiro de 6×7, tem 4.531.985.219.092 posições possíveis. Os cientistas de computação resolveram o jogo em 1988, mostrando que o jogador que começa primeiro tem sempre uma forma de forçar uma vitória.
O jogo das Damas é significativamente mais complexo, com as 500 triliões de posições possíveis no tabuleiro. Este popular jogo só foi resolvido em 2007, ano em que uma equipa de cientistas da computação demonstrou que se ambos os lados jogarem perfeitamente, o jogo terminará sempre em empate.
Agora, Hiroki Takizawa, bioinformático da empresa de computação japonesa Preferred Networks, resolveu Othello (ou Reversi), um jogo com 1028 (um 1 seguido de 28 zeros) de possíveis posições.
“Resolver Othello, determinando o resultado de um jogo em que nenhum dos jogadores cometa um erro, foi até agora um grande desafio na ciência da computação”, diz Takizawa, citado pela Discover Magazine.
“Othello está agora resolvido“, anuncia o bioinformático nipónico.
Othello é um jogo para duas pessoas jogado num tabuleiro de 8×8 inventado em Inglaterra em 1883. Nos anos 70, o jogo tornou-se popular no Japão, nos EUA e outros países, incluindo Portugal. Desde 1977 que se disputam anualmente os seus Campeonatos Mundiais, apenas interrompidos pela pandemia de COVID-19.
No jogo, os jogadores colocam alternadamente peças no tabuleiro com o lado preto ou branco virado para cima. O objetivo do jogo é virar as peças da cor do adversário (brancas ou pretas), rodeando-as por peças da cor oposta.
As combinações possíveis decorrentes destas mudanças tornam particularmente difícil para os jogadores humanos antecipar as jogadas seguintes. Obviamente, os algoritmos de computador, que andam desde a década de 1990 a ganhar jogos de computador a humanos, não têm tais problemas.
Recentemente, numa pesquisa cujos resultados foram apresentados num artigo pré-publicado no arXiv, Takizawa modificou um desses algoritmos — um programa chamado Edax — para resolver o jogo aplicando-lhe “força bruta” computacional.
Dois fatores tornaram-no possível: Takizawa modificou o Edax para o tornar mais adequado a este tipo de resolução de problemas num jogo como Othello, e depois dividiu a tarefa em partes mais pequenas e fáceis de gerir.
O bioinformático japonês analisou então o problema depois de 14 espaços terem sido ocupados, deixando 50 espaços vazios no tabuleiro. Depois, analisou novamente o problema quando restavam apenas 36 espaços vazios.
Takizawa executou o seu programa num cluster de supercomputadores da Preferred Networks chamado MN-J, que inclui o MN-3, atualmente classificado como o 11º supercomputador mais poderoso do mundo em termos de eficiência energética. Em 2020, este supercomputador ocupava o 1º lugar do ranking.
Resultado desta prova de força bruta: tal como nas Damas, se ambos os jogadores fizerem sempre o jogo perfeito, sem erros, o jogo termina sempre num empate.
Qual o próximo passo para os cientistas de computação que jogam jogos?
Provavelmente, especula Takizawa, o Xadrez pode ser o próximo jogo a ser resolvido. Mas este é um enorme desafio, que exigira significativamente mais trabalho e capacidade computacional. O número de posições possíveis num jogo no Xadrez é espantoso: 1043, ou seja, 1 com 43 zeros.
Assim, talvez tenhamos que esperar pela computação quântica para ver o Xadrez finalmente “resolvido”.
