Ouvrir le menu principal

Turochamp

programme d'échecs

Wikipédia:Bons articles Vous lisez un « bon article ».

Turochamp est un programme d'échecs et le premier jeu développé pour un ordinateur, développé en 1948 par Alan Turing et D. G. Champernowne. Le duo écrit les algorithmes alors qu'il n'a pas d'ordinateur, puis Turing tente d'adapter le programme sur Ferranti Mark I, mais l'écriture reste inachevée. Le programme utilise notamment d'importantes méthodes d'évaluation et des concepts de sélectivité. Toutefois, son fonctionnement n'est pas basé sur une recherche exhaustive, mais plutôt sur une orientation de type heuristique. En 1952, un ami de Turing joue contre Turochamp et gagne la partie, alors que Turing simule à la main les calculs normalement pris en charge par l'ordinateur.

À l'occasion des 100 ans de la naissance d'Alan Turing, en 2012, le programme est reconstruit par des experts informatiques, et Garry Kasparov, l'un des meilleurs joueurs de l'histoire du jeu d'échecs, joue une partie contre lui, qu'il gagne facilement tout en reconnaissant le contexte historique et la qualité de Turochamp.

Turochamp reste le premier programme d'échecs, conçu avant même les premiers ordinateurs. Toutefois, en , Dietrich Prinz, qui a travaillé pour Ferranti, développe le premier programme d'échecs fonctionnant sur un ordinateur, le Ferranti Mark I du Massachusetts Institute of Technology (MIT).

Histoire du développementModifier

 
Alan Turing à l'âge de 16 ans.

Alan Turing est un mathématicien britannique né en 1912, célèbre pour sa machine de Turing dont il pose les bases dès 1936, sa participation dans le décryptage de la machine Enigma durant la Seconde Guerre mondiale et ses travaux qui fondent scientifiquement l'informatique[1]. En 1946, Turing rédige un rapport pour le National Physical Laboratory (NPL), intitulé Proposed Electronic calculator, dans lequel il décrit quelques problèmes qu’il prévoit de soumettre à l'ordinateur ACE, dont l’un d’entre eux est la réalisation d'un programme permettant de jouer aux échecs. En 1947, il fait une lecture à la London Mathematical Society dans laquelle il présente l’idée qu’une machine programmée pour jouer aux échecs pourrait apprendre seule et acquérir sa propre expérience. Par la suite en 1948, il rédige un nouveau rapport pour le NPL, intitulé Intelligent Machinery, qui suggère une forme d’imitation du jeu (s’apparentant au test de Turing) qu deviendra célèbre à travers son article intitulé Computing machinery and intelligence parut en 1950[2].

À la fin de l'été 1948, Turing et le statisticien économique D. G. Champernowne, son ami et collègue au King's College de Cambridge, conçoivent un système de règles théoriques visant à déterminer les coups suivants d'une partie d'échecs. Ils développent donc un programme d'échecs connu sous le titre de Turochamp, pour un ordinateur n'existant pas encore[3]. Le nom du programme est fondé sur leur patronyme[2]. Champernowne précise que sa femme a joué une partie d'échecs contre le programme et a perdu la partie[3]. L'algorithme de Turing, seulement posé sur papier, se voit donner le surnom de paper machine[4].

Turochamp met en œuvre les règles de bases édictées par Turing et Champernowne, permettant de réaliser les meilleurs coups. Le programme utilise notamment d'importantes méthodes d'évaluation et des concepts de sélectivité[5]. Toutefois, son fonctionnement n'est pas basé sur une recherche exhaustive, mais plutôt sur une orientation de type heuristique[3]. Il prévoit uniquement les deux coups suivants d'une partie en calculant des centaines de coups potentiels[6] et peut normalement terminer une partie[3],[7]. Turochamp simule tous les mouvements autorisés en fonction de la situation jusqu'aux positions mortes, puis calcule toutes les actions possibles lors du coup suivant de son adversaire. Pour évaluer les positions et les décisions à prendre, Turing et Champernowne mettent au point plusieurs critères comme la mobilité des pièces et leurs déplacements possibles, la sécurité des pièces ainsi que la mobilité et la sécurité du roi, le roque, la structure de pions, la menace d'échec et mat et la valeur de chaque pièce. Chaque critère attribue des points que le duo a défini en fonction du coup, ce qui permet à Turochamp de décider du meilleur coup à jouer (par exemple : un pion vaut 1 point, un cavalier en vaut 3, un fou 3,5, une tour 5 et la reine 10 ; d'autres points sont attribués si la tour, le fou ou le cavalier sont défendus, 1 point ou un demi-point sont attribués en fonction de la menace échec ou mat ; et des points sont retirés en fonction de la vulnérabilité du roi[8]). Champernowne précise que la plus grande part de leur attention s'est focalisée sur la décision du coup à suivre. Turing admet que ces règles produisent un jeu d'échecs d'un niveau faible, à la mesure de son niveau qu'il juge moyen[3],[9],[8].

Turing essaye de faire fonctionner le jeu sur l’ordinateur Ferranti Mark I, mais la plate-forme manque de puissance et ne peut exécuter le programme. De plus, le code est d'une trop grande complexité[10]. L'écriture du programme reste inachevée[11],[3]. Jack Copeland, professeur de philosophie à l'université de Canterbury en Nouvelle-Zélande et auteur d'un livre sur Alan Turing, précise que cela ne dérange pas Turing, tant il est convaincu du fonctionnement futur de son programme[12]. Turochamp perd une partie, qui fut enregistrée, contre un collègue de Turing dénommé Alick Glennie. Turing réalise à la main les opérations normalement calculées par l'ordinateur, ce qui requiert près d'une demi-heure pour déterminer chaque coup[11],[3].

En 1953, Turing écrit un article publié dans l'ouvrage de B. V. Bowden intitulé Faster Than Thought: Symposium on Digital Computing Machines. Turing pose des questions et y répond en évoquant le système d'évaluation, avec les concepts de stratégie minimax, d'analyse préalable variable, de recherche quiescente (en) et d'apprentissage. Il va beaucoup plus loin que dans les règles mises en place dans Turochamp[12]. Il n'y mentionne pas le nom de Turochamp mais évoque la partie d'une machine contre un humain[13],[14].

PostéritéModifier

Héritage et influenceModifier

Le code original écrit par Turing et Champernowne n'a pas été conservé. En 1980, Champernowne décrit aussi bien qu'il le peut la manière dont fonctionnait Turochamp, mais il ne se rappelle pas en détails de toutes les règles mises en œuvre dans le programme[3],[12]. En 2012, des experts en informatique recréent le programme dans le but de jouer une partie symbolique[15].

Turochamp reste le premier programme d'échecs, conçu avant même les premiers ordinateurs. Turochamp fait d'Alan Turing un des candidats au titre de fondateur des programmes d'échecs, au même titre que Claude Shannon avec son article de 1949 intitulé Programming a Computer for Playing Chess et que Konrad Zuse grâce à son langage de programmation intitulé Plankalkül et les routines informatiques d'échecs qu'il écrit de 1941 à 1945[2],[16]. En 1947-1948, Donald Michie et Shaun Wylie écrivent également un programme d'échecs intitulé Machiavelli, que Turing essaye en vain de transposer sur Ferranti Mark I en même temps que Turochamp[17]. Ce programme, qui permet seulement de calculer une profondeur de coup et écrit comme un concurrent de Turochamp, reste inachevé[18].

En , Dietrich Prinz, qui a travaillé pour Ferranti, développe le premier programme d'échecs fonctionnant sur un ordinateur, le Ferranti Mark I du Massachusetts Institute of Technology (MIT). Prinz apprend à programmer sur Ferranti Mark I en suivant des séminaires animés par Alan Turing[3].

Turochamp contre KasparovModifier

Turochamp - Kasparov
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup no 7  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°7  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°8  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°8  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°9  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°9  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°10  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°10  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°11  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°11  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°12  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°12  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°13  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°13  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°14  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°14  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°15  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°15  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°16  
Turochamp   - Kasparov  
abcdefgh
88
77
66
55
44
33
22
11
abcdefgh
Coup n°16  

À l'occasion de la The Alan Turing Centenary Conference du au [Note 1] célébrant les 100 ans de la naissance d'Alan Turing, une partie d'échecs est organisée entre Turochamp, vieux de 60 ans, et Garry Kasparov, l'un des meilleurs joueurs de l'histoire du jeu d'échecs[15]. Le programme est recréé par des experts en informatique, selon les règles conçues par Turing et Champernowne. Intitulé Turing program vs Kasparov, il est joué sur un ordinateur portable, grâce au programme ChessBase qui permet de faire fonctionner le Turing Engine (nommé ainsi en mémoire d'Alan Turing)[12],[19]. Cependant, les experts butent sur certains coups décrits par Turing dans sa partie de 1952 que le programme moderne ne peut exécuter. Ken Thompson, un des pionniers des échecs en informatique, qui a notamment réalisé le premier ordinateur entièrement dédié aux échecs nommé Belle[20], tente de remédier au problème, mais, déconcerté, ne trouve pas de solution. Est alors contacté Donald Michie qui réalisa aussi un programme d'échecs en 1947-1948[17],[21]. Ce pionnier de l'intelligence artificielle rappelle que Turing n'était pas passionné par les détails et se focalisait sur les grandes idées et les principes généraux[22].

La partie se termine sur la victoire de Kasparov en 16 coups[6],[7]. Malgré cette victoire très facile, Kasparov reconnait le contexte historique et la qualité de Turochamp qu'il qualifie, en raison de ses 60 ans, de premier jeu de l'histoire[23],[6],[15].

« Turing a écrit les algorithmes sans même avoir d'ordinateur. De jeunes scientifiques ne croiraient même pas cela possible. Ce fut un accomplissement exceptionnel[24]. »

— Garry Kasparov.

NotesModifier

  1. (en) « The Alan Turing Centenary Conference Manchester UK », (consulté le 8 septembre 2016).

RéférencesModifier

  1. Jean Lassègue, « Alan Turing, un souffle de génie », sur Interstices, .
  2. a b et c S. Barry Cooper et Jan van Leeuwen, Part III, p. 644-650.
  3. a b c d e f g h et i Alan Mathison Turing et B. J. Copeland, p. 563-564.
  4. (en) Anthea Carson, « The 1952 Paper Chess Computer of Alan Turing » (consulté le 7 août 2016).
  5. (en) « David Champernowne (1912-2000) », ICGA Journal (en) , vol. 23,‎ , p. 262.
  6. a b et c (en) Bryan Bishop, « Alan Turing's 60-year-old chess program takes on Garry Kasparov », sur The Verge, .
  7. a et b (en) Daniel Cochlin, « Kasparov versus Turing », sur Manchester.ac.uk, .
  8. a et b (en) « An “easy” engine for the Fritz/Rybka interface », sur USCFSales - Official Chess Shop of the United States Chess Federation, .
  9. David N. L. Levy, Monroe Newborn et Monty Newborn, p. 35.
  10. Tristan Donovan, p. 1-9.
  11. a et b (en) Liat Clark et Ian Steadman, « Turing's achievements: codebreaking, AI and the birth of computer science », sur wired.co.uk, .
  12. a b c et d Graham Oppy et Nick Trakakis, p. 13-14.
  13. Bowden, p. 286-287.
  14. L. Fox, p. 187-190.
  15. a b et c (en) « Joueur du siècle », New in Chess,‎ août 1999 & janvier 2000, p. 6-7.
  16. Subrata Dasgupta, p. 193.
  17. a et b Lisa Rougetet, « Une machine en boîtes d’allumettes qui apprend à jouer au Morpion », sur CNRS : Images des mathématiques, (consulté le 9 août 2016).
  18. George W. Atkinson 1998, p. 39.
  19. a et b (en) « Garry Kasparov versus Alan Turing's 1950 chess program », sur ChessVibes.
  20. (en) « Computer History Museum - Middle Game: Computer Chess Comes of Age », sur Computer History Museum.
  21. (en) « Obituary: Donald Michie », sur The Guardian, .
  22. (en) Frederic Friede, « The Reconstruction of Turing's "Paper Machine" », sur Videolectures.net, .
  23. (en) « Alan Turing plays Garry Kasparov at chess 58 years after his death », sur Chess News, .
  24. (en) « Chess algorithm written by Alan Turing goes up against Kasparov », sur The Register.

BibliographieModifier

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

  • (en) George W. Atkinson, Chess and Machine Intuition, Intellect Books, , 175 p. (ISBN 9781871516449, lire en ligne).   ;
  • (en) B. V. Bowden, Faster Than Thought: Symposium on Digital Computing Machines, Sir Isaac Pitman and Sons, Ltd, , 416 p.   ;
  • (en) S. Barry Cooper et Jan van Leeuwen, Alan Turing : His Work and Impact, Elsevier Science, , 914 p. (ISBN 9780123869807, lire en ligne).   ;
  • (en) Subrata Dasgupta, It Began with Babbage : The Genesis of Computer Science, Oxford University Press, , 328 p. (ISBN 9780199309412, lire en ligne).   ;
  • (en) Tristan Donovan, Replay: The History of Video Games, Yellow Ant, (ISBN 978-0-9565072-0-4).   ;
  • (en) L. Fox, Advances in programming and non-numerical computation : [Symposium 1963], Oxford, Pergamon Pr., (ISBN 9780080113562, OCLC 310804145, lire en ligne).   ;
  • (en) David N. L. Levy, Monroe Newborn et Monty Newborn, How Computers Play Chess, Ishi Press, , 260 p. (ISBN 9784871878012).   ;
  • (en) Graham Oppy et Nick Trakakis, The Antipodean Philosopher, Lexington Books, , 282 p. (ISBN 9780739166550 et 0739166557, lire en ligne).   ;
  • (en) Alan Mathison Turing et B. J. Copeland, 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 9780198250791 et 0198250797, lire en ligne).  .

Liens externesModifier

  Vidéo externe
  [vidéo] (en) Turochamp contre Kasparov
Cet article est reconnu comme « bon article » depuis sa version du 9 septembre 2016 (comparer avec la version actuelle).
Pour toute information complémentaire, consulter sa page de discussion et le vote l'ayant promu.
La version du 9 septembre 2016 de cet article a été reconnue comme « bon article », c'est-à-dire qu'elle répond à des critères de qualité concernant le style, la clarté, la pertinence, la citation des sources et l'illustration.