← Retour au blog

Arthur Samuel : le programme de dames qui apprenait seul

En juillet 1959, un ingénieur d'IBM publie un article au titre modeste, « Some Studies in Machine Learning Using the Game of Checkers ». Il y affirme, dès le résumé, qu'on peut programmer un ordinateur pour qu'il apprenne à jouer aux dames mieux que la personne qui a écrit le programme, et cela en « 8 ou 10 heures » de jeu de la machine. L'auteur s'appelle Arthur Samuel. Son programme n'a pas rivalisé avec les meilleurs joueurs, mais plusieurs idées qu'il a testées sur un damier, comme l'évaluation pondérée de la position ou l'élagage alpha-bêta, se retrouvent dans Chinook comme dans l'ordinateur de ce site. Voici ce qu'il faisait vraiment, et ce qu'on lui a fait dire.

🎮 Jouer aux Dames

Un ingénieur de l'électronique chez IBM

Arthur Lee Samuel naît en 1901 au Kansas. Ingénieur en électronique passé par le MIT, les laboratoires Bell et l'université de l'Illinois, il entre chez IBM en 1949 et y reste jusqu'en 1966, avant de finir sa carrière à Stanford, où il meurt en 1990.

Samuel date lui-même les étapes dans une note de son article : un premier programme de dames tourne sur l'IBM 701 en 1952, il est réécrit pour l'IBM 704 en 1954, la première version qui apprend est achevée en 1955 et elle est montrée à la télévision le 24 février 1956. Son programme de base, précise-t-il, ressemble beaucoup à celui que Christopher Strachey avait décrit en 1952.

Pourquoi les dames, et lesquelles

Samuel dit avoir choisi les dames plutôt que les échecs parce que la simplicité des règles lui permettait de se concentrer sur l'apprentissage. Attention au mot checkers : il s'agit des dames anglaises, sur damier 8×8, avec 12 pions par camp, et non des dames internationales sur 10×10, avec 20 pions par camp. Aux dames anglaises, les Noirs commencent, le pion ne prend que vers l'avant, la dame n'avance que d'une case à la fois et l'on choisit librement sa prise. Aux dames internationales, le pion prend aussi en arrière, la dame parcourt toute la diagonale et il faut prendre le plus grand nombre de pièces. Notre comparatif des dames internationales et anglaises détaille ces écarts. Tout ce qui suit concerne le jeu sur 8×8.

Regarder quelques coups devant, puis noter la position

Le programme de 1959 essaie ses coups, imagine les réponses, puis juge les positions obtenues. Il regarde en général au moins trois demi-coups devant lui, et continue tant qu'une prise est possible ou vient d'avoir lieu, jusqu'à 20 demi-coups au plus. Il remonte ensuite les notes par la méthode du minimax : il suppose que l'adversaire choisira toujours la réponse la plus gênante.

Pour noter une position, Samuel utilise un polynôme linéaire : une somme de critères mesurés sur le damier, chacun multiplié par un coefficient qui dit son importance. Le premier est l'avantage matériel, une dame comptant pour 1,5 pion (un rapport de trois pour deux, écrit-il) ; viennent ensuite la mobilité, le contrôle du centre, l'avance des pions, etc. L'ordinateur du site fait de même : aux dames anglaises, il compte une dame pour 1,6 pion et ajoute des bonus pour le centre, l'avance des pions et la défense de la dernière rangée. Mais ses coefficients sont écrits à la main et ne changent pas d'une partie à l'autre. Ceux de Samuel apprenaient.

Apprendre par cœur : 53 000 positions sur bande

La première méthode, le rote learning ou apprentissage par cœur, garde en mémoire les positions rencontrées avec leur note. Quand le programme retombe sur l'une d'elles au bout de sa recherche, il reprend cette note, qui contenait elle-même plusieurs demi-coups de calcul : sans chercher plus longtemps, il voit plus loin.

Il s'entraîne contre lui-même, contre des joueurs et sur des parties publiées. En 1959, sa bande magnétique contient un peu plus de 53 000 positions. Résultat, selon Samuel : de bonnes ouvertures, des finales reconnues longtemps à l'avance, mais un milieu de partie à peine meilleur. Il juge son élève « un débutant plutôt meilleur que la moyenne, mais certainement pas un expert », et estime qu'il faudrait au moins 20 fois plus de positions pour vraiment progresser en milieu de partie.

Apprendre en généralisant : Alpha contre Beta

La seconde méthode est plus ambitieuse. Au lieu de retenir des positions, le programme ajuste les coefficients de son polynôme et choisit lui-même quels critères garder : 16 termes, piochés dans une liste de 38 proposée par Samuel. Seul l'avantage matériel est imposé, pour que la machine sache ce qu'elle cherche.

Pour apprendre, le programme joue contre une copie de lui-même. Le joueur baptisé Alpha compare, à chaque coup, la note qu'il avait donnée à la position précédente avec celle que lui donne sa nouvelle recherche, et corrige ses coefficients selon l'écart. Beta garde les siens toute la partie. Si Alpha gagne, Beta reprend sa façon de juger ; si Alpha perd trop souvent, on bouleverse son polynôme. Des amateurs qui l'ont affronté le trouvent alors « retors mais battable ». Samuel note un point faible amusant : après 28 parties, le programme ne savait toujours pas gagner la finale de deux dames contre une quand la dame seule se réfugie dans le coin double.

En 1967, un second article présente une évaluation plus fine, les « tables de signatures », qui jugent des groupes de critères ensemble au lieu de les additionner un par un. Samuel y reconnaît que son programme reste « incapable de surclasser les maîtres ».

« Machine learning » : le mot et la définition

On présente souvent Samuel comme l'inventeur de l'expression machine learning, l'apprentissage automatique. Ce qui est sûr, c'est qu'elle figure dans le titre et le texte de son article de 1959, qui l'a fait connaître. Qu'il soit le tout premier à l'avoir écrite, nous n'avons pas trouvé de source qui le démontre : prends cette attribution avec prudence.

Méfie-toi aussi de la définition qu'on lui prête souvent : apprendre « sans être explicitement programmé ». Nous l'avons cherchée dans les articles de 1959 et de 1967 sans la trouver ; elle ressemble à une paraphrase plus tardive. Sa propre phrase est plus concrète : programmer les ordinateurs pour qu'ils apprennent par l'expérience devrait, à terme, éviter une bonne partie de la programmation détaillée.

Couper les branches : l'alpha-bêta

L'article de 1967 fait aussi un « plein usage » de l'élagage alpha-bêta, un nom donné, précise Samuel, par John McCarthy. L'idée : dès qu'une réponse adverse montre qu'un coup est moins bon qu'un autre déjà examiné, inutile de regarder les autres réponses à ce coup. Le résultat est exactement le même que celui du minimax complet, pour beaucoup moins de calcul. Samuel donne un exemple : avec 8 coups possibles à chaque fois et un ordre des coups parfait, chercher 10 demi-coups devant coûte environ 66 000 positions au lieu d'environ un milliard.

Nous avons refait le calcul avec un petit script : 810 = 1 073 741 824, et l'arbre minimal qu'un ordre parfait laisse à examiner compte 85 + 85 − 1 = 65 535 positions. Puis nous avons fait chercher le moteur de règles du site depuis la position de départ des dames anglaises, avec une évaluation linéaire volontairement simple, qui n'est ni celle de Samuel ni celle de notre ordinateur (matériel, dame à 1,5 pion, petit bonus d'avance), les coups étant triés d'après la note de la position qu'ils donnent. À chaque profondeur, les deux méthodes ont choisi le même coup avec la même note.

Demi-coups Minimax complet Alpha-bêta Rapport
249133,8
41 4692376,2
636 7681 59623
8845 9318 062105

Le tableau donne le nombre de positions notées par chaque méthode. La colonne du minimax retombe sur le nombre de suites de coups publié pour les dames anglaises (845 931 à 8 demi-coups). L'écart grandit à chaque demi-coup, et c'est ce qui permet de chercher plus loin dans le même temps : Chinook comme l'ordinateur du site cherchent avec l'alpha-bêta.

La télévision, l'action IBM et la partie contre Nealey

Deux histoires accompagnent souvent ce programme. La première est rapportée par ses collègues de Stanford dans leur hommage de 1990 : avant une démonstration, Thomas J. Watson Sr., le fondateur d'IBM, aurait prédit qu'elle ferait monter l'action IBM de 15 points, « et ce fut le cas ». Un article de Fortune de 2018 relie la prédiction à la démonstration télévisée. Nous n'avons trouvé aucun relevé de cours qui le confirme : garde-la comme une anecdote rapportée.

La seconde est mieux documentée, et moins flatteuse. En 1962 (1961 selon la notice de l'IEEE Computer Society), le programme bat Robert Nealey, un joueur aveugle de Stamford présenté comme un champion du Connecticut et l'un des meilleurs joueurs du pays. En 1996, Jonathan Schaeffer et Robert Lake, de l'équipe de Chinook, remettent les choses en place : Nealey se disait maître sans avoir dépassé la catégorie inférieure (Schaeffer ajoute ailleurs qu'il n'a gagné le titre du Connecticut qu'en 1966), il a commis dans cette partie une erreur élémentaire, et il a remporté nettement la revanche l'année suivante, sans perdre une partie. Selon eux, la presse en a pourtant conclu que les dames étaient un problème réglé, et la recherche s'est tournée vers les échecs.

En 1965, le programme affronte le champion du monde Walter Hellman et Derek Oldbury : Schaeffer et Lake écrivent qu'il perd les huit parties. Samuel, en 1967, nuance : Hellman a gagné les quatre parties jouées par correspondance, mais a concédé la nulle dans une partie jouée rapidement face au damier. D'après Schaeffer et Lake, Samuel ne se faisait aucune illusion sur la force de son programme.

Chronologie : de l'IBM 701 à Chinook

Date Événement
1952Premier programme de dames de Samuel, sur l'IBM 701. Christopher Strachey publie la même année la description de son propre programme.
1954Le programme est réécrit pour l'IBM 704.
24 février 1956Démonstration à la télévision de la version qui apprend.
Juillet 1959Article dans l'IBM Journal of Research and Development : apprentissage par cœur et par généralisation.
1962Victoire contre Robert Nealey, qui gagne la revanche l'année suivante.
1965Défaites face à Walter Hellman et Derek Oldbury.
1967Second article : tables de signatures et alpha-bêta.
1977Le programme de l'université Duke bat le grand maître Elbert Lowder dans une partie hors tournoi, mais perd le match.
1989Début du projet Chinook à l'université d'Alberta.

La suite, des matchs contre Marion Tinsley à la preuve de 2007 que le jeu parfait mène à la nulle, est racontée dans notre article sur Chinook, l'IA qui a résolu les dames anglaises.

Ce qu'il faut retenir

Le jeu de Samuel se joue sur ce site : joue aux dames en ligne contre l'ordinateur et choisis « 8×8 anglaises » parmi les variantes, à l'un des quatre niveaux. Il cherche avec l'alpha-bêta, mais n'apprend rien de tes parties : à toi de trouver ses faiblesses. Les règles complètes de chaque variante sont dans notre guide des règles du jeu de dames.

Sources

À lire aussi

← Retour au blog Jouer aux Dames
Nouveautés 1/6
Voir tous nos défis du jour
Tu aimeras aussi
Voir tous les jeux →