Quand une IA joue un coup aux échecs, elle ne choisit pas forcément la meilleure solution. Randy Fath / Unsplash, CC BY-SA

Pourquoi l’intelligence artificielle se trompe tout le temps

En mai 1997, Garry Kasparov, maître incontesté des Échecs, affronte un programme d’intelligence artificielle. L’adversaire est de taille : 1 mètre 80 de haut, 1,4 tonne de composants électroniques, et une vingtaine d’ingénieurs informaticiens pour faire fonctionner la bête. Capable de calculer plus de 100 millions de positions par seconde, Deep Blue est forcément impressionnant. Pourtant, Garry Kasparov a toutes ses chances et il le prouve en remportant la première manche. Mais dans la deuxième, tout bascule. La machine prend l’avantage après un 36e coup qui empêche Kasparov de menacer son roi. Le champion d’échec est alors mis en difficulté, la machine prend progressivement l’ascendant. Mais soudain, au 44e coup, Deep Blue commet une erreur. Une erreur terrible, inexplicable, qui aurait pu sauver Kasparov en lui assurant une partie nulle ! La machine déplace son roi sur la mauvaise case et, au lieu de s’assurer une victoire, elle offre à son adversaire une porte de sortie.

Pourtant, Kasparov ne croit pas à l’erreur de la machine. Il pense qu’il n’a pas vu quelque chose, que la machine ne peut pas se tromper. Pas si grossièrement. Il ne saisit pas cette opportunité qui lui est donnée. Il se dit peut-être qu’il a loupé quelque chose. Au 45e coup, il abandonne la partie.

Quand le champion d’échecs Gary Kasparov est battu… par la machine Deep Blue (Public Sénat).

La réaction de Garry Kasparov immédiatement après ce match est intéressante. Il accuse l’équipe de Deep Blue d’avoir triché, d’avoir fait appel à un joueur humain pour le battre. Pour le champion du monde, aucune machine n’aurait pu à la fois jouer l’excellent 36e coup et commettre cette erreur grossière au 44e. C’est donc forcément un joueur humain qui a dicté ce coup à Deep Blue. Comme beaucoup de non-spécialistes, Kasparov ne croit pas que la machine puisse être à ce point faillible. Il est à mille lieues de la vérité.

La théorie de la complexité

Les programmes d’intelligence artificielle, comme tous les programmes informatiques, obéissent à certains principes mathématiques incontournables. Les spécialistes regroupent ces principes sous le nom de « théorie de la complexité ».

Pour comprendre cette théorie, il faut se rappeler qu’un programme informatique correspond simplement à une séquence de calculs effectuée par une machine. Chaque programme nécessite donc un certain nombre d’opérations pour calculer une réponse à un problème donné, qu’il s’agisse de trouver le meilleur coup pour jouer aux échecs ou de déterminer l’action à produire sur le système de conduite d’un véhicule autonome. Ainsi, un ordinateur individuel construit en 2020 est capable de faire quelques milliards de calculs à chaque seconde. C’est à la fois gigantesque (combien de temps faut-il au cerveau humain pour effectuer une seule addition de deux nombres ayant plusieurs dizaines de chiffres) et ridiculement petit à l’échelle de la théorie de la complexité.

Le nombre d’opérations qu’un programme informatique doit effectuer pour calculer une réponse peut en effet rapidement atteindre des valeurs astronomiques. Au sens propre du terme. Prenons le cas des échecs. Pour déterminer à coup sûr le coup gagnant, il faudrait regarder toutes les parties possibles, chaque joueur jouant alternativement l’une de ses 16 pièces sur le plateau de 64 cases. Au milieu du XXe siècle, le mathématicien Claude Shannon a estimé qu’il y a environ 10 puissance 120 parties d’échecs possibles. Cela s’écrit avec un 1 suivi de 120 zéros. Pour vous donner la mesure de ce nombre, il est des milliards de milliards de fois plus grand que le nombre total d’atomes dans tout l’univers. Prenez le temps de réfléchir à ce que cela représente… Même avec des machines dont la puissance de calcul continuerait de doubler tous les deux ans, comme le stipule la loi de Moore, nous sommes encore très loin de construire un ordinateur qui serait capable d’énumérer toutes ces parties avant de tomber en ruine (sans même parler de les jouer).

Mais il y a pire. La théorie définit la complexité d’un problème comme le nombre d’opérations que mettrait le meilleur programme imaginable pour donner une réponse exacte à ce problème. Cette complexité peut être purement théorique : il arrive qu’on n’ait pas encore trouvé l’algorithme capable de l’atteindre. Mais c’est une limite infranchissable. Quoi qu’il arrive, aucune méthode de résolution basée sur le calcul ne pourra jamais descendre en dessous. Lorsque cette complexité est trop grande, comme c’est le cas pour le problème « trouver le coup gagnant à coup sûr aux échecs », c’est qu’il est impossible, quelle que soit la méthode utilisée, de construire un programme informatique qui y réponde sans y passer des millénaires. Et c’est là que l’intelligence artificielle intervient.

L’intelligence artificielle pour des solutions imparfaites

En effet, s’il est impossible d’avoir une solution exacte en un temps raisonnable, rien n’interdit d’écrire un programme qui ne calcule pas la solution exacte, mais une autre solution, a priori moins bonne. Les chercheurs en intelligence artificielle appellent ce type de calcul une « heuristique ». L’objectif de ces programmes est alors de calculer une solution raisonnablement correcte au problème, dans un temps de calcul qui reste acceptable. C’est avec cette méthode que nous pouvons écrire des programmes capables de jouer correctement aux échecs. Ou de résoudre la plupart des problèmes auxquels s’attaque l’intelligence artificielle, qu’il s’agisse de jeux, de contrôle de véhicules autonomes, de traduire un texte de l’anglais au français ou de reconnaître le visage d’une personne sur une image.

L’ordinateur calcule alors un résultat, dans un temps qui est acceptable pour nous. Mais nous ne sommes certains que d’une chose : rien ne garantit que ce résultat soit le meilleur. Ainsi, il est impossible de vérifier que le coup proposé par Deep Blue est forcément gagnant (cela nécessiterait des millions d’années de calcul). Avec un peu de chance et d’adresse de la part des programmeurs, on peut espérer que le coup proposé sera un bon choix. Voire un très bon choix. Suffisamment pour battre le champion du monde. Mais ce ne sera certainement pas le coup parfait. Ou, si ça l’est, nous ne le saurons jamais…

Le principe des programmes d’IA est donc de calculer des solutions pas trop mauvaises à des problèmes dont on sait, mathématiquement, qu’ils ne peuvent pas être résolus de façon exacte dans un temps de calcul raisonnable. Et pour cela, il faut accepter de faire parfois des erreurs. De ne pas avoir toujours la meilleure réponse, ou une réponse complètement correcte. C’est pourquoi tout programme d’IA fait forcément des erreurs. C’est inévitable et c’est même ce qui les caractérise. Pour trouver des solutions à ces problèmes donc la complexité est trop élevée, ils construisent des heuristiques aussi bonnes que possible. Mais quel que soit le programme d’IA, système à base de règle, réseau de neurones ou toute autre méthode restant à inventer, il ne s’agit que d’une heuristique. Donc d’un programme qui peut se tromper.

Est-il alors raisonnable de monter dans un véhicule autonome ? La question est légitime, lorsqu’on sait que la complexité du problème est trop élevée et donc qu’il est impossible d’écrire un programme informatique qui ne fasse jamais d’erreur lorsqu’il décide d’une action sur le véhicule. Mais on peut aussi se demander si ce programme fait plus d’erreurs que les conducteurs humains. Les progrès récents dans le domaine de l’IA permettent de réduire rapidement cet écart et il arrivera probablement un jour où les voitures autonomes seront plus sûres que celles conduites par les humains. Mais elles ne seront jamais infaillibles.


Cet article reprend et développe une intervention tenue dans le cadre d’une formation sur la transition numérique. Cette conférence a été donnée lors du cycle national de formation 2019-2020 de l’IHEST, l’Institut des hautes études pour la science et la technologie, par Nicolas Sabouret.

Want to write?

Write an article and join a growing community of more than 110,800 academics and researchers from 3,637 institutions.

Register now