Programming a Computer for Playing Chess

Programming a Computer for Playing Chess est l'article fondateur des échecs en informatique, écrit par Claude Shannon en 1949. Tous les programmes d'échecs passés et présents sont inspirés de ce papier. Shannon présente sa stratégie de type minimax basée sur des fonctions d'évaluations. Il met en avant deux types de recherches des coups à jouer (type A et type B) et constate l'impossibilité d'utiliser une recherche par force brute, notamment à cause de la capacité de calcul limitée des ordinateurs de l'époque. La recherche de type B, à la manière d'un humain, se concentre sur les positions et coups les plus prometteurs.

Dans son article, Shannon, soulève l'impossibilité de calculer toutes les positions et coups possibles. Il calcule un nombre de coups potentiels ayant un sens durant une partie, nombre connu sous l'expression « nombre de Shannon ».

L'article de Shannon fait plus que résumer ce que doit être une machine qui peut jouer aux échecs. Il soulève les défis théoriques à résoudre, informe un large public de la possibilité de créer une machine capable de jouer aux échecs et impulse les recherches d'une génération de programmateurs d’échecs. Claude Shannon est le premier à publier une description cohérente de l’application du minimax au jeu d’échecs et cet article fait de lui l'un des candidats au titre de fondateur des programmes d'échecs, au même titre qu'Alan Turing avec son programme de 1948 intitulé Turochamp et que Konrad Zuse grâce à son langage de programmation intitulé Plankalkül et les routines informatiques d'échecs qu'il a écrites de 1941 à 1945.

Parallèlement à partir de 1949, Shannon construit un automate composé uniquement de 150 relais électromécaniques qui permet de jouer aux échecs.

Contexte

Claude Shannon.

Claude Shannon, né le 30 avril 1916 et mort le 24 février 2001, est un mathématicien, cryptographe et ingénieur en électrotechnique américain. Il est fondateur en 1937 de la théorie de la conception des circuits numériques, lorsqu'à l'âge de 21 ans il écrit, alors qu'il passe sa maîrise au Massachusetts Institute of Technology (MIT), sa thèse démontrant que les applications de l'algèbre de Boole dans le domaine de l'électricité permettent de construire n'importe quelle relation logique ou numérique. Shannon contribue également dans le domaine de la cryptanalyse pour la défense nationale américaine durant la Seconde Guerre mondiale, notamment grâce à ses travaux de décryptage et de sécurisation des télécommunications. Il est aussi le fondateur de la théorie de l'information, avec un article repère intitulé A Mathematical Theory of Communication qu'il publie en 1948.

Shannon, qui travaille chez Bell Laboratories depuis 1941, approfondit les travaux effectués par Turing sur le sujet des échecs (Turochamp). Lors de l'IRE Convention qui se tient en mars 1949 à New York, Shannon présente un article intitulé Programming a Computer for Playing Chess, ayant pour sujet un ordinateur qui permet de jouer aux échecs. L'article est par la suite publié en février 1950 dans une version épurée dans le magazine Scientific American n^o 182, puis dans une version détaillée en mars 1950 dans le magazine Philosophical Magazine n^o 314.

Généralités

Shannon n'écrit pas de programme mais met en avant des techniques et des algorithmes qui forment la base des programmes d'échecs créés depuis-là. Il admet que les échecs sont un problème intéressant et un test décisif des capacités de systèmes de traitement de l'information. Il décrit l'analyse de la stratégie des machines comme un problème de forme réelle sans la complexité du monde réel. Selon lui, bien que ceci n’ait peut-être aucune importance pratique, savoir si un ordinateur peut jouer aux échecs revêt un intérêt théorique et il est à espérer qu'une solution satisfaisante à ce problème puisse agir comme un effet de levier dans la résolution d'autres problématiques de nature similaire, mais de plus grande importance.

Selon Shannon, le but des échecs est clair et distinct : faire échec et mat. En outre, le jeu utilise un système de règles simples qui n'inclut aucun élément de chance ou de hasard, même si ce simple but, avec ces règles simples est difficile à approcher. Il considère le match homme-machine au jeu d'échecs comme une opposition loyale.

Il ne pense pas que la victoire de l'ordinateur sur l'homme au jeu d'échecs est inévitable, mais relève cependant quatre avantages pour chaque opposant. il considère qu'un ordinateur est très rapide pour réaliser des calculs, ne se trompe jamais à moins qu'une erreur ne soit introduite dans le programme, n'est jamais lassé ou fatigué et analyse pleinement chaque position ou tous les coups envisageables, et ne joue pas avec un registre émotionnel ou ne pêche pas par excès de confiance dans des situations a priori gagnantes qui pourraient être gaspillées ou transformées en des situations difficiles qui pourraient nécessiter un sauvetage. Shannon considère que de son côté, l'opposant humain possède un esprit flexible qui est capable de changer de raisonnement ou de vitesse pour résoudre un problème plutôt que d'appliquer uniquement une série de règles simples. Il remarque qu'il est également doué de la raison, de l'imagination et de la capacité d'apprendre.

L'article décrit comment une machine ou un ordinateur peut jouer une partie d'échecs raisonnable. Il y présente la manière dont un programme peut se représenter un échiquier, évaluer une position et générer les prochains déplacements.

Recherches

Shannon considère deux types de recherche afin d'évaluer le choix des coups à jouer. Il oppose la recherche et l'approche de la connaissance aux machines d’échecs. La première qu'il nomme « Type A » est une recherche par force brute de toutes les variations. Un programme de recherche en profondeur analyse toutes les séquences de mouvements possibles et leurs conséquences avec la profondeur de coups désirée et assigne une valeur à chaque position finale. L’algorithme minimax choisit le meilleur coup possible en fonction de ce que lui permet son opposant. L’unique connaissance liée aux échecs est contenue dans la fonction d’évaluation qui détermine la valeur associée à une position. La seconde méthode de recherche, qu'il appelle « Type B », est une recherche sélective sur les branches importantes uniquement. Un matériel basé sur la recherche imite le comportement d’un joueur d’échecs débutant, qui, connaissant uniquement les mouvements, tâtonne systématiquement jusqu’à un moment clef où il peut sélectionner le meilleur coup à jouer.

Shannon estime les stratégies de type A non-viables pour des raisons de complexité de calculs numériques et démontre l'impossibilité d'envisager toutes les positions : Il y a environ trente coups possibles pour chaque position, et en prenant en compte une profondeur de trois coups, pour chacune des deux couleurs, le calcul prendrait seize minutes, avec un système capable d'évaluer un million de positions à la seconde (en comparaison, Deep Blue peut évaluer 200 millions de positions par seconde). En outre, Shannon remarque que les stratégies de type A sont trop simplistes, en ignorant l'aspect de la recherche quiescente (en) (une recherche heuristique intelligente suit les mouvements les plus prometteurs sur une plus grande profondeur, tout en écartant les coups peu prometteurs ou tranquilles).

Shannon suggère que les stratégies de type B puissent utiliser deux approches. Une sorte de recherche quiescente peut être utilisée, ou l'évaluation de seulement quelques coups pour chaque position, en ignorant tous les coups sauf ceux identifiés comme bons (méthode appelée élagage).

Fonctions d'évaluations

John von Neumann.

Shannon expose son processus de type minimax présenté pour la première fois quelques années auparavant par von Neumann, basé sur la fonction d'évaluation (en) statique de la position donnée d'une pièce d'échecs, pour permettre à l'ordinateur de décider du coup à jouer. Il donne l'exemple grossier d'une fonction d'évaluation dans laquelle la valeur des positions noires sont soustraites à celles des blanches. Le matériel est estimé en fonction de l'habituelle valeur relative des pièces (1 points pour un pion, 3 points pour un cavalier ou un fou, 5 pour une tour et 9 points pour une dame ou un roi). Il considère des facteurs positionnels comme les pions doublés, les pions arriérés ou les pions isolés. La mobilité est aussi un facteur qui permet d'ajouter 0,1 point à chaque mouvement autorisé. Il considère également qu'échec et mat est la capture du roi et lui donne la valeur artificielle de 200 points.

Suggestions

Shannon offre également quelques suggestions et commentaires supplémentaires. Comme Charles Babbage, il préconise l'usage d'éléments statistiques afin de choisir aléatoirement parmi les coups les plus sûrs. Il conseille en outre l'usage d'une bibliothèque d'ouvertures avec un choix aléatoire qui a pour effet d'amener de la variété.

Nombre de Shannon

Dans son article, Shannon soulève l'impossibilité de calculer toutes les positions et coups possibles. Il calcule un nombre de coups potentiels ayant un sens durant une partie, nombre connu sous l'expression « nombre de Shannon ». Le nombre de Shannon, soit 10¹²⁰, est l'estimation de la complexité de l'arbre de jeu d'échecs, c'est-à-dire du nombre de parties différentes, ayant un sens échiquéen possibles.

Postérité

L'article de Shannon est plus qu’un simple résumé de ce que doit être une machine qui peut jouer aux échecs. Il met en avant les problèmes théoriques non résolus et a alerté un large public sur la possibilité de créer une machine capable de jouer aux échecs et a également inspiré une génération de programmateurs d’échecs. Claude Shannon est le premier à publier une description cohérente de l’application du minimax au jeu d’échecs et cet article fait de lui l'un des candidats au titre de fondateur des programmes d'échecs, au même titre qu'Alan Turing avec son programme de 1948 intitulé Turochamp et que Konrad Zuse grâce à son langage de programmation intitulé Plankalkül et les routines informatiques d'échecs qu'il écrivit de 1941 à 1945. Tous les programmes d'échecs passés et présents se sont basés sur les techniques décrites par Claude Shannon.^{[réf. nécessaire]}

Parallèlement à partir de 1949, Shannon construisit un automate composé uniquement de 150 relais électromécaniques. La machine était conçue pour permettre l'essai de plusieurs méthodes de programmation. Elle peut déplacer six pièces, joue son coup en 10 à 50 secondes, et les choix qu'elle fait comportent un aspect aléatoire qui lui permet de ne pas tout le temps jouer le même coup en fonction de la même situation. Durant la période où Shannon cherche des idées qui peuvent le mener à réaliser la machine, il passe tellement de temps à jouer aux échecs chez Bell Laboratories qu'au moins un de ses supérieurs était « plutôt » inquiet.

Chez Christie's, 20 Rockefeller Plaza, Manhattan (New York).

Lors d'une vente aux enchères intitulée The Origins of Cyberspace, organisée en février 2003 par Christie's à la Rockefeller Plaza à New York, les pages de l'article complet Programming a Computer for Playing Chess du Philosophical Magazine de mars 1950, ont été vendues 960 dollars.

Publication

• Lecture : Programming a Computer for Playing Chess, IRE Convention, mars 1949 à New York ;
• Version épurée : (en) Claude Shannon, « Programming a Computer for Playing Chess », Scientific American, vol. 182, n^o 2,‎ février 1950 (lire en ligne) ;
• Version détaillée : (en) Claude E. Shannon, « XXII. Programming a computer for playing chess », The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, vol. 41, n^o 314,‎ mars 1950, p. 256–275 (ISSN 1941-5982 et 1941-5990, DOI 10.1080/14786445008521796, lire en ligne, consulté le 4 mai 2019)

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Claude Shannon » (voir la liste des auteurs).

Bibliographie

 : document utilisé comme source pour la rédaction de cet article.

• (en) George W. Atkinson, Chess and Machine Intuition, Intellect Books, 1998, 175 p. (ISBN 978-1-871516-44-9, lire en ligne).  ;
• (en) S. Barry Cooper et Jan van Leeuwen, Alan Turing : His Work and Impact, Waltham, MA/Kidlington, Oxford, Elsevier Science, 2013, 914 p. (ISBN 978-0-12-386980-7, lire en ligne).  ;
• (en) Gary M. Danelishen, The Final Theory of Chess, Philidor Press, 2008, 385 p. (ISBN 978-0-9815677-0-9, lire en ligne).  ;
• (en) Subrata Dasgupta, It Began with Babbage : The Genesis of Computer Science, Oxford, Oxford University Press, 2014, 328 p. (ISBN 978-0-19-930941-2, lire en ligne).  ;
• (en) Hamid Reza Ekbia, Artificial Dreams : The Quest for Non-biological Intelligence, Cambridge University Press, 2008 (ISBN 978-0-521-87867-8, lire en ligne).  ;
• (en) William Poundstone, Fortune's Formula : The Untold Story of the Scientific Betting System That Beat the Casinos and Wall Street, Macmillan, 2006, 386 p. (ISBN 978-0-8090-4599-0, lire en ligne).  ;
• (en) Claude Elwood Shannon, Neil James Alexander Sloane et Aaron D. Wyner, Claude Elwood Shannon : Collected papers, IEEE Press, 1993, 924 p. (ISBN 978-0-7803-0434-5, lire en ligne).  ;
• (en) Nate Silver, The Signal and the Noise : Why So Many Predictions Fail - But Some Don't, Penguin Press HC, 2012, 534 p. (ISBN 978-1-59420-411-1, lire en ligne).  ;
• (en) Friedrich von Borries, Steffen P. Walz et Matthias Böttger, Space Time Play : Computer Games, Architecture and Urbanism: The Next Level, Bäsel, Springer Science & Business Media, 2007, 495 p. (ISBN 978-3-7643-8414-2, lire en ligne). .