Chinook est un programme informatique qui joue au jeu de société des dames (également connu sous le nom de jeu de dames). Développé par une équipe de l'Université de l'Alberta dirigée par l'informaticien Jonathan Schaeffer, Chinook a été conçu pour rivaliser au plus haut niveau du jeu de dames humain. Il a atteint un jalon historique en 1994 en devenant le premier programme informatique à remporter un championnat du monde dans un jeu de stratégie contre un champion du monde humain, battant Marion Tinsley. En 2007, l'équipe de Chinook a annoncé que le programme avait effectivement résolu le jeu de dames, ce qui signifie qu'avec un jeu parfait des deux côtés, la partie se termine toujours par un match nul.
Le développement de Chinook a commencé en 1989 comme projet de recherche en intelligence artificielle et en théorie des jeux. Le programme utilise une combinaison d'algorithmes de recherche, de fonctions d'évaluation et d'un vaste livre d'ouvertures. Son succès repose sur les principes de la recherche minimax avec élagage alpha-bêta, une technique qui permet au programme d'explorer des millions de positions par seconde. Le programme a été affiné sur plusieurs années, avec des améliorations significatives de sa fonction d'évaluation et de son efficacité de recherche.
Réalisations au Championnat du Monde
La réalisation la plus célèbre de Chinook est survenue en 1990 lorsqu'il a obtenu le droit de défier le championnat du monde en terminant deuxième du championnat national américain de dames, devenant ainsi le premier ordinateur à se qualifier pour un titre mondial humain. En 1992, Chinook a joué un match contre Marion Tinsley, le champion du monde en titre et largement considéré comme le plus grand joueur de dames de tous les temps. Le match s'est terminé par un match nul après 40 parties, Tinsley conservant son titre. En 1994, une revanche a eu lieu, mais Tinsley s'est retiré après six parties pour des raisons de santé, et Chinook a été déclaré vainqueur, devenant ainsi le premier programme informatique à détenir un championnat du monde dans un jeu de société.
Après la retraite de Tinsley, Chinook a défendu son titre en 1995 contre Don Lafferty, remportant le match. Le programme a continué à participer à des tournois humains mais a finalement été retiré de la compétition après la saison 1996.
Résolution du Jeu de Dames
En 2007, l'équipe de Chinook a publié un article dans la revue Science annonçant qu'elle avait résolu le jeu de dames. La solution a impliqué un effort computationnel massif utilisant une combinaison d'analyse rétrograde et d'algorithmes de recherche pour prouver que le jeu est un match nul avec un jeu parfait. L'équipe a calculé une base de données de toutes les positions avec jusqu'à 10 pièces sur le plateau, ce qui a nécessité environ 10^14 calculs et a pris plus de 18 ans de temps de calcul continu (en utilisant le calcul distribué). Le résultat a montré qu'à partir de la position de départ standard, le jeu de dames est un match nul théorique, ce qui signifie qu'aucun joueur ne peut forcer une victoire si les deux jouent de manière optimale.
La résolution du jeu de dames a été une réalisation marquante en apprentissage automatique et en IA de jeu, car c'était le plus grand jeu résolu à l'époque, avec un espace de recherche d'environ 5×10^20 positions possibles. Elle a démontré la puissance de la combinaison d'algorithmes de recherche avec le calcul à grande échelle et a fourni des informations sur les limites de l'expertise humaine dans les jeux.
Approche Technique
L'architecture de Chinook était basée sur une conception classique d'IA de jeu. Il utilisait une recherche en profondeur avec élagage alpha-bêta pour évaluer les positions, et il employait une fonction d'évaluation sophistiquée qui prenait en compte le matériel, la mobilité et les avantages positionnels. Le programme disposait également d'un grand livre d'ouvertures, contenant des millions de positions issues du jeu d'experts, et d'une base de données de fin de partie construite à l'aide de l'analyse rétrograde. La base de données de fin de partie était cruciale pour le processus de résolution, car elle permettait au programme de jouer parfaitement dans les dernières étapes du jeu.
Pour l'effort de résolution, l'équipe a utilisé une technique appelée "recherche par nombre de preuves" pour guider la recherche vers les positions les plus susceptibles d'être des victoires ou des défaites. Ils ont également utilisé un réseau de calcul distribué pour traiter les milliards de positions dans la base de données de fin de partie. La solution finale était une preuve que le jeu de dames est un match nul, mais l'équipe a également montré que si l'un des joueurs commet une erreur, l'autre peut forcer une victoire.
Héritage et Impact
Le succès de Chinook a eu un impact significatif sur le domaine de l'intelligence artificielle et de la recherche sur les jeux. Il a inspiré des efforts ultérieurs pour résoudre d'autres jeux, comme le Puissance 4 (résolu en 1988) et, plus tard, le jeu de Go, abordé par des programmes comme AlphaGo. Chinook a également contribué au développement de techniques pour résoudre des jeux avec de grands espaces d'états, et son approche a été appliquée à d'autres problèmes combinatoires.
En plus de ses contributions techniques, Chinook a soulevé des questions philosophiques sur la nature de l'intelligence humaine par rapport à celle des machines. La victoire du programme sur un champion du monde humain a été un précurseur des réalisations ultérieures aux échecs (Deep Blue en 1997) et au Go (AlphaGo en 2016). Aujourd'hui, Chinook est rappelé comme un effort pionnier qui a démontré le potentiel des ordinateurs à maîtriser des jeux stratégiques complexes.
Le projet Chinook a également conduit au développement du benchmark Fhourstones, un test utilisé pour mesurer la performance des algorithmes de recherche. Le code et les bases de données du programme ont été mis à disposition à des fins de recherche, et son héritage continue d'influencer la conception des systèmes d'IA de jeu.