# Comment le programme de jeu de dames d’Arthur Samuel apprenait-il, et d’où vient l’expression « apprentissage automatique »?

Date: 2019-04-12 · Author: Robert Scales · https://guidetoartificialintelligence.com/fr/apprendre/samuel-jeu-de-dames-apprentissage-automatique/

**Answer:** Dans le numéro de juillet 1959 de l’IBM Journal of Research and Development, l’ingénieur d’IBM Arthur Samuel présentait un programme de jeu de dames pour l’IBM 704 qui s’améliorait avec l’expérience, jusqu’à jouer mieux que lui après seulement 8 à 10 heures de jeu machine. Le titre de l’article, « Some Studies in Machine Learning Using the Game of Checkers », a contribué à faire de *machine learning* (apprentissage automatique) le nom des ordinateurs qui s’améliorent par l’expérience au lieu de se faire dicter chaque étape.

Toute personne qui programme connaît la frustration de devoir détailler chaque étape qu’un ordinateur doit suivre. Arthur Samuel, ingénieur chez IBM, a vu un moyen de contourner le problème. Si un ordinateur pouvait apprendre par l’expérience, écrivait-il, il épargnerait un jour aux gens une bonne partie de cette programmation minutieuse. Pour le prouver, il a appris à un ordinateur à jouer aux dames, puis l’a laissé s’améliorer par lui-même.

Les résultats ont paru en juillet 1959 dans l’*IBM Journal of Research and Development*, volume 3, numéro 3, sous le titre « Some Studies in Machine Learning Using the Game of Checkers ». Samuel montrait qu’un programme pouvait apprendre à jouer mieux que la personne qui l’avait écrit, et qu’il pouvait y arriver en environ 8 à 10 heures de jeu.

## Qui était Arthur Samuel

Samuel est né en 1901 à Emporia, au Kansas, et a enseigné au MIT et à l’Université de l’Illinois avant d’entrer chez IBM à Poughkeepsie, dans l’État de New York, en 1949. Il a travaillé sur le jeu de dames dans ses temps libres pendant des années. Une première version tournait sur l’IBM 701, le premier ordinateur commercial d’IBM, et sa démonstration publique aurait fait grimper l’action d’IBM de 15 points du jour au lendemain.

En août 1956, il a présenté ses travaux à l’atelier d’été de Dartmouth sur l’intelligence artificielle. Les notes de cet été-là mentionnent un exposé sur la façon de noter les positions aux dames et de fixer des objectifs intermédiaires, ainsi que la remarque d’un observateur selon laquelle Samuel s’intéressait bien plus au problème de l’apprentissage qu’au jeu de dames lui-même.

On attribue largement l’expression *machine learning* (apprentissage automatique) à Samuel en raison de cet article de 1959, qui l’emploie dans son titre et tout au long du texte.

## Pourquoi le jeu de dames?

Samuel a soigneusement expliqué son choix. Les jeux éliminent les détails désordonnés de la vie réelle tout en gardant ce qui compte pour étudier l’apprentissage : un but clair (gagner), des règles précises et aucune recette connue qui garantisse la victoire. Il a préféré les dames aux échecs parce que leurs règles plus simples lui permettaient de se concentrer sur les méthodes d’apprentissage plutôt que sur le jeu. Il appréciait aussi que les gens puissent jouer contre la machine, ce qui faisait une démonstration convaincante pour quiconque doutait que les machines puissent apprendre.

Même le jeu de dames est trop vaste pour être résolu par la force brute. Samuel estimait qu’explorer toutes les parties possibles prendrait un nombre absurde de siècles; le programme devait donc faire des choix.

## Comment le programme jouait

Le programme tournait sur l’IBM 704. Il stockait chaque damier dans quatre des mots de 36 bits de l’ordinateur, en utilisant 32 bits pour les 32 cases foncées du damier. Pour choisir un coup, il :

1. Dressait la liste de tous les coups permis à partir de la position actuelle.
2. Anticipait plusieurs coups pour les deux camps, habituellement environ trois au départ, en allant plus loin quand des prises étaient possibles.
3. Notait les positions au bout de chaque ligne de jeu à l’aide d’une formule, en additionnant des caractéristiques pondérées comme le nombre de pièces de chaque camp.
4. Remontait l’arbre en supposant que chaque joueur choisit sa meilleure option, une méthode appelée *minimax*, et choisissait le coup au meilleur résultat.

L’apprentissage consistait à améliorer cette formule de notation et à mémoriser des positions.

## Deux façons d’apprendre

**L’apprentissage par cœur.** Le programme enregistrait les positions qu’il avait rencontrées, avec leur note. Quand il en revoyait une, il pouvait réutiliser la note stockée, qui reflétait déjà une anticipation faite lors de la partie précédente. En pratique, il voyait plus loin chaque fois qu’une position revenait. La bande mémoire de Samuel contenait plus de 53 000 positions, et l’apprentissage par cœur à lui seul faisait du programme un débutant meilleur que la moyenne, fort dans les ouvertures et les finales, mais faible en milieu de partie.

**L’apprentissage par généralisation.** C’est la méthode qui ressemble le plus à l’apprentissage automatique moderne. Le programme tenait une liste de caractéristiques possibles et ajustait les poids de sa formule de notation après chaque coup. Il le faisait en comparant la note rapide d’une position avec la note plus approfondie obtenue en anticipant. Si la note rapide était fausse, les termes qui avaient causé l’erreur étaient modifiés.

Pour lui donner de la pratique, Samuel faisait jouer le programme contre lui-même, sous la forme de deux joueurs qu’il appelait Alpha et Beta :

| Joueur | Ce qu’il fait | Ce qui se passe après chaque partie |
|---|---|---|
| Alpha | Met à jour sa formule de notation après chaque coup | Si Alpha gagne, Beta reçoit la formule d’Alpha |
| Beta | Garde la même formule toute la partie | Si Beta gagne, Alpha reçoit un mauvais point |
| Règle | Après trois mauvais points, la formule d’Alpha est brassée | Cela l’empêche de rester coincé |

Lors des premiers essais, l’apprentissage était rapide, mais irrégulier. Des joueurs amateurs décrivaient le programme comme rusé, mais battable, et après quelques dizaines de parties, il approchait le niveau d’un joueur meilleur que la moyenne. Samuel a ensuite corrigé plusieurs sources d’instabilité, comme le fait que le programme se laissait tromper par le mauvais jeu d’un adversaire.

> **À essayer :** jouez dix parties de tic-tac-toe contre une amie ou un ami. Après chaque partie, notez une règle empirique que vous ajouteriez ou abandonneriez, comme « prendre le centre en premier ». Comptez combien de règles survivent à la dixième partie. Vous faites ce que faisait l’Alpha de Samuel : ajuster une méthode de notation à partir de l’expérience.

## Pourquoi c’était important

Les travaux de Samuel ont montré, avec un programme qui fonctionnait et des mesures soignées, qu’un ordinateur pouvait devenir meilleur dans une tâche sans être reprogrammé. Ils ont aussi introduit des idées qui restent centrales : le jeu contre soi-même, l’apprentissage d’une fonction d’évaluation et l’ajustement de prédictions pour qu’elles concordent avec des prédictions ultérieures mieux informées. Il a même décrit une « approche par réseau de neurones » de l’apprentissage comme une voie distincte, qu’il jugeait en 1959 encore très loin de produire des appareils pratiques.

Il est ensuite passé à Stanford, après avoir pris sa retraite d’IBM en 1966, et est resté actif en informatique jusqu’à la fin de ses quatre-vingts ans. Il est mort en 1990.

## Comment l’apprentissage du jeu de dames de Samuel se compare-t-il à celui des IA de jeu d’aujourd’hui?

L’air de famille est frappant. AlphaGo de DeepMind, qui a battu Lee Sedol au go en 2016, et son successeur AlphaZero, décrit dans la revue *Science* en décembre 2018, ont tous deux appris en grande partie en jouant contre eux-mêmes, exactement comme Alpha jouait contre Beta. Ils combinent aussi une recherche par anticipation avec une façon apprise de juger les positions, ce qui est précisément la structure du programme de Samuel.

La principale différence tient à ce qui fait le jugement. La formule de notation de Samuel était une somme pondérée de caractéristiques qu’il choisissait à la main, comme le nombre de pièces. Les systèmes actuels utilisent des réseaux de neurones profonds qui apprennent leurs propres caractéristiques à partir des positions brutes, avec des millions de poids ajustables au lieu de quelques dizaines. Et ils s’entraînent avec d’énormes quantités de puissance de calcul, en jouant des millions de parties là où le programme de Samuel en jouait quelques dizaines lors de ses premiers essais.

L’intuition centrale de Samuel tient toujours : un programme qui compare ses estimations rapides avec ce que révèle un examen plus approfondi, et qui se corrige, peut apprendre par lui-même à jouer mieux que celui qui l’a créé.

## Sources

- Some Studies in Machine Learning Using the Game of Checkers: https://people.csail.mit.edu/brooks/idocs/Samuel.pdf
- Arthur Samuel: https://web.archive.org/web/20190225155629/https://en.wikipedia.org/wiki/Arthur_Samuel
- Ray Solomonoff and the Dartmouth Summer Research Project in Artificial Intelligence, 1956: http://raysolomonoff.com/dartmouth/dartray.pdf