Qu’était le programme de jeu de dames de Christopher Strachey, l’un des premiers programmes de jeu?

En 1951, l’un des programmes les plus ambitieux de Grande-Bretagne s’écrivait le soir, sous la plume d’un enseignant. Christopher Strachey était professeur à la Harrow School, près de Londres, et dans ses temps libres, il s’était mis en tête de faire jouer un ordinateur aux dames, le jeu que les Britanniques appellent draughts et les Américains checkers. À l’été 1952, son programme pouvait jouer une partie complète contre une personne sur le Ferranti Mark 1 de l’Université de Manchester, en affichant le damier à l’écran au fil du jeu.

C’est l’un des tout premiers programmes de jeu exécutés sur un ordinateur polyvalent, c’est-à-dire une machine qu’on peut reprogrammer pour n’importe quelle tâche plutôt que construite pour un seul jeu. C’est aussi l’un des premiers exemples d’un ordinateur qui fait ses propres choix dans une partie contre un humain, un petit pas, mais un vrai, vers l’intelligence artificielle.

Qui était Strachey

Strachey est né en 1916 et a étudié les sciences naturelles au King’s College de Cambridge, où il connaissait un peu Alan Turing. Pendant la Seconde Guerre mondiale, il a fait de la recherche sur le radar chez Standard Telephones and Cables, puis il est devenu enseignant, d’abord à la St. Edmund’s School de Canterbury et, à partir de 1949, à Harrow.

Son premier contact avec un ordinateur à programme enregistré a eu lieu en janvier 1951. Par l’intermédiaire d’un ami commun, il a rencontré Mike Woodger, qui travaillait au National Physical Laboratory (NPL) britannique, à Teddington. Le NPL venait de construire le Pilot ACE, une version réduite et fonctionnelle d’un ordinateur que Turing avait conçu après la guerre.

Du Pilot ACE à Manchester

De retour à Harrow, Strachey a décidé d’écrire un programme de dames pour le Pilot ACE. La plupart des débutants auraient commencé par quelque chose de simple, comme une table de nombres. Strachey a choisi un jeu, en partie inspiré par un article sur la façon dont les machines pourraient jouer aux échecs et au tic-tac-toe que Donald Davies, scientifique du NPL, avait publié dans Penguin Science News en juin 1950.

Le programme était trop gros. Il épuisait la petite mémoire du Pilot ACE et, lorsqu’on l’a essayé pour la première fois au NPL, le 30 juillet 1951, il a échoué à cause d’erreurs dans le code.

Entre-temps, Strachey a appris de Woodger l’existence du Ferranti Mark 1, nouvellement installé à l’Université de Manchester, qui avait une mémoire beaucoup plus grande. Turing, alors directeur adjoint du laboratoire de calcul de Manchester, avait rédigé son manuel de programmation, et Strachey lui en a demandé un exemplaire. Il s’est rendu à Manchester pour la première fois en juillet 1951 et a réécrit son programme dans les codes d’instruction de la machine de Manchester, vers octobre de la même année.

Turing a été impressionné, mais il a d’abord proposé un autre défi : faire en sorte que l’ordinateur se simule lui-même, en retraçant ses propres opérations pas à pas. Strachey a mis le jeu de côté et a écrit un programme de traçage d’environ 1 000 instructions, l’un des plus longs écrits pour cette machine. Il est revenu aux dames ensuite, et en juin et juillet 1952, le programme jouait des parties complètes à une vitesse raisonnable.

Bref, le programme a été écrit au cours de 1951, et il a joué ses premières parties complètes à l’été 1952.

Comment jouait le programme

Le Ferranti Mark 1 stockait ses données sur des tubes cathodiques, le même genre d’écran de verre que celui des premiers téléviseurs, et les opérateurs pouvaient observer certains de ces tubes. Strachey a transformé l’un de ces écrans de contrôle en image du damier, où les positions des pions et des dames apparaissaient sous forme de points.

Pour choisir un coup, le programme anticipait trois ou quatre coups, calculait les positions possibles et choisissait celle qui donnait le meilleur résultat. Sa notation était simple : compter les pièces de chaque camp, une dame valant trois pions ordinaires. Le joueur entrait ses coups au moyen d’interrupteurs et de boutons, et l’ordinateur imprimait ses propres coups sur un téléimprimeur, une machine à écrire électrique reliée à l’ordinateur.

Strachey lui a aussi donné une personnalité. Si l’humain tardait ou faisait des erreurs de saisie, le téléimprimeur imprimait des messages comme « Vous devez jouer immédiatement ou abandonner » ou, si l’humain continuait d’ignorer les règles, « Je refuse de perdre plus de temps. Allez jouer avec un être humain. »

Voici le cœur de ce processus de décision, sous forme d’étapes simples :

1. Dresser la liste de tous les coups permis pour l’ordinateur.
2. Pour chaque coup, dresser la liste de toutes les répliques, puis de toutes les répliques à celles-ci, sur quelques niveaux.
3. Au bout de chaque ligne, noter le damier : les pièces de l’ordinateur moins celles de l’humain, les dames comptant pour 3.
4. Supposer que l’humain choisit toujours la réplique la pire pour l’ordinateur.
5. Jouer le coup dont le pire scénario est le meilleur.

Pourquoi il a compté

Le programme de Strachey a été l’un des premiers à montrer qu’un ordinateur polyvalent pouvait prendre part à une partie contre une personne, en prenant des décisions et en les communiquant à l’écran et sur une imprimante. Certains auteurs le qualifient pour cette raison de premier jeu vidéo, mais cette affirmation dépend des définitions, et un programme de tic-tac-toe appelé OXO tournait la même année sur l’ordinateur EDSAC, à Cambridge.

Sa plus grande influence s’est exercée sur un autre programmeur. En septembre 1952, Strachey s’est rendu à une conférence de l’Association for Computing Machinery, à Toronto, et y a décrit son programme de dames. Arthur Samuel, d’IBM, en a entendu parler à cette occasion et a ensuite écrit son propre programme de dames pour l’IBM 701.

Le projet a aussi lancé la carrière de Strachey. Son habileté en programmation a impressionné le groupe de Manchester et, en juin 1952, il a quitté l’enseignement pour entrer à la National Research Development Corporation. Il est devenu une figure de proue de la conception des langages de programmation et a contribué à fonder la sémantique dénotationnelle, une façon mathématique de décrire ce que signifient les programmes.

Comment le programme de dames de Strachey a-t-il mené à l’apprentissage automatique?

Le programme de Strachey lui-même n’apprenait pas. Il jouait de la même façon chaque fois, en utilisant des règles de notation fixes qu’il avait écrites à la main. Il a bien conçu une routine d’apprentissage et discuté avec Turing de l’idée de l’essayer sur un jeu plus simple, le jeu de Nim, mais il ne l’a pas terminée avant que d’autres présentent des programmes d’apprentissage fonctionnels.

Arthur Samuel a franchi l’étape suivante. Inspiré par le travail de Strachey, il a construit son propre programme de dames et a continué de l’améliorer tout au long des années 1950; en 1956, il a été présenté à la télévision. Les travaux de Samuel sur les dames sont devenus l’un des premiers exemples les plus connus d’un ordinateur qui s’améliore à une tâche grâce à l’expérience, l’idée de base sur laquelle repose l’apprentissage automatique.

Cette lignée mène directement aux systèmes de jeu des dernières années, qui apprennent à évaluer les positions à partir d’un nombre énorme de parties plutôt qu’à partir de la formule d’un programmeur. La règle de notation que Strachey avait écrite à la main, une dame vaut trois pions, est le genre de jugement humain que ces systèmes découvrent maintenant par eux-mêmes.