Chinook (programa de computador) - Chinook (computer program)
Chinook é um programa de computador que joga damas (também conhecido como rascunhos). Foi desenvolvido entre os anos de 1989 a 2007 na Universidade de Alberta , por uma equipe liderada por Jonathan Schaeffer e composta por Rob Lake , Paul Lu , Martin Bryant e Norman Treloar . Os algoritmos do programa incluem um livro de abertura que é uma biblioteca de movimentos de abertura de jogos jogados por grandes mestres de damas; um algoritmo de pesquisa profunda; uma boa função de avaliação de movimento; e um banco de dados de final de jogo para todas as posições com oito peças ou menos. Todo o conhecimento do Chinook foi programado por seus criadores, ao invés de aprendido usando um sistema de inteligência artificial .
Campeão Mundial Homem vs. Máquina
Chinook é o primeiro programa de computador a ganhar o título de campeão mundial em uma competição contra humanos. Em 1990, ganhou o direito de jogar no Campeonato Mundial humano ao ficar em segundo lugar para Marion Tinsley no Nacional dos Estados Unidos. No início, a American Checkers Federation e a English Drafts Association foram contra a participação de um computador em um campeonato humano. Quando Tinsley renunciou ao título em protesto, a ACF e a EDA criaram o novo título Man vs. Machine World Championship , e a competição prosseguiu. Tinsley venceu com quatro vitórias contra duas de Chinook, com 33 empates.
Em uma revanche, Chinook foi declarado o Campeão Mundial Homem-Máquina em damas em 1994 em uma partida contra Marion Tinsley após seis jogos empatados, e a retirada de Tinsley devido a câncer no pâncreas. Embora Chinook tenha se tornado o campeão mundial, ele nunca derrotou o melhor jogador de damas de todos os tempos, Tinsley, que era significativamente superior até mesmo ao seu par mais próximo.
Em 1995, Chinook defendeu seu título homem-máquina contra Don Lafferty em uma partida de 32 jogos. O placar final foi 1–0 com 31 empates para Chinook sobre Lafferty. Após a partida, Jonathan Schaeffer decidiu não deixar o Chinook competir mais, ao invés disso, tentou resolver o jogo de damas. Na época, foi avaliado em 2814 Elo . A solução foi alcançada e o resultado publicado em 2007.
Algoritmo
O algoritmo do programa de Chinook inclui um livro de abertura, uma biblioteca de movimentos de abertura de jogos jogados por grandes mestres; um algoritmo de pesquisa profunda; uma boa função de avaliação de movimento; e um banco de dados de final de jogo para todas as posições com oito peças ou menos. A função de avaliação artesanal linear considera vários recursos do tabuleiro de jogo, incluindo contagem de peças, contagem de reis, reis presos, turno, damas em fuga (caminho desimpedido para ser rei) e outros fatores menores. Todo o conhecimento do Chinook foi programado por seus criadores, ao invés de aprendido com inteligência artificial.
Linha do tempo
- 1997 - Jonathan Schaeffer escreve um livro sobre Chinook chamado One Jump Ahead: Challenging Human Supremacy in Checkers . Uma versão atualizada do livro foi publicada em novembro de 2008.
- 24 de maio de 2003 - O Chinook completa seu banco de dados de 10 peças com 5 peças de cada lado.
- 2 de agosto de 2004 - A equipe Chinook anuncia que a abertura do torneio em damas, chamada White Doctor (10-14, 22-18, 12-16), provou ser um empate.
- 18 de janeiro de 2006 - A equipe Chinook anuncia que a abertura de 21-17 de 09 a 17 de 05-09 provou ser um empate.
- 18 de abril de 2006 - A equipe Chinook anuncia que a abertura de 13 a 22 de 13 a 13 de setembro provou ser um empate.
- 10 de março de 2007 - Jonathan Schaeffer anuncia (na conferência ACM SIGCSE 2007) que uma solução final para verificadores é esperada dentro de 3–5 meses.
- 19 de julho de 2007 - A revista Science publica o artigo da equipe de Schaeffer "Damas Is Solved", apresentando a prova de que o melhor que um jogador pode alcançar jogando contra um jogador com informações perfeitas é um empate.