Comment Claude Shannon proposait-il qu’un ordinateur joue aux échecs?

Avant même qu’un ordinateur ait joué une seule partie d’échecs, Claude Shannon a décrit par écrit comment il pourrait le faire. Son article, « Programming a Computer for Playing Chess », est court et facile à lire, et pourtant il expose la méthode qu’ont utilisée les programmes d’échecs pendant des décennies : donner à la machine une façon approximative de juger une position, la laisser imaginer les coups à venir et lui faire supposer que l’adversaire répondra toujours le mieux possible.

Shannon était mathématicien et ingénieur aux Bell Telephone Laboratories, à Murray Hill, au New Jersey, et déjà célèbre pour avoir fondé la théorie de l’information, les mathématiques de la transmission efficace des messages. Il a présenté pour la première fois ses travaux sur les échecs au National IRE Convention, à New York, le 9 mars 1949. (L’IRE, l’Institute of Radio Engineers, était une association professionnelle d’ingénieurs électriciens.) La version écrite a paru dans la revue Philosophical Magazine en mars 1950.

Pourquoi les échecs?

Shannon ne s’intéressait pas vraiment à une machine à jouer aux échecs pour elle-même. Il l’a dit d’entrée de jeu : la valeur pratique était mince, mais résoudre les échecs pourrait ouvrir la voie à des machines qui conçoivent des circuits, acheminent des appels téléphoniques, traduisent des langues ou font des déductions logiques. Toutes ces tâches demandent du jugement et des essais et erreurs, pas seulement de l’arithmétique.

Les échecs, soutenait-il, étaient le banc d’essai idéal. Les coups et le but y sont parfaitement clairs. Le jeu n’est ni trivialement facile ni désespérément difficile. Et l’on s’entend généralement pour dire que bien y jouer demande de la réflexion; un programme réussi nous obligerait donc soit à admettre que les machines peuvent penser en un certain sens, soit à restreindre ce que nous entendons par penser.

Le problème des coups trop nombreux

En principe, un ordinateur pourrait jouer parfaitement en examinant toutes les suites possibles jusqu’à la fin de la partie. Shannon a montré pourquoi c’est hors de question. Une position typique offre environ 30 coups légaux; un coup de chaque camp donne donc environ un millier de possibilités. Sur une partie d’environ 40 coups, cela représente quelque 10 puissance 120 variantes différentes. Même en vérifiant une variante par millionième de seconde, le premier coup à lui seul prendrait plus de 10 puissance 90 années.

Le but n’était donc pas de jouer parfaitement. C’était de jouer habilement, peut-être aussi bien qu’un humain de bon niveau.

La recette de Shannon : noter, puis chercher

Le premier ingrédient est une fonction d’évaluation, une formule qui attribue un nombre à n’importe quelle position : positif si elle semble bonne pour les Blancs, négatif si elle semble bonne pour les Noirs. L’exemple de Shannon comptait le matériel avec les valeurs que les joueurs d’échecs connaissaient déjà (dame 9, tour 5, fou et cavalier 3, pion 1), retranchait un peu pour les structures de pions faibles et ajoutait un peu pour la mobilité, c’est-à-dire le nombre de coups dont dispose un camp. Il insistait sur le fait qu’elle était grossière et n’avait de sens que dans les positions calmes, pas au milieu d’un échange de pièces.

Le deuxième ingrédient est l’anticipation. La machine examine chacun de ses coups, puis chaque réplique, et ainsi de suite jusqu’à une profondeur fixe. Au bout de chaque ligne, elle applique la fonction d’évaluation. Puis elle remonte : au tour de l’adversaire, elle suppose la réplique la pire pour elle; à son propre tour, elle choisit la meilleure. Prendre le minimum d’un côté et le maximum de l’autre, voilà pourquoi on appelle aujourd’hui cette méthode minimax.

Voici un tout petit exemple, avec deux coups possibles pour les Blancs et deux répliques pour les Noirs :

Le coup A peut mener à +3, mais des Noirs attentifs répondront par la réplique 2, laissant les Blancs à -2. Le coup B garantit au moins +1. Minimax choisit le coup B : non pas le coup au meilleur résultat possible, mais celui qui donne le meilleur résultat face à une bonne défense.

Type A et type B

Shannon a vu qu’examiner tous les coups à la même profondeur, ce qu’il appelait une stratégie de type A, serait lent et faible. Regarder trois coups à l’avance pour chaque camp exigerait environ un milliard d’évaluations par coup, soit plus de seize minutes chacun, même à une vitesse très optimiste.

Il a proposé une stratégie plus astucieuse, de type B, calquée sur la façon dont pensent les bons joueurs. Suivre les coups forcés, comme les échecs au roi et les prises, plus loin que les coups tranquilles. Ne s’arrêter que lorsque la position s’est stabilisée. Et écarter tôt les coups manifestement inutiles, en prenant soin de ne pas rejeter ceux qui ont seulement l’air mauvais à première vue. Il a ajouté des touches que d’autres programmes ont adoptées par la suite : un répertoire d’ouvertures classiques en mémoire, et un petit élément de hasard pour que la machine ne répète pas la même partie perdante.

Il était franc sur le point faible : une telle machine n’apprendrait pas de ses erreurs. Seul un meilleur programme pourrait l’améliorer.

En quoi les programmes d’échecs d’aujourd’hui diffèrent-ils du plan de Shannon?

Pendant la plus grande partie des cinquante années suivantes, les programmes d’échecs ont suivi de près le plan de Shannon : une fonction d’évaluation écrite par des humains, plus une recherche minimax. Les premiers programmeurs préféraient son approche sélective de type B, mais dans les années 1970, du matériel plus rapide et de meilleures techniques de recherche ont rendu plus forte la recherche profonde de style type A. Deep Blue, d’IBM, qui a battu le champion du monde Garry Kasparov dans un match de six parties en mai 1997, appartenait encore à cette famille de programmes qui combinent une formule de notation et une recherche profonde.

Le grand changement est venu récemment. En 2017, AlphaZero, de DeepMind, a appris à juger les positions d’échecs avec un réseau de neurones plutôt qu’avec une fonction d’évaluation écrite à la main et, dans un match de 100 parties, il a battu le meilleur programme classique, Stockfish, sans perdre une seule partie. Il a aussi remplacé le minimax classique par une autre recherche, fondée sur l’échantillonnage.

En un sens, AlphaZero répond à la faiblesse que Shannon avait relevée en 1949. Sa machine ne pouvait pas apprendre; le jugement d’AlphaZero sur les positions est entièrement appris. Pourtant, l’ossature de son plan reste visible : une façon de juger les positions, et une recherche parmi les avenirs possibles qui suppose un adversaire compétent.