Programme de dames de Christopher Strachey

Le programme de dames de Christopher Strachey est un programme informatique de jeu de dames créé par l'informaticien britannique Christopher Strachey en 1951 et qui fonctionne pour la première fois, à une vitesse raisonnable, au cours de l'été 1952 sur l'ordinateur Ferranti Mark I de l'université de Manchester.

Programme de dames de Christopher Strachey

---

Développeur	Christopher Strachey
Réalisateur	Christopher Strachey

---

Début du projet	1951
Date de sortie	Juillet 1952

Genre	Jeu de dames
Mode de jeu	un joueur
Plate-forme	Pilot ACE (début du développement), Ferranti Mark I

Strachey est rapidement attiré par les machines intelligentes et intègre au début de l'année 1951 le National Physical Laboratory, qui vient de réussir à fabriquer un prototype d'ordinateur appelé Pilot ACE, basé sur l'Automatic Computing Engine d'Alan Turing. Pour se familiariser avec la programmation sur cette machine, Strachey écrit un programme de jeu de dames en s'inspirant de l'article A Theory of Chess and Noughts and Crosses paru en 1950. Il est également influencé dans son choix par Charles Babbage, sa machine analytique et ses propositions de jeu d'échecs et de dames. Cependant, des erreurs de programmation, le manque de puissance de l'ordinateur et les changements fréquents de composants sur la plate-forme empêchent le programme de fonctionner correctement. Au printemps 1952, Strachey apprend que l'université de Manchester dispose d'un ordinateur plus puissant que le Pilot ACE, le Ferranti Mark I. Il se rend alors au Computing Machine Laboratory de Manchester où il rencontre Alan Turing. Poussé par les encouragements de ce dernier, il apporte de nombreuses améliorations à son programme qu'il parvient à faire fonctionner à une vitesse raisonnable en juillet 1952.

C'est le premier jeu sur un ordinateur Turing-complet à usage général, par opposition à des jeux comme Bertie the Brain qui fonctionnent sur des machines dédiées. L'importance de ce programme va au-delà du domaine des jeux sur ordinateur. Il est en effet l'un des premiers à faire fonctionner une intelligence artificielle et une méthode de recherche heuristique, uniquement précédé par le programme d'échecs Turochamp théorisé par Alan Turing en 1948. En outre, il est « probablement » le premier à utiliser un affichage graphique. Au moment où Christopher Strachey porte le jeu de dames sur Ferranti Mark I et parvient à le faire fonctionner en 1952, le jeu vidéo de tic-tac-toe OXO est conçu par Alexander S. Douglas sur l'EDSAC. OXO et le programme de Strachey sont les plus anciens jeux à proposer un affichage visuel sur un écran électronique. La plupart des ouvrages traitant le sujet considèrent OXO comme le premier jeu vidéo de l'histoire, bien que certains observateurs estiment qu'il est difficile de déterminer lequel des deux est le premier à avoir été fonctionnel.

Le programme inspire notamment Arthur Samuel qui le découvre la même année à Toronto au Canada, lors d'une conférence au cours de laquelle Strachey décrit son jeu sur ordinateur. Samuel développe alors son programme de jeu de dames en 1952 sur IBM 701.

Développement

Le National Physical Laboratory et le Pilot ACE

Christopher Strachey est un informaticien britannique, connu pour être l'un des fondateurs, parmi les premiers à avoir prôné une approche mathématique dans l'étude des programmes, de la sémantique dénotationnelle et l'un des pionniers du langage de programmation. Né en 1916, il est le fils du cryptographe britannique Oliver Strachey et de Ray Strachey, une écrivaine et politicienne féministe britannique. Il fait ses études à la Gresham's School, au King's College de Cambridge et à l'Université de Cambridge. Malgré ses antécédents familiaux, il ne se fait pas spécialement remarquer au King's, et travaille par la suite sur des radars durant la Seconde Guerre mondiale, puis enseigne à Harrow. Cependant, le concept des machines intelligentes attire tout de suite son attention. En janvier 1951, un ami le présente à Mike Woodger du National Physical Laboratory (NPL), puis il rejoint le laboratoire. Le NPL accueille le prototype d'ordinateur Automatic Computing Engine élaboré et construit par Alan Turing à partir de 1945, mais le projet traîne de longs mois, pour des raisons aussi bien techniques, que politiques et économiques. Turing est découragé, et, peu diplomate, il abandonne en 1947 ce projet très ambitieux. Le laboratoire, grâce à Donald Davies qui travaille au NPL, continue les travaux et réussit finalement à construire une version plus modeste, de taille réduite, basée sur le concept ACE de Turing, nommée Pilot ACE, qui fonctionne à partir de mai 1950.

Le Pilot ACE au Science Museum de Londres.

Pendant son temps libre, Strachey développe un programme de jeu de dames dans le but de se familiariser avec la programmation sur cette machine, qu'il termine en février 1951. Il s'inspire d'un article intitulé « A Theory of Chess and Noughts and Crosses » paru en 1950 dans le périodique Penguin Science News écrit par le scientifique du NPL Donald Davies. Il est également influencé dans son choix par Charles Babbage, sa machine analytique et ses propositions de jeu d'échecs et de dames. Strachey compile une version préliminaire du programme en mai 1951 au NPL, qu'il essaye pour la première fois le 30 juillet 1951 sur l'ordinateur Pilot ACE. Cependant des erreurs dans le code de programmation empêchent le programme de fonctionner. De plus, la mémoire du prototype est insuffisante pour faire fonctionner le jeu correctement. Strachey fait également face à des changements fréquents de composants de l'ordinateur, ce qui rend régulièrement obsolète une partie de ce qu'il a écrit.

L'université de Manchester et le Ferranti Mark I

Parallèlement, au printemps 1951, Woodger apprend à Strachey que l'ordinateur Ferranti Mark I vient d'être installé à l'université de Manchester, à la place du Manchester Mark I dont il s'inspire. Cet ordinateur possède plus de mémoire que le Pilot ACE, ce qui correspond mieux aux travaux que veut réaliser Strachey. Au mois de juillet, il se rend pour la première fois à l'université de Manchester, afin de découvrir l'ordinateur de chez Ferranti, et rencontre Alan Turing, qui est alors directeur assistant au Computing Machine Laboratory de l'université. Strachey lui explique ses idées au sujet de la création d'un programme de jeu de dames. Il connait un peu Turing puisqu'ils étaient tous deux au King's College, ce qui lui permet d'obtenir le manuel d'utilisation du Ferranti Mark I, que Turing a récemment écrit, afin de porter le jeu sur cet ordinateur. Turing est assez impressionné par son projet de programme de dames, mais suggère à Strachey qu'un travail intéressant serait de simuler la machine elle-même, de la même manière que le programme d'analyse sélective développé pour l'ordinateur EDSAC de l'université de Cambridge. Strachey est convaincu par cette idée et met temporairement de côté son programme de dames. La version finale du programme comporte près de 1 000 instructions, ce qui en fait à l'époque le programme le plus long jamais écrit pour une machine, sans que Strachey soit conscient de ce record.

Néanmoins, les encouragements de Turing sont cruciaux pour Strachey qui parvient finalement à faire fonctionner le programme de dames sur le Ferranti Mark I. En outre, Turing apprécie Strachey, qui a su amener des idées nouvelles du King's College dans l'atmosphère purement technique du laboratoire de Manchester, d'autant plus qu'ils se comportent de la même manière et ont le même sens de l'humour. Parallèlement en 1952, ils s'amusent tous les deux à réaliser un programme sur le Mark I qui rédige des lettres d'amour au contenu aléatoire, grâce aux nombres aléatoires et à des morceaux de textes pré-enregistrés. En outre, Turing réussit à convaincre Strachey de réaliser deux programmes audio, les premiers du genre, qui permettent de jouer de la musique sur un ordinateur, notamment In the Mood de Glenn Miller et Baa, Baa, Black Sheep.

Au départ, les autres membres du laboratoire sont amusés de voir que Strachey veut dès le début passer son programme sur bande perforée, pensant naïvement que le premier venu peut réussir du premier coup. Cependant, après la rectification de quelques erreurs, le programme fonctionne, au grand étonnement de tout le monde, et joue God Save the King sur un haut-parleur. À partir de là, Strachey bénéficie d'une réputation de « formidable » développeur. Le programme fait plus de 20 pages de long et comporte plus de 1 000 instructions. Strachey apporte de nombreuses améliorations et finit le portage du programme de dames qui, en juillet 1952, peut enfin jouer une partie de dames complète à une vitesse raisonnable.

Fonctionnement

Reproduction moderne du programme de dames de Christopher Strachey, fonctionnant pleinement en 1952 sur Ferranti Mark I.

Le programme simule un jeu de dames classique. Il utilise une heuristique simple, et calcule les trois à quatre coups suivants. Il calcule toutes les positions possibles à chaque tour, afin de choisir la position la plus forte. Il prend également en compte d'autres paramètres comme la valeur des dames qui se voient attribuer une valeur trois fois supérieure à celle d'un pion ordinaire. Il affiche le déroulement du jeu sur un écran cathodique. Strachey détourne de son usage originel deux des écrans de l'ordinateur destinés au contrôle de son fonctionnement, pour afficher des graphismes. Les écrans affichent un bitboard et les positions des pions ou dames. Les cases blanches sont numérotés de 1 à 31 et le programme utilise trois variables 32 bits pour répertorier les positions des pions ou des dames de chaque couleur. Les parties sont enregistrées par un téléscripteur.

Le joueur appuie sur un bouton pour lancer la partie et le programme lui propose de lancer une pièce afin de décider à pile ou face qui va commencer. Le joueur transmet alors cette information à l'ordinateur à l'aide d'un interrupteur puis d'un bouton. L'ordinateur et le joueur jouent alternativement, le premier inscrivant son coup sur le téléscripteur et ce dernier le jouant à l'aide d'un bouton, puis d'un second pour valider. Un des deux écrans permet à l'ordinateur de présenter le coup qu'a choisi le joueur avant qu'il le valide, ou qu'il l'annule pour choisir un autre coup. L'autre écran permet d'afficher le déroulement de la partie.

Quand la partie est lancée, l'ordinateur émet des bips sonores dès qu'il est prêt à accepter le coup du joueur. Le programme propose des réponses pré-enregistrées en fonction des actions du joueur. Par exemple : si le joueur met trop de temps à jouer, l'ordinateur affiche à l'écran « You must play at once or resign. » (« Vous devez jouer un coup ou abandonner. ») ; si le joueur fait une erreur de manipulation, il affiche « Kindly read the instructions and start the move again. » (« Veuillez lire les instructions et recommencez le coup. ») ; un comportement anormal du joueur provoque « If you don't follow the instructions I can't play with you. » (« Si vous ne suivez pas les instructions, je ne peux pas jouer avec vous. ») ou un brusque « I refuse to waste any more time. Go and play with a human being. » (« Je refuse de perdre plus de temps. Allez jouer avec un être humain. »). La machine étant également sujette à des problèmes matériels ou logiciels, elle peut produire des messages erronés comme « Please dread zthe sintruction fcard. Shall wwe ztoss ffor zthe ffirst xmove. »…

Quand la partie est terminée, le programme joue God Save the King.

Postérité

Le programme de Strachey a été préservé et est conservé à la bibliothèque Bodléienne à l'université d'Oxford. Cinq versions du programme existent, écrites à la main et longues d'une vingtaine de pages chacune. Les retranscriptions sur papier de parties jouées par Strachey lors des tests, enregistrés grâce à un téléscripteur, sont également conservées. Ces impressions indiquent que le programme a principalement été développé en juin et juillet 1952 mais une version, non datée, a probablement été écrite avant mai 1951. En 2012, David Link réalise l'émulation du programme de dames de Strachey.

C'est le premier jeu sur un ordinateur Turing-complet à usage général, par opposition à des jeux comme Bertie the Brain qui fonctionnent sur des machines dédiées. Ce programme inspire Arthur Samuel, qui découvre le jeu lors d'une conférence, organisée la même année à Toronto au Canada, au cours de laquelle Strachey décrit son jeu sur ordinateur. Samuel crée alors son programme de jeu de dames en 1952 sur IBM 701. Jusqu'en 1955, il en améliore l'intelligence artificielle, de manière rudimentaire, dans des versions successives et en 1956, une version est présentée à la télévision.

L'importance du programme de jeu de dames de Strachey va au-delà du domaine des jeux sur ordinateur. Il est effet un des premiers programmes à faire fonctionner une intelligence artificielle et une méthode de recherche heuristique, uniquement précédé par le programme d'échecs Turochamp théorisé par Alan Turing en 1948. En outre, il est « probablement » le premier programme à utiliser un affichage graphique. Au moment où Strachey porte le jeu de dames sur Ferranti Mark I et parvient à le faire fonctionner en 1952, le jeu vidéo de tic-tac-toe OXO est conçu par Alexander S. Douglas sur l'EDSAC. OXO et le programme de Strachey sont les plus anciens jeux à proposer un affichage visuel sur un écran électronique. La plupart des ouvrages traitant le sujet considèrent OXO comme le premier jeu vidéo de l'histoire, bien que certains observateurs estiment qu'il est difficile de déterminer lequel des deux est le premier à être fonctionnel.

À l'époque où Christopher Strachey écrit son programme de dames, il imagine un système d'apprentissage automatique. Il conçoit un programme d'apprentissage routinier qu'il envisage d'implémenter un jour dans une machine de jeu de Nim. Il en parle également avec Turing par le biais d'un courrier qu'il lui envoie. Strachey manque cependant l'opportunité d'être le premier à présenter un programme fonctionnel incorporant le concept d'apprentissage automatique. Il est en effet devancé par Anthony Oettinger et ses programmes fonctionnant sur l'EDSAC de l'université de Cambridge.

Bibliographie

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

• (en) Robin Andersen et Jonathan Alan Gray, Battleground : The Media, Greenwood Publishing Group, 2008 (lire en ligne).  ;
• (en) Kevin Baker, The Ultimate Guide to Classic Game Consoles, eBookIt, 2013, 299 p. (ISBN 978-1-4566-1708-0, lire en ligne).  ;
• (en) Nigel Cawthorne, Alan Turing : The Enigma Man, Arcturus Publishing, 2014, 128 p. (ISBN 978-1-78428-042-0, lire en ligne) ;
• (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/New York, Oxford University Press, 2004, 613 p. (ISBN 0-19-825079-7, EAN 9780198250791, lire en ligne).  ;
• (en) B. Jack Copeland, Turing : Pioneer of the Information Age, Oxford University Press, 2012, 300 p. (ISBN 978-0-19-963979-3, lire en ligne) ;
• (en) Roberto Dillon, The Golden Age of Video Games : The Birth of a Multibillion Dollar Industry, CRC Press, 2016, 218 p. (ISBN 978-1-4398-7324-3, lire en ligne).  ;
• (en) Tristan Donovan, Replay : The History of Video Games, East Sussex, England, Yellow Ant, 20 avril 2010, 501 p. (ISBN 978-0-9565072-0-4).  ;
• Andrew Hodges, Alan Turing, Michel Lafon, 2015, 636 p. (ISBN 978-2-7499-2485-4, lire en ligne).  ;
• (en) Arie Kaplan, The Biggest Names of Video Games, Lerner Publications, 2013, 32 p. (ISBN 978-1-4677-1253-8, lire en ligne).  ;
• (en) Bill Loguidice et Matt Barton, Vintage game consoles : an inside look at Apple, Atari, Commodore, Nintendo, and the greatest gaming platforms of all time, 2014 (ISBN 978-0-415-85600-3, lire en ligne).  ;
• (en) James H. Moor, The Turing Test : The Elusive Standard of Artificial Intelligence, Dordrecht, Kluwer Academic, 2003, 273 p. (ISBN 978-1-4020-1205-1, lire en ligne).  ;
• (en) Jonathan Schaeffer, One Jump Ahead : Computer Perfection at Checkers, Springer, 2008, 585 p. (ISBN 978-0-387-76575-4, lire en ligne).  ;
• (en) Dermot Turing, PROF : Alan Turing Decoded, The History Press, 2015, 320 p. (ISBN 978-1-84165-643-4, lire en ligne).  ;
• (en) Mark J. P. Wolf, The video game explosion : a history from PONG to Playstation and beyond, Westport, Conn., Greenwood Publishing Group, 30 novembre 2007, 380 p. (ISBN 978-0-313-33868-7, lire en ligne).  ;
• (en) Alix Wood, Video game designer, Powerkids Pr., 2014 (ISBN 978-1-4777-6015-4, lire en ligne). .

Liens externes

• (en) « Catalogue of the papers and correspondence of Christopher Strachey, 1930-1983 », sur bibliothèque bodléienne, université d'Oxford ;
• (en) David Link, « David Link: Software Archaeology. On the Resurrection of Programs for the Mark 1, 1948–58 — de 1 h 02 min 10 s à 1 h 05 min 30 s », sur Vimeo ;
• (en) « Strachey 100 », sur Université d'Oxford.