Turochamp
Développé par | Alan Turing et D. G. Champernowne |
---|---|
Type |
Jeu vidéo Moteur d'échecs |
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éveloppement
[modifier | modifier le code]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 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, paru 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éfinis 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 | modifier le code]Héritage et influence
[modifier | modifier le code]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étail 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 Kasparov
[modifier | modifier le code]À 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 et Garry Kasparov, l'un des meilleurs joueurs de l'histoire du jeu d'échecs, soixante ans après la partie historique de [15]. Le programme est recréé par des experts en informatique, selon les règles conçues par Turing et Champernowne. 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 destiné 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].
Intitulé Turing program vs Kasparov, le programme 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]. 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]. »
Notes
[modifier | modifier le code]- (en) « The Alan Turing Centenary Conference Manchester UK », (consulté le ).
Références
[modifier | modifier le code]- Jean Lassègue, « Alan Turing, un souffle de génie », sur Interstices, .
- S. Barry Cooper et Jan van Leeuwen, Part III, p. 644-650.
- Alan Mathison Turing et B. J. Copeland, p. 563-564.
- (en) Anthea Carson, « The 1952 Paper Chess Computer of Alan Turing » (consulté le ).
- (en) « David Champernowne (1912-2000) », ICGA Journal (en) , vol. 23, , p. 262.
- (en) Bryan Bishop, « Alan Turing's 60-year-old chess program takes on Garry Kasparov », sur The Verge, .
- (en) Daniel Cochlin, « Kasparov versus Turing », sur Manchester.ac.uk, .
- (en) « An “easy” engine for the Fritz/Rybka interface », sur USCFSales - Official Chess Shop of the United States Chess Federation, .
- David N. L. Levy, Monroe Newborn et Monty Newborn, p. 35.
- Tristan Donovan, p. 1-9.
- (en) Liat Clark et Ian Steadman, « Turing's achievements: codebreaking, AI and the birth of computer science », sur wired.co.uk, .
- Graham Oppy et Nick Trakakis, p. 13-14.
- Bowden, p. 286-287.
- L. Fox, p. 187-190.
- (en) « Joueur du siècle », New in Chess, août 1999 & janvier 2000, p. 6-7.
- Subrata Dasgupta, p. 193.
- Lisa Rougetet, « Une machine en boîtes d’allumettes qui apprend à jouer au Morpion », sur CNRS : Images des mathématiques, (consulté le ).
- George W. Atkinson 1998, p. 39.
- (en) « Garry Kasparov versus Alan Turing's 1950 chess program », sur ChessVibes.
- (en) « Computer History Museum - Middle Game: Computer Chess Comes of Age », sur Computer History Museum.
- (en) « Obituary: Donald Michie », sur The Guardian, .
- (en) Frederic Friede, « The Reconstruction of Turing's "Paper Machine" », sur Videolectures.net, .
- (en) « Alan Turing plays Garry Kasparov at chess 58 years after his death », sur Chess News, .
- (en) « Chess algorithm written by Alan Turing goes up against Kasparov », sur The Register.
Bibliographie
[modifier | modifier le code] : document utilisé comme source pour la rédaction de cet article.
- (en) George W. Atkinson, Chess and Machine Intuition, Intellect Books, , 175 p. (ISBN 978-1-871516-44-9, 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, Waltham, MA/Kidlington, Oxford, Elsevier Science, , 914 p. (ISBN 978-0-12-386980-7, lire en ligne).
;
- (en) Subrata Dasgupta, It Began with Babbage : The Genesis of Computer Science, Oxford, Oxford University Press, , 328 p. (ISBN 978-0-19-930941-2, lire en ligne).
;
- (en) Tristan Donovan, Replay : The History of Video Games, East Sussex, England, Yellow Ant, , 501 p. (ISBN 978-0-9565072-0-4).
;
- (en) L. Fox, Advances in programming and non-numerical computation : [Symposium 1963], Oxford, Pergamon Pr., (ISBN 978-0-08-011356-2, OCLC 310804145, lire en ligne).
;
- (en) David N. L. Levy, Monroe Newborn et Monty Newborn, How Computers Play Chess, Ishi Press, , 260 p. (ISBN 978-4-87187-801-2).
;
- (en) Graham Oppy et Nick Trakakis, The Antipodean Philosopher, Lanham (Md.), Lexington Books, , 282 p. (ISBN 978-0-7391-6655-0 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 978-0-19-825079-1 et 0198250797, lire en ligne).
.
Liens externes
[modifier | modifier le code]Vidéo externe | |
[vidéo] (en) Turochamp contre Kasparov |
- (en) « Alan Turing vs Alick Glennie (1952) "Turing Test" », sur Chessgames.com ;
- (en) « Turochamp (Computer) vs Garry Kasparov (2012) », sur Chessgames.com ;
- (en) « Alan Turing Plays Garry Kasparov At Chess 58 Years After His Death », sur Chess News, .