Chinook (programme de dames)

Chinook est un programme informatique qui joue aux dames anglaises (connues aussi sous le nom de checkers ou de draughts). Il fut développé entre 1989 et 2007 à l'université de l'Alberta, par une équipe dirigée par Jonathan Schaeffer et formée par Rob Lake, Paul Lu, Martin Bryant (en), et Norman Treloar. En 2007, il a obtenu une solution complète du jeu, montrant qu'entre deux joueurs parfaits, la partie se conclut nécessairement par la nullité.

Championnat du Monde Homme contre Machine

Chinook est le premier programme informatique à avoir gagné le titre de champion du monde dans une compétition d'un jeu de stratégie contre des joueurs humains. En 1990, il gagna le droit de participer au championnat du monde (humain) en remportant la seconde place derrière Marion Tinsley dans le championnat national américain. Les fédérations de jeu de dames anglaises (l'American Checker Federation (en) et la English Draughts Association (en)) étaient d'abord opposées à la participation d'un ordinateur à des compétitions humaines, mais lorsque Tinsley renonça à son titre en signe de protestation, l'ACF et la EDA créèrent un nouveau titre, Man vs. Machine World Championship (Championnat du Monde Homme contre Machine), et la rencontre put avoir lieu. Tinsley la remporta par quatre victoires à deux, avec 33 nulles.

En 1994, une nouvelle rencontre vit Chinook déclaré Champion du monde après six parties nulles, Tinsley ayant déclaré forfait à la suite de la dégradation de son état de santé. Ainsi, Chinook ne réussit en fait jamais à vaincre celui qui est généralement considéré comme le meilleur joueur de tous les temps.

En 1995, Chinook défendit son titre contre Don Lafferty (en) dans une rencontre en 32 parties (score final 1–0 et 31 nulles) . Après cette rencontre, Jonathan Schaeffer décida de ne plus laisser Chinook participer à des compétitions, et se lança dans le projet de la résolution du jeu de checkers.

Algorithme

L'algorithme de jeu de Chinook contient un recueil d'ouvertures, formé de coups joués au début de parties de grands maîtres ; un algorithme d'exploration de variantes à grande profondeur ; une fonction d'évaluation de la qualité des coups et enfin une base de données de positions finales formée de toutes les positions ayant huit pièces ou moins. La fonction d'évaluation, optimisée à la main, est une combinaison linéaire de divers facteurs de la position, comme le compte des pièces et des dames, l'existence de chemins de promotion non gardés, ou le blocage de certaines pièces. Toutes les connaissances de Chinook ont été programmées par ses créateurs, et non apprises par des méthodes d'intelligence artificielle.

Calendrier de la progression de Chinook vers la solution du jeu de dames

• 1997 - Jonathan Schaeffer publie un livre sur Chinook intitulé One Jump Ahead: Challenging Human Supremacy in Checkers (Un saut d'avance : contester la suprématie humaine aux dames) ; une mise à jour de ce livre fut publiée en novembre 2008, avec le nouveau titre One Jump Ahead: Computer perfection at Checkers.
• 24 mai 2003 - Chinook complète sa base de données pour les positions à 5 pièces de chaque côté .
• 2 août 2004 - L'ouverture appelée White Doctor (le médecin blanc, 10–14 22–18 12–16) est démontrée conduire à la nullité.
• 18 janvier 2006 - L'ouverture 09–13 21–17 05–09 conduit à la nullité.
• 18 avril 2006 - L'ouverture 09–13 22–17 13–22 conduit à la nullité.
• 19 juillet 2007 - La revue Science publie l'article de l'équipe de Schaeffer intitulé Checkers Is Solved, présentant leur démonstration de ce que le meilleur résultat possible si les deux joueurs jouent optimalement est une partie nulle.

Liens externes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Chinook (draughts player) » (voir la liste des auteurs).
• (en) Site consacré à Chinook
• (en) Informations techniques sur Chinook
• Delahaye JP, « La fin des dames anglaises ? », Interstices.info, 27/10/2009