Une machine en boîtes d’allumettes qui apprend à jouer au Morpion

En 1961, Donald Michie met au point MENACE, une des premières learning machines pour jouer au Tic-Tac-Toe – plus connu sous le nom de Morpion en France – construite à l’aide d’exactement 304 boîtes d’allumettes vides et de quelques billes de couleur.

Donald Michie (1923-2007) est un chercheur britannique en intelligence artificielle reconnu pour avoir travaillé au déchiffrage des messages codés allemands pendant la seconde guerre mondiale. Tout comme Alan Turing, avec qui il a travaillé à Bletchley Park, Michie s’intéresse à théoriser les mécanismes du jeu d’Échecs ; les deux hommes entretiennent régulièrement des discussions autour d’un déjeuner sur la possibilité de construire des programmes informatiques qui pourraient faire preuve d’intelligence et capables d’apprendre par eux-mêmes ⁴À partir de 1943, Turing et Michie se retrouvent chaque vendredi soir dans un pub pour jouer aux Échecs et discuter. Voir (Hodges, 2012, p. 310).. Ils mettent respectivement au point les programmes Turochamp (d’Alan Turing et David Champernowne) et Machiavelli (de Donald Michie et Shaun Wylie) vers la fin des années 1940, alors qu’il n’existe pas encore de machine pour exécuter les instructions ⁵Tous les calculs étaient faits à la main !. Turochamp et Machiavelli ont joué quelques parties par correspondance, mais les calculs fastidieux ont rapidement découragé les concepteurs…

Ces réflexions sur la possibilité de créer des machines « qui apprennent » amènent Donald Michie à développer en 1961 une machine destinée à jouer, et surtout à apprendre à jouer, au Tic-Tac-Toe. Il la nomme MENACE (Matchbox Educable Noughts And Crosses Engine ⁶Machine Éducable en Boîtes d’Allumettes pour Morpion, soit MEBAM en français, mais qui n’a aucune signification !). Elle est composée de boîtes d’allumettes vides et de perles de couleur. L’objectif de Michie n’est pas d’élaborer une machine qui jouerait parfaitement dès le début, mais de construire un dispositif qui ne dispose d’aucune information préalable – à part les règles du jeu – et qui devient un joueur expert avec de la pratique.

Dispositif et fonctionnement de MENACE

MENACE est composée de 304 boîtes d’allumettes vides sur lesquelles sont dessinées respectivement les configurations possibles pouvant se présenter au jeu du Tic-Tac-Toe (ce nombre a été réduit au minimum en tenant compte des symétries de la grille par rapport à la diagonale). Les boîtes sont collées ensemble pour former une sorte de « commode », comme le montre la figure ci-dessous.

Figure 1

Dans chaque boîte, on dispose des billes de couleurs différentes : il y a 9 couleurs, une pour chacune des 9 cases de la grille. Une boîte donnée contient les billes de couleur correspondant aux cases inoccupées de la position en question. Par exemple, au troisième tour de jeu pour MENACE (qui est toujours la première à jouer), il reste 5 cases inoccupées sur la grille, soit 5 billes de couleurs différentes. Chaque boîte est également munie d’une petite « gouttière » en forme de V, de sorte qu’en basculant la boîte vers l’avant, une des billes roule au hasard la première vers l’avant de la boîte (on peut voir ce mécanisme sur la première figure de l’entête de l’article).

Pour faire jouer à MENACE son premier tour, on sélectionne la boîte correspondant à la position initiale (grille vide), on la secoue, et on regarde la couleur de la bille qui est arrivée dans la gouttière : la couleur orange, par exemple, indique que MENACE place son rond au coin en bas à gauche de la grille. On remet la boîte à sa place, mais en la laissant ouverte, pour montrer que cette position a été jouée. Si on décide de répondre par une croix au centre, on choisit ensuite la boîte correspondant à cette nouvelle position, on la secoue, et on regarde la bille arrivée dans la gouttière pour jouer le coup de MENACE. Le processus se poursuit jusqu’à ce qu’il y ait un gagnant, comme le montre l’exemple ci-dessous, où le joueur humain remporte la victoire :

Figure 2

Comment MENACE apprend-elle ?

L’apprentissage de MENACE est basé sur un système de « récompenses » et de « punitions » dépendant du résultat de la partie :

• si MENACE a perdu la partie, on retire des boîtes ouvertes (c’est-à-dire des positions qui ont été rencontrées) les billes qui sont arrivées dans la gouttière. Ainsi, il est moins probable que MENACE reproduise le même mouvement si la configuration se présente à nouveau, elle a en quelque sorte « appris » de ses erreurs.
• si MENACE a gagné la partie, alors on donne à chaque boîte ouverte un bonus de trois billes, de la même couleur que celle qui est arrivée dans la gouttière. Ainsi, on encourage la répétition du coup concerné.
• si MENACE arrive à une partie nulle, un bonus d’une bille seulement est appliqué à chaque boîte ouverte. Cela donne à MENACE « suffisamment de ressources pour supporter les découragements répétés des premières parties » (Michie, 1961, p. 137). Une fois les « récompenses » distribuées, on ferme toutes les boîtes et MENACE est prête pour la prochaine partie.

Il est possible qu’après quelques parties jouées – contre un joueur expert par exemple – MENACE se retrouve à court de billes dans une position donnée. Dans ce cas, elle a perdu la partie, et on effectue le retrait des billes. En revanche, si la première boîte est vide, MENACE doit être ré-initialisée et l’apprentissage reprend au début.

MENACE a joué un tournoi de 220 parties en deux jours de temps (deux fois huit heures), et d’après Michie, après 20 parties la machine assurait une partie nulle à chaque fois. Le graphique ci-dessous montre la progression de MENACE au cours des parties.

Figure 3

Après 150 parties jouées, MENACE pouvait se débrouiller avec n’importe quelle configuration : quoique Michie fasse, il ne pouvait atteindre au mieux qu’une partie nulle. Ce dernier explique avoir également tenté des techniques de jeu différentes, mais la machine « exploitait alors des pistes dangereuses avec une perspicacité incroyable » (Michie, 1961, p. 138). Le tournoi s’est achevé lorsque Michie eut perdu 8 parties successives sur 10 jouées. La machine était devenue un joueur expert !

Et pour d’autres jeux ?

Cette méthode d’apprentissage de la machine par un système de « récompenses » et de « punitions » peut s’envisager pour d’autres jeux de la sorte (ces jeux sont appelés des jeux combinatoires), nécessitant un nombre de boîtes d’allumettes moins important. Par exemple, en 1962, le grand spécialiste des mathématiques récréatives Martin Gardner propose un dispositif similaire nommé HER (Hexapawn Educable Robot), en modifiant le système de récompenses, pour un jeu de son invention, l’Hexapawn, sur un échiquier 3 × 3. HER ne nécessite que 24 boîtes d’allumettes et Gardner a utilisé des bonbons « jujube » (comme les Ours d’Or d’Haribo) à la place des billes de couleur. Ce dernier explique qu’une telle machine a également été créée pour le jeu de Nim (nommé NIMBLE : Nim Box Logic Engine Machine) avec 18 boîtes d’allumettes et qui n’a nécessité que 30 parties pour jouer parfaitement.

Le mécanisme de ces learning machines fonctionnent également très bien pour des jeux combinatoires plus complexes, mais sur des plateaux de taille réduite. C’est le cas du jeu de Go sur un plateau 2 × 2, ou des Dames sur un plateau 3 × 3. En revanche, même sur le plateau le plus simplifié du jeu d’Échecs (de taille 5 × 5, en enlevant un fou, une tour et un cavalier), le modèle reste bien trop complexe pour les capacités d’apprentissage de la machine. Ceci explique certainement pourquoi il faudra attendre 1997 pour que le programme Deep Blue l’emporte sur le champion du monde Garry Kasparov !

Références

Copeland, Jack (Ed.) (2004). The Essential Turing : Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence and Artificial Life plus The Secrets of Enigma, Oxford University Press.

Gardner, Martin (1962). « A Matchbox Game Learning-Machine », Scientific American, March 1962, pp. 138-144.

Hodges, Andrew (2012). Alan Turing : The Enigma, Princeton University Press.

Michie, Donald (1961). « Trial and Error », Penguin Science Survey, Vol. 2, pp. 129-145.

Site mscroggs.co.uk.

Site boingboing.