Comment un programme de dames a-t-il appris seul à battre un maître du jeu ?

Le programme de dames d'Arthur Samuel a appris en jouant, notamment des milliers de parties contre lui-même, jusqu'à battre en 1962 Robert Nealey, un « maître » des dames autoproclamé. Samuel, ingénieur chez IBM, avait lancé le projet en 1949. En 1959, il a donné un nom à ce que faisait son programme : l'apprentissage automatique (machine learning). C'est un programme qui apprend à partir de données et généralise, au lieu de suivre seulement les étapes qu'on lui a données.

Le programme explorait un arbre de positions possibles sur le damier. Il notait chacune avec une formule qui pesait les pions, les dames et la distance des pions avant d'être couronnés. Puis il choisissait le meilleur coup, en supposant que l'adversaire jouait lui aussi au mieux. L'apprentissage venait par-dessus. Il retenait les positions déjà vues et si elles avaient mené à une victoire ou à une défaite. Des versions ultérieures ajustaient aussi la formule à partir de parties de professionnels, et de milliers de parties contre elles-mêmes.

Cette victoire célèbre mérite une note de bas de page. C'était une seule partie, et les résultats suivants du programme contre des humains furent mitigés. Il atteignit un niveau amateur respectable, le premier programme à jouer aussi bien à un jeu de plateau. Mais il était loin de maîtriser les dames. Une seule victoire a suffi pour donner au public l'impression qu'il était très fort.

Son idée centrale se retrouve aujourd'hui dans des outils du quotidien. Un filtre de messagerie, par exemple, apprend à partir d'exemples étiquetés dans quel dossier ranger chaque nouveau message. Ce pouvoir s'accompagne d'un piège classique : le surapprentissage. Un modèle qui mémorise ses données d'entraînement, bruit compris, peut réussir tous les exemples déjà vus puis échouer sur tout ce qui est nouveau, comme un élève qui a appris par cœur un seul sujet d'entraînement.