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é.

Pour les articles homonymes, voir Chinook.

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[1].

En 1995, Chinook défendit son titre contre Don Lafferty (en) dans une rencontre en 32 parties (score final 1–0 et 31 nulles) [2]. 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)[3] ; une mise à jour de ce livre fut publiée en , avec le nouveau titre One Jump Ahead: Computer perfection at Checkers.
  • - Chinook complète sa base de données pour les positions à 5 pièces de chaque côté [4].
  • - L'ouverture appelée White Doctor (le médecin blanc, 10–14 22–18 12–16) est démontrée conduire à la nullité[5].
  • - L'ouverture 09–13 21–17 05–09 conduit à la nullité.
  • - L'ouverture 09–13 22–17 13–22 conduit à la nullité.
  • - 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[6],[7].

Notes et références
  1. (en) 1994 Chinook-Tinsley checkers match
  2. (en)Details of the 1995 Man vs. Machine World Championship
  3. (en) Jonathan Schaeffer, One Jump Ahead : Challenging Human Supremacy in Checkers, Springer, , 496 p. (ISBN 978-0-387-94930-7, lire en ligne)
  4. (en)site de Chinook, 24 juin 2003
  5. (en) site de Chinook, 30 septembre 2004
  6. (en) J. Schaeffer, N. Burch, Y. Bjornsson, A. Kishimoto, M. Muller, R. Lake, P. Lu et S. Sutphen, « Checkers is Solved », Science, vol. 317, no 5844,‎ , p. 1518–22 (PMID 17641166, DOI 10.1126/science.1144079)
  7. Delahaye JP, « La fin des dames anglaises ? », Interstices.info, 27/10/2009

Liens externes
  • Portail des jeux
  • Portail de l’informatique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.