Tópico: Jogo de damas - a solução final

[Unknown]

Fim de jogo

Agência FAPESP – Acabou. Depois de séculos, o jogo de damas, um dos mais populares jogos de tabuleiros, foi resolvido. Por resolvido entenda-se a criação de um programa de computador sofisticado o bastante para escolher sempre a jogada perfeita entre todas as possíveis. E são muitas: cerca de 500 quintilhões, ou cinco vezes dez elevado à vigésima potência.

Foram precisos quase 20 anos de trabalho para que o grupo liderado por Jonathan Schaeffer, da Universidade de Alberta em Edmonton, no Canadá, conseguisse solucionar o jogo cuja história remonta ao Egito de cerca de 5 mil anos atrás. Em 1989, Schaeffer criou o Chinook, que entrou para a história da inteligência artificial cinco anos depois ao se tornar o primeiro programa de computador a derrotar um campeão mundial.

Desde então, o desafio dos pesquisadores canadenses deixou de ser simplesmente criar um software imbatível, mas solucionar o jogo de damas de uma vez por todas. A resposta demorou, mas acaba de ser conseguida e está descrita em artigo na edição de 20 de julho da revista Science.

De acordo com os cientistas, se os dois lados sempre executarem jogadas perfeitas, não há outra possibilidade além do empate. Algo similar ao que ocorre com o muito mais simples jogo da velha.

“Tecnologias de inteligência artificial têm sido usadas para gerar poderosos programas de jogos baseados na heurística. Solucionar um jogo nos leva ao próximo nível, ao substituir a heurística pela perfeição”, descreveram os autores. Ou seja, a simples exatidão entra no lugar da tentativa, da descoberta e da experiência. Jogadas sempre perfeitas, fim de jogo. Resultado: empate. Mas a graça continua, pois nenhum humano é capaz de calcular todas as combinações possíveis – a menos que recorra ao Chinook.

Mas, para a ciência, o feito é notável. “Trata-se de uma tremenda conquista, um avanço verdadeiramente significativo em inteligência artificial”, disse Jaap van den Herik, editor do International Computer Games Journal.

“Acho que subimos o nível – e o subimos consideravelmente – em termos de o que pode ser conseguido com tecnologia de informática e inteligência artificial”, disse Schaeffer.

“Conseguimos pegar o conhecimento usado em aplicações de inteligência artificial e levar até o extremo de substituir a heurística compreensível pelos humanos com o conhecimento perfeito. Trata-se de uma demonstração impressionante das possibilidades que os softwares e hardwares são capazes de atingir”, afirmou o pesquisador, que se descreve como um “sofrível” jogador de damas.

Foram usados até 200 computadores por vez e 50 em média para calcular as combinações possíveis em cada situação de uma partida. Agora que o jogo foi solucionado, o programa não precisa mais “aprender” a partir de combinações e tentativas, uma vez que se tornou um banco de dados que sabe sempre o movimento certo em cada situação.

O Chinook só deixa de ganhar um jogo caso seu oponente também saiba sempre a jogada perfeita. Ou seja, teria que ser outra máquina rodando o mesmo programa. No caso, a partida terminaria empatada.

“Estou muito entusiasmado com a conquista. Solucionar o jogo de damas se tornou como que uma obsessão pessoal de quase duas décadas e é realmente uma satisfação ver a conclusão”, disse Schaeffer.

O cientista afirma que não tentará resolver o xadrez, cuja complexidade exigiria milhares de anos de processamento com os computadores atuais. O próximo desafio está nas cartas. O grupo de Schaeffer levará outro programa, o Polaris, para o campeonato mundial de pôquer Homem versus Máquina, que será realizado na semana que vem, no Texas, nos Estados Unidos.

O artigo Checkers is solved, de Jonathan Schaeffer e outros, pode ser lido por assinantes da Science em www.sciencemag.org.

Quem quiser jogar contra o Chinook pode acessar o endereço www.cs.ualberta.ca/~chinook/play.php.

http://www.agencia.fapesp.br/boletim_dentro.php?data[id_materia_boletim]=7471

[Spitfire]

War games, who?

[Nigh†mare]

Foda mesmo!

Mas ainda estou invicto contra um humano desde 1998.

[Südenbauer]

Bah, que massa! Queria que fizessem isso no truco.

[uiliníli]

Damas e xadrez são fáceis. Ainda vai levar milênios é para resolverem o futebol

[Pregador]

Não sei se conseguirão resolver o xadrez... Talvez um mega-computador com um milhão de processadores e com um milhão de núcleos...

[uiliníli]

Qual é a relação dessa solução do jogo de damas como o problema P = NP? ? Quer dizer que o jogo de damas é um jogo do tipo polinominal?

[Guinevere]

O jogo de damas tem um tabuleiro 8x8. Tem uma versão também 10x10. Em ambos os casos, estamos falando de um problemas FINITOS.

A questão P versus NP tem a ver com problemas de qualquer tamanho arbitrário. Tipo: dá pra construir um programa que pegue qualquer tabuleiro de damas quadrado, de lado N, e dê a melhor jogada em tempo "bom".

Se não me engano, um tabuleiro de damas generalizado pra N por N é um problema PSPACE. PSPACE "deve" ser maior que NP, mas não se sabe ainda. Assim como NP "deve" ser maior que P, mas não se sabe.

O que chamo de maior é "tem mais problemas em PSPACE que em P", ou seja, tem problemas que dá pra resolver usando espaço polinomial que não dá pra resolver em tempo polinomial.


O que foi resolvido foi o tabuleiro 8x8, pelo que eu entendi. A solução de um tabuleiro NxN levaria tempo infinito e vai ter que ser resolvido usando métodos atualmente desconhecidos... Não dá pra testar todas as possibilidades.

Na verdade, acho que seria possível ainda dizer "o tabuleiro NxN sempre empata" ou "as brancas ganham" sem dizer COMO. Se não me engano... quem disser COMO terá resolvido PSPACE versus P. E possivelmente P versus NP, dependendo da resposta.