Programme d'échecs de Dietrich Prinz
Vous lisez un « bon article » labellisé en 2017.
Le programme d'échecs de Dietrich Prinz (parfois appelé Robot Chess ou Mate-in-two) fonctionne pour la première fois en sur le Ferranti Mark I de l'université de Manchester, premier ordinateur à usage commercial. Précurseur de l'intelligence artificielle, c'est le premier programme informatique de jeu d'échecs à fonctionner sur un ordinateur, seulement précédé par le programme d'échecs théorique d'Alan Turing, intitulé Turochamp.
| Développeur |
Dietrich Prinz (en) |
|---|---|
| Réalisateur |
Dietrich Prinz |
| Début du projet |
1949 |
|---|---|
| Date de sortie |
Novembre 1951 |
| Genre | |
|---|---|
| Plate-forme |
Dans le cadre d'une collaboration entre Ferranti et l'université de Manchester, le pionnier de l'informatique britannique Dietrich Prinz participe à la création du Ferranti Mark I et de ses prototypes, le SSEM et le Manchester Mark I. Prinz développe son programme sur le Ferranti Mark I à partir de 1949, programme qui est fonctionnel en . Les capacités limitées de l'appareil ne permettent pas de jouer une partie d'échecs classique contre l'ordinateur et obligent Prinz à mettre en œuvre seulement une étude de la finale, en particulier les mats en deux coups. En outre, les règles sont considérablement simplifiées, occultant le roque, les mouvements de deux pas du pion, la prise en passant et la promotion, ou ne faisant pas la distinction entre mat et pat. Prinz choisit une recherche exhaustive, ce qui exige l'évaluation de milliers de coups possibles durant chaque partie jouée. Le programme, qui est nettement moins rapide qu'un humain, nécessite près de quinze minutes pour chaque coup. Les transferts entre la mémoire magnétique et la mémoire électronique, ainsi que les tests sont les principales causes de cette lenteur.
Les observateurs relèvent l'aspect rudimentaire de la programmation, la lenteur du programme, mais notent la valeur historique de la réalisation de Prinz. Ce dernier ne développe plus jamais de programme d'échecs, notamment en raison de l'augmentation de sa masse de travail chez Ferranti.
Genèse
modifier
Dietrich Prinz est un pionnier de l'informatique d'origine allemande, formé à l'université Humboldt de Berlin où il a suivi les cours de Max Planck et d'Albert Einstein. Sa condition juive le pousse à fuir le Troisième Reich en 1938, puis il s'installe en Angleterre[1]. Il adopte la nationalité britannique en 1947[2]. Communément appelé par ses initiales DP à l'université de Manchester[3], Prinz est une sorte de geek avant même l'invention du terme, et un « disciple » de Turing[2].
Les avancées dans la recherche sur les radars et le matériel utilisé pour la cryptologie pendant la Seconde Guerre mondiale ouvrent une brèche dans le domaine de l'informatique et facilitent le développement des ordinateurs à la fin des années 1940. Après la guerre, l'activité de l'entreprise Ferranti commence à diminuer, faute de commandes du Ministère de la défense du Royaume-Uni. Eric Grundy, un responsable, met alors en place une équipe qui a pour but d'étudier les utilisations potentielles des ordinateurs. En 1947, il nomme Dietrich Prinz responsable de l'équipe de développement informatique. Prinz travaille en collaboration avec l'université de Manchester au développement d’ordinateurs. Ferranti a déjà travaillé avec l'université dans les années 1930 à la fabrication de tubes électroniques. Après deux mois de tests, le Small-Scale Experimental Machine (SSEM, surnommé baby) fonctionne enfin[4]. Dès qu'il démontre la faisabilité de sa conception, un projet est lancé afin d'en faire un ordinateur plus convivial : le Manchester Mark I, qui devient rapidement le prototype du Ferranti Mark I, le premier ordinateur généraliste commercialisé[5]. Il est livré en à l'université. Alan Turing et son collègue Cicely Popplewell travaillent environ six mois notamment sur l'interface utilisateur, puis l'ordinateur est officiellement finalisé en [4].
Prinz apprend la programmation sur le Mark I par l'intermédiaire de séminaires dirigés par Turing et Popplewell[6]. Il voit dans la programmation d'échecs « un indice sur les méthodes qui pourraient être utilisées pour traiter les problèmes structurels ou logistiques se produisant dans d'autres domaines, par le biais d'ordinateurs électroniques »[6]. Son intérêt pour les programmes informatiques d'échecs est probablement influencé par Alan Turing[7]. Prinz fait alors fonctionner sur le Mark I son programme d'échecs qu'il développe depuis 1949[8],[4]. Rapidement, Turing et Prinz concluent qu'aucun programme sur le Mark I ne peut jouer une partie d'échecs complète. Ils décident alors de concentrer leurs efforts sur la finale des parties, en particulier les mats en deux coups[3]. Prinz s'inspire probablement, comme Christopher Strachey et Donald Michie, d'un article intitulé « A Theory of Chess and Noughts and Crosses »[6] paru en 1950 dans le périodique Penguin Science News écrit par le scientifique du National Physical Laboratory (NPL) Donald Davies[9]. Il aurait également connu l'existence de l'El Ajedrecista, qui permet de jouer aux échecs la finale roi et tour contre roi seul, et s'en serait inspiré pour réaliser son programme[10].
En , son programme sur le Mark I réussit à résoudre les mats en deux coups[11].
Fonctionnement
modifierLes capacités techniques limitées du Ferranti Mark I n'imposent pas seulement à Prinz de réduire le jeu aux mats en deux coups. Afin de permettre l'exécution des tâches dans le délai le plus court possible, quelques restrictions sont imposées à la manière dont les règles sont expliquées à la machine. Notamment, aucune distinction n'est faite entre mat et pat, le roque n'est pas autorisé, ni les mouvements de deux pas du pion, ni la prise en passant, ni la promotion[11],[12].
Chaque partie jouée par le programme exige l'évaluation de plusieurs milliers de coups, soit une recherche par force brute, contrairement à Turochamp qui effectue moins de recherches, car il est fondé sur une recherche de type heuristique[6]. Prinz a pris cette option parce qu'un jeu aussi simplifié n'a nul besoin d'une recherche heuristique[2].
Le programme et la position initiale des pièces sont fournis à la machine par l'intermédiaire d'une bande perforée et transférés dans sa mémoire magnétique. Une routine initiale transfère les données dans la mémoire électronique, puis l'ordinateur démarre les calculs[11]. Le programme examine d'abord toutes les cases reliées à celle du roi par un mouvement de cavalier afin de savoir si ce dernier figure sur le plateau, quelles cases sont alors occupées, quelle pièce est à côté et finalement si c'est bien un cavalier. Cette série de vérifications est répétée pour chaque pièce[12]. Le programme intègre une routine calculant le prochain coup possible, une routine chargée de vérifier la légalité du mouvement et plusieurs séquences dont le rôle est d'enregistrer le mouvement et la position obtenue. Toutes ces routines sont chapeautées par une routine maîtresse, qui synthétise la structure du problème dans son ensemble et s'assure que les sous-routines entrent dans la bonne séquence. Les techniques de programmation sont rudimentaires ; la vitesse d'exécution du programme nécessite des perfectionnements et améliorations[11]. Le programme met plus de temps à choisir son coup qu'un joueur humain[8]. Par exemple, un simple coup demande quinze minutes à l'ordinateur pour imprimer la solution[11].
Une grande partie du temps utilisé par le programme est allouée à des tests d'autocontrôle. L'autre tâche consommatrice de temps est le transfert magnétique des données entre le stockage magnétique et électronique, comme celui des sous-programmes et des données concernant les positions et les déplacements. Neuf de ces transferts de données sont effectués à chaque coup[11],[2]. En comparaison, le temps nécessaire pour réaliser les calculs des déplacements est d'une importance mineure, même si tous les coups possibles comme ceux impossibles sont évalués. Les positions erronées ou les déplacements interdits sont rapidement écartés par le programme et ne représentent qu'une petite partie du temps de calcul. Lors du premier problème d'échecs de l'histoire proposé au programme, un simple déplacement oblige le programme à vérifier 450 mouvements possibles, dont 100 sont illégaux. Le programme met environ deux secondes pour décider chacun de ses coups[11].
Le programme poursuit son examen jusqu'à ce qu'une solution soit trouvée[13]. Il imprime chaque coup des blancs testé, et annonce « mate » une fois qu'un coup gagnant est trouvé[11]. Il ne comporte aucune interface graphique[14], le résultat étant imprimé sur du papier[11].
Premier problème d'échecs de l'histoire résolu par le programme
modifier| a | b | c | d | e | f | g | h | ||
| 8 |        | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
(La numérotation des cases était différente dans le programme d'échecs de Dietrich Prinz.)
Le programme doit trouver un coup pour les blancs permettant de faire échec et mat au coup suivant quel que soit le choix des noirs[11]. Les cases sont anormalement numérotées, de gauche à droite et de 11 à 18 pour la ligne du bas, puis de 21 à 28 pour la deuxième, et ainsi de suite, jusqu'à la ligne la plus haute (de 81 à 88). La case 68 est donc en ligne 6 et en colonne 8 (h6). Le programme imprime toutes les positions testées, puis annonce « mate » lorsqu'il trouve la solution. Dans le schéma à la droite, c'est Rook in 68 (« Tour en 68 »), c'est-à-dire Th6. Le programme a préalablement essayé dans l'ordre les coups P78 (gxh7), T17 (Tg1), T16 (Tf1), T15 (Te1), T14 (Td1), T13 (Tc1), T12 (Tb1), T11 (Ta1), T28 (Th2), T38 (Th3), T48 (Th4), T58 (Th5)[11],[2]. Ce problème est communément attribué, sans preuve aucune, au prodige américain Paul Morphy (1837-1884), soit bien avant la création du programme[15].
Postérité
modifierLe programme d'échecs de Dietrich Prinz est unanimement désigné comme le premier programme de jeu à fonctionner sur un ordinateur multi-usage, en particulier sur le premier ordinateur commercial, le Ferranti Mark I, et figure notablement dans l'histoire du jeu d'échecs sur ordinateur[6],[2],[3],[14]. À ce titre, il figure également dans la genèse du jeu vidéo où il est cité dans les ouvrages traitant de l'histoire de ce média, comme le premier jeu fonctionnel sur un ordinateur[14]. Il figure également parmi les précurseurs du développement de l'intelligence artificielle[13]. Jack Copeland, qui a écrit de nombreux ouvrages sur la vie et l'œuvre d'Alan Turing, qualifie le programme de « moment important, de Big Bang des échecs sur ordinateur »[2]. Si le programme de Prinz résout les mats en deux coups à partir de , il faut cependant attendre 1958 et le programme proposé par l'Américain Alex Bernstein sur IBM 704, pour pouvoir jouer à une partie d'échecs complète contre un ordinateur[10]. Selon Copeland, malgré la simplicité du programme et le choix de la recherche par force brute, « l'importance de ce que Prinz a accompli est comparable au premier vol court des frères Wright »[2].
Prinz publie en 1952 tous les détails de son programme dans l'article « Robot Chess » du magazine Research (no 5, p. 261-266)[2]. L'article est réédité en 1988 dans le livre Computer Chess Compendium (p. 213-219)[16].
B. V. Bowden décrit le programme dans son ouvrage de 1953 intitulé Faster Than Thought: Symposium on Digital Computing Machines. Pour lui, il ne peut que servir d'exemple grossier de la vitesse qu'un programme peut atteindre et fait la démonstration de la nécessité d'améliorer matériel et programmation, pour réaliser une machine capable de joueur aux échecs contre un humain[11]. Il considère que le programme peut être amélioré sur plusieurs aspects, en particulier au niveau de l'utilisation de la mémoire électronique. De meilleures techniques de programmation peuvent réduire le temps de calcul en diminuant les échanges de données entre les espaces de stockage[11]. Il critique sévèrement le programme en ajoutant que si cette méthode rudimentaire de programmation est la seule à disposition, la compétition dans des conditions raisonnables entre la machine et l'être humain est peu réaliste. Il nuance cependant sa position en rappelant que le programme a réussi à résoudre un problème en seulement quelques semaines d'apprentissage, ce qui est un progrès plutôt raisonnable pour un joueur débutant[11]. En 1972, Alex Bell évoque également le programme dans son ouvrage traitant de l'histoire des programmes informatiques d'échecs intitulé Games Playing with Computers. Comme Bowden, il juge le programme trop rudimentaire pour rivaliser avec l'humain dans des conditions raisonnables[12]. Selon Copeland, Turing aurait probablement pu améliorer le code source du programme, mais il ne le fait pas : il sait qu'une recherche par force brute, utilisée seule, n'a aucun avenir et il n'y porte que peu d'intérêt[2].
Prinz rapporte que le programme, une fois devenu fonctionnel, n'est plus jamais utilisé. Il ajoute que la quantité de travail ayant augmenté à cause du plus grand nombre d'ordinateurs, il n'a pu s'affairer à des tâches mineures comme la programmation de jeux d'échecs. De plus, un problème d'échecs très légèrement plus compliqué aurait, selon lui, probablement nécessité des heures de calculs à un ordinateur[2]. Par la suite, Prinz écrit un manuel pour le Ferranti Mark I, un modèle de clarté, à l'opposé de ceux écrits par Turing, tout en continuant à travailler à la musique sur ordinateur[2].
Références
modifier- (de) Detlef Borchers, « Vor 50 Jahren fing alles an: das erste "Elektronenhirn" in Deutschland », sur Heise Online, .
- B. Jack Copeland , Jonathan Bowen et Mark Sprevak Robin Wilson, The Prinz Chess Program, Brute-force Chess, p. 339-342.
- S. Barry Cooper J. van Leeuwen, Turing's work on "Thinking Machines": The Fourth facet of a genius, p. 875.
- (en) « Ferranti Mark 1 Computer », sur Museum of Science and Industry.
- (en) R.B.E. Napper, « Introduction to the Mark 1 », sur The University of Manchester.
- B. Jack Copeland Alan Mathison Turing, Chapter 16: The First Working Chess Programme, p. 564-565.
- (en) « Computer History Museum - Opening Moves: Origins of Computer Chess - First Tests », sur Computer History Museum.
- (en) Thomas Dreher, « IASLonline NetArt: Theory », sur IASLonline.
- « Computer Pioneers - Christopher Strachey », sur IEEE Computer History (consulté le ).
- Julian Alvarez et Damien Djaouti, « Arcade : Les Pionniers du jeu vidéo » (Mook), Pix'n Love, Éditions Pix'n Love, no 11, , p. 32-43 (ISBN 9782918272106).
- Bowden, p. 286-287.
- Alex G. Bell, Chapter 5: Some Chess Programs.
- (en) Jack Copeland, « What is Artificial Intelligence? », sur Alanturing.net, .
- (en) Rachel Kowert et Thorsten Quandt, The Video Game Debate : Unravelling the Physical, Social, and Psychological Effects of Video Games, Routledge, , 204 p. (ISBN 978-1-317-56717-2 et 131756717X, lire en ligne), p. 3.
- CD-ROM Chessbase Monograph Paul Morphy, Genius and Myth - Chessbase.
- (en) David Levy, Computer chess compendium, New York, Springer New York, , 440 p. (ISBN 978-1-4757-1968-0, lire en ligne), p. 213-219.
Bibliographie
modifier- (en) Alex G. Bell, Games Playing with Computers, Allen and Unwin, , 204 p.
- (en) B. V. Bowden, Faster Than Thought : Symposium on Digital Computing Machines, Sir Isaac Pitman and Sons, Ltd, , 416 p.
- (en) B. Jack Copeland et Alan Mathison Turing, The Essential Turing : Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Oxford University Press, , 613 p. (ISBN 978-0-19-825079-1 et 0198250797, lire en ligne).
- (en) B. Jack Copeland, Jonathan Bowen, Mark Sprevak et Robin Wilson, The Turing Guide, Oxford University Press, , 400 p. (ISBN 978-0-19-106500-2, lire en ligne).
- (en) S. Barry Cooper et J. van Leeuwen, Alan Turing : His Work and Impact, Elsevier, , 944 p. (ISBN 978-0-12-387012-4, lire en ligne).
