Programas de damas são softwares de computador projetados para jogar o jogo de tabuleiro damas, também conhecido como draughts. Esses programas utilizam técnicas algorítmicas para avaliar posições, buscar movimentos ótimos e competir contra jogadores humanos ou outros computadores. O programa de damas mais proeminente é o Chinook, desenvolvido na Universidade de Alberta (embora o projeto fosse sediado lá, não em Toronto) por uma equipe liderada por Jonathan Schaeffer, que alcançou marcos históricos tanto no jogo competitivo quanto na resolução do jogo.
O Chinook foi desenvolvido entre 1989 e 2007 por uma equipe da Universidade de Alberta, composta por Jonathan Schaeffer, Rob Lake, Paul Lu, Martin Bryant e Norman Treloar. Diferentemente das abordagens modernas que dependem de aprendizado de máquina, o conhecimento do Chinook foi inteiramente codificado à mão por seus criadores, usando técnicas tradicionais de inteligência artificial, como algoritmos de busca e funções de avaliação. Essa distinção destaca a evolução da IA de sistemas baseados em regras para métodos orientados por dados.
Campeão Mundial Homem vs. Máquina
Em 1990, o Chinook conquistou o direito de competir no Campeonato Mundial humano ao terminar em segundo lugar para Marion Tinsley no Campeonato Nacional dos EUA. Inicialmente, a Federação Americana de Damas e a Associação Inglesa de Draughts se opuseram à participação de computadores em campeonatos humanos. Quando Tinsley renunciou ao título em protesto, essas organizações criaram o novo título de Campeonato Mundial Homem vs. Máquina, permitindo que a competição prosseguisse. Tinsley venceu a primeira partida com quatro vitórias, duas derrotas e 33 empates.
Uma revanche em 1994 resultou na declaração do Chinook como Campeão Mundial Homem-Máquina após seis jogos empatados, pois Tinsley se retirou devido a um câncer no pâncreas. Isso tornou o Chinook o primeiro programa de computador a vencer um título de campeonato mundial contra humanos, embora nunca tenha derrotado Tinsley, que era significativamente superior até mesmo aos seus rivais mais próximos. Em 1995, o Chinook defendeu seu título contra Don Lafferty em uma partida de 32 jogos, vencendo por 1-0 com 31 empates. Após isso, Schaeffer decidiu encerrar o jogo competitivo e se concentrar em resolver completamente as damas.
Algoritmo
O algoritmo do Chinook compreendia quatro componentes principais: um livro de aberturas contendo movimentos de partidas de grandes mestres, um algoritmo de busca profunda para explorar movimentos possíveis, uma função de avaliação de movimentos e um banco de dados de final de jogo cobrindo todas as posições com oito peças ou menos. A função de avaliação era uma função linear artesanal que considerava características como número de peças, número de damas, damas presas, vez de jogar e peças em fuga (peças com caminhos desimpedidos para se tornarem damas). Todo o conhecimento foi programado pelos criadores em vez de aprendido, contrastando com sistemas de IA posteriores, como as abordagens da DeepMind.
Linha do Tempo e Resolução das Damas
Marcos importantes no desenvolvimento do Chinook incluem: 1997, quando Schaeffer publicou o livro "One Jump Ahead: Challenging Human Supremacy in Checkers" (atualizado em novembro de 2008); 24 de maio de 2003, quando o banco de dados de 10 peças (5 peças por lado) foi concluído; e 2 de agosto de 2004, quando a abertura "White Doctor" (10-14 22-18 12-16) foi comprovada como empate. Outras aberturas foram comprovadas como empates em 18 de janeiro de 2006 (09-13 21-17 05-09) e 18 de abril de 2006 (09-13 22-17 13-22).
Em 10 de março de 2007, Schaeffer anunciou na conferência ACM SIGCSE que uma solução final era esperada dentro de 3 a 5 meses. Em 19 de julho de 2007, a revista Science publicou "Checkers Is Solved", provando que, com jogo perfeito, o melhor resultado é um empate. Isso tornou as damas o primeiro grande jogo de tabuleiro a ser completamente resolvido, seguindo trabalhos anteriores em jogos mais simples. No auge de sua fase competitiva, o Chinook foi avaliado em 2814 Elo.
Legado
O sucesso do Chinook demonstrou o poder das técnicas clássicas de IA, incluindo busca profunda e avaliação artesanal, antes do surgimento do aprendizado profundo. Sua solução das damas permanece uma conquista marcante na IA de jogos, comparável aos computadores de xadrez como o Deep Blue. Embora programas modernos de damas possam usar redes neurais, a abordagem do Chinook influenciou pesquisas subsequentes em teoria dos jogos e resolução combinatória de jogos, e seus métodos ainda são estudados em cursos de IA em instituições como a Universidade Carnegie Mellon e o MIT CSAIL.