Les programmes de dames sont des logiciels conçus pour jouer au jeu de société des dames, également connu sous le nom de jeu de dames anglaises. Ces programmes utilisent des techniques algorithmiques pour évaluer les positions, rechercher les coups optimaux et affronter des joueurs humains ou d'autres ordinateurs. Le programme de dames le plus célèbre est Chinook, développé à l'Université de l'Alberta (bien que le projet y ait été basé, et non à Toronto) par une équipe dirigée par Jonathan Schaeffer, qui a atteint des jalons historiques tant dans le jeu compétitif que dans la résolution du jeu.
Chinook a été développé entre 1989 et 2007 par une équipe de l'Université de l'Alberta, composée de Jonathan Schaeffer, Rob Lake, Paul Lu, Martin Bryant et Norman Treloar. Contrairement aux approches modernes qui reposent sur le apprentissage automatique, la connaissance de Chinook était entièrement codée à la main par ses créateurs, utilisant des techniques traditionnelles d'intelligence artificielle telles que les algorithmes de recherche et les fonctions d'évaluation. Cette distinction met en évidence l'évolution de l'IA, passant de systèmes basés sur des règles à des méthodes guidées par les données.
Champion du monde homme contre machine
En 1990, Chinook a obtenu le droit de participer au championnat du monde humain en terminant deuxième derrière Marion Tinsley aux championnats nationaux des États-Unis. Initialement, la Fédération américaine de dames et l'Association anglaise de dames se sont opposées à la participation d'ordinateurs aux championnats humains. Lorsque Tinsley a démissionné de son titre en signe de protestation, ces organisations ont créé le nouveau titre de champion du monde homme contre machine, permettant ainsi à la compétition de se dérouler. Tinsley a remporté le premier match avec quatre victoires, deux défaites et 33 parties nulles.
Une revanche en 1994 a abouti à la déclaration de Chinook comme champion du monde homme-machine après six parties nulles, Tinsley s'étant retiré en raison d'un cancer du pancréas. Cela a fait de Chinook le premier programme informatique à remporter un titre de champion du monde contre des humains, bien qu'il n'ait jamais vaincu Tinsley, qui était nettement supérieur même à ses plus proches rivaux. En 1995, Chinook a défendu son titre contre Don Lafferty lors d'un match de 32 parties, remportant 1-0 avec 31 parties nulles. Après cela, Schaeffer a décidé d'arrêter le jeu compétitif et de se concentrer entièrement sur la résolution du jeu de dames.
Algorithme
L'algorithme de Chinook comprenait quatre composants principaux : un livre d'ouvertures contenant des coups de parties de grands maîtres, un algorithme de recherche approfondie pour explorer les coups possibles, une fonction d'évaluation des coups et une base de données de fin de partie couvrant toutes les positions avec huit pièces ou moins. La fonction d'évaluation était une fonction linéaire artisanale prenant en compte des caractéristiques telles que le nombre de pièces, le nombre de dames, les dames piégées, le tour de jeu et les pions en fuite (pièces ayant des chemins sans obstacle pour devenir des dames). Toute la connaissance était programmée par les créateurs plutôt qu'apprise, contrastant avec les systèmes d'IA ultérieurs comme les approches de DeepMind.
Chronologie et résolution du jeu de dames
Les jalons clés du développement de Chinook incluent : 1997, lorsque Schaeffer a publié le livre « One Jump Ahead: Challenging Human Supremacy in Checkers » (mis à jour en novembre 2008) ; le 24 mai 2003, lorsque la base de données à 10 pièces (5 pièces par camp) a été achevée ; et le 2 août 2004, lorsque l'ouverture « White Doctor » (10-14 22-18 12-16) a été prouvée comme nulle. D'autres ouvertures ont été prouvées nulles le 18 janvier 2006 (09-13 21-17 05-09) et le 18 avril 2006 (09-13 22-17 13-22).
Le 10 mars 2007, Schaeffer a annoncé lors de la conférence ACM SIGCSE qu'une solution finale était attendue dans les 3 à 5 mois. Le 19 juillet 2007, la revue Science a publié « Checkers Is Solved », prouvant qu'avec un jeu parfait, le meilleur résultat est une partie nulle. Cela a fait du jeu de dames le premier grand jeu de société à être complètement résolu, après des travaux antérieurs sur des jeux plus simples. Au sommet de sa carrière compétitive, Chinook était classé à 2814 Elo.
Héritage
Le succès de Chinook a démontré la puissance des techniques classiques d'IA, y compris la recherche approfondie et l'évaluation artisanale, avant l'essor du apprentissage profond. Sa résolution du jeu de dames reste une réalisation marquante dans l'IA de jeu, comparable aux ordinateurs d'échecs comme Deep Blue. Bien que les programmes de dames modernes puissent utiliser des réseaux de neurones, l'approche de Chinook a influencé les recherches ultérieures en théorie des jeux et en résolution combinatoire de jeux, et ses méthodes sont encore étudiées dans les cours d'IA dans des institutions comme l'Université Carnegie Mellon et le CSAIL du MIT.