Petite histoire des matches homme-ordinateur

A quelques jours du match opposant Vladimir Kramnik au logiciel Deep Fritz, voici, comme promis un petit historique de ce genre de rencontres. La première confrontation entre un homme et un programme se fit... sans ordinateur. On doit l'expérience au mathématicien britannique Alan Turing (photo ci-contre), un des pères de l'informatique. Turing, célèbre pour avoir dirigé l'équipe qui, durant la Deuxième Guerre mondiale, décryptait les messages allemands codés par la machine Enigma, avait en effet écrit, en 1952, un programme d'échecs mais il ne disposait pas à l'époque d'une machine suffisamment puissante pour le faire tourner. Il décida donc... de la remplacer et d'effectuer lui-même les calculs nécessaires, ce qui prenait environ une demi-heure par coup. Le logiciel perdit la partie contre Alick Gleenie, un des collègues de Turing. Ceux qui ont envie de rejouer cette partie historique, disputée à Manchester, peuvent la trouver sur ce site.
En parallèle avec les travaux exploratoires de Turing, un autre des pères de l'informatique, l'Américain Claude Shannon, établit les bases des logiciels d'échecs, toujours appliquées aujourd'hui. L'idée est relativement simple : étant donné qu'une machine n'a pas les qualités humaines qui permettent, avec un minimum d'expérience, d'éliminer un certain nombre de coups absurdes, il faut profiter de son seul atout, la puissance de calcul, pour envisager tous les coups possibles, toutes les réponses possibles, toutes les réponses aux réponses possibles, etc. Evidemment, l'arborescence est très vite foisonnante et il faut l'agrémenter d'une fonction d'évaluation, qui donne une valeur à tous les coups et les classe. La valeur de chaque position est fonction du matériel restant sur l'échiquier, de la sécurité du roi, de la structure des pions, du dynamisme des pièces, etc. Evidemment, Shannon s'aperçut que les lignes possibles augmentaient très rapidement avec la profondeur de recherche et envisagea une stratégie sélective, qui permettait de "couper" des branches de l'évaluation, sachant qu'elles menaient à des impasses. Les chiffres donnent en effet le vertige. Dans un milieu de partie ouvert, une quarantaine de coups sont possibles de part et d'autre. Si l'on envisage un coup et sa réponse (deux demi-coups disent les spécialistes), il faut évaluer 40x40 possibilités, soit 1600 positions. Si l'on passe à 4 demi-coups, cela donne 40⁴ possibilités, soit 2 560 000 positions. Si l'on passe à 6 demi-coups (trois coups de chaque côté, ce qui n'est pas énorme), on trouve le chiffre de 4,1 milliards d'éventualités... Il apparut très clairement, dès le début, que les performances échiquéennes des ordinateurs seraient directement liées à leur vitesse. Le nombre de parties différentes jouables selon les règles en vigueur est généralement estimé à 10¹²⁰ (un 1 suivi de 120 zéros), soit beaucoup plus que le nombre d'atomes présents dans l'Univers...
La première partie d'un ordinateur a cinquante ans. Elle a été jouée en 1956 dans le très fermé laboratoire de Los Alamos, en plein désert du Nouveau-Mexique, où les Etats-Unis avaient installé un calculateur, Maniac I (photo ci-contre), destiné au développement des bombes atomiques. Un instrument dont les performances pouvaient être testées à des fins moins belliqueuses (quoique...) avec un logiciel d'échecs. Pour économiser du temps de calcul, les fous avaient été retirés de l'échiquier, lequel n'avait plus que 36 cases (6x6) au lieu de 64 (le double pas du pion et le roque n'étaient pas autorisés). On fit tout d'abord jouer l'ordinateur contre... lui-même. Les pièces blanches gagnèrent. Puis on lui opposa un bon joueur lequel, malgré le handicap d'une dame, remporta la partie. Enfin, la troisième et dernière rencontre vit Maniac I battre une jeune femme qui venait d'apprendre les règles du jeu. C'était la première victoire (assez peu méritoire, il faut bien le dire), d'un logiciel joueur d'échecs contre Homo sapiens.
Après ces balbutiements, Américains et Soviétiques (sous la houlette, notamment, de l'ancien champion du monde Mikhaïl Botvinnik) développèrent un certain nombre de programmes et, dans la deuxième moitié des années 1980, ceux-ci commencèrent à atteindre un niveau plus qu'acceptable, quand on les opposait au tout venant des joueurs. En revanche, ils faisaient encore piètre figure contre les grands champions. Ainsi, en 1985, Garry Kasparov joua une simultanée à Hambourg contre 15 programmes et gagna 15-0. En 1989, Deep Thought (programmé par des étudiants de l'université américaine Carnegie-Mellon), qui venait de remporter le championnat du monde des machines, rencontra son homologue de chair et de sang. Un carnage sanglant s'ensuivit : Kasparov gagna 2-0 en montrant que la profondeur de sa stratégie faisait plus que contrebalancer les calculs de la boîte de conserve.
Mais ce n'était qu'une question de temps. Avec l'augmentation quasi linéaire de la puissance de calcul, le fossé entre le silicium et nos petites cellules grises ne pouvait que se combler. Et ce d'autant plus vite que le géant IBM s'était lancé dans la bataille contre Kasparov, en finançant les développeurs de Deep Thought dont le successeur, Deep Blue, s'annonçait comme un monstre de calcul. Le match en 6 parties qui se tint à Philadelphie faisait donc figure de grand spectacle. Le champion du monde n'avait, claironnait-il, d'autre objectif que de défendre la "dignité" humaine. Il savait à peu près ce qui l'attendait. En 1994, il avait pour la première fois été battu (en partie rapide) par un logiciel, Chess Genius 2. De plus, Deep Blue n'était pas un simple ordinateur du commerce mais un calculateur colossal, dont les microprocesseurs travaillant en parallèle permettaient d'analyser entre 50 et 100 milliards de positions en trois minutes. L'"Ogre de Bakou" perdit la partie inaugurale du match : pour la première fois dans l'histoire du jeu, un champion du monde était défait par une machine en rythme classique. Heureusement pour le genre humain, le Russe se reprit et sut trouver les failles du programme. Il gagna le match par 4 points à 2 (3 victoires, 2 nulles et 1 défaite), misant notamment sur l'effet d'horizon, c'est-à-dire en mettant sur pied des stratégies (détérioration de la chaîne de pions adverse, par exemple) dont il savait que les effets se feraient sentir assez tard dans la partie, au-delà de l'horizon de calcul et d'évaluation de la machine.
En mai 1997, IBM revint à la charge avec un Deep Blue amélioré (photo ci-contre), Deeper Blue. Le match en 6 parties se joua cette fois à New York dans une ambiance de paranoïa qui ne fit rien pour améliorer les performances du Russe. Celui-ci commença par se plaindre d'être "dans une obscurité absolue : le secret sur les parties jouées par mon adversaire a été mieux gardé que les informations les plus confidentielles du Pentagone." Après le début du match, il soupçonna l'équipe d'IBM d'avoir recours en cachette à l'aide d'un grand maître pour diriger les 256 microprocesseurs de la bête de silicium. Le Russe gagna de belle manière la première partie mais prit une leçon de jeu positionnel dans la deuxième. J'étais à New-York, dans le public de l'Equitable Center où se déroulait l'événement. Quelques étages en-dessous de la salle de jeu, les spectateurs, dans le brouhaha et un climat bon enfant, applaudissaient aux coups et donnaient leur avis sur tout, rigolaient aux grimaces traditionnelles de Kasparov, qui se tortillait, visiblement mal à l'aise.
Voici un extrait de mon compte-rendu dans Le Monde : "Kasparov, en retard au temps, lorgne sur la pendule avant de lancer, en direction de l'ingénieur qui lui fait face, un de ses fameux regards assassins dont il a le secret et qui ont fusillé moralement plus d'un joueur de chair. A ces brefs instants de rébellion succède une sorte d'abattement. Avachi au fond de son fauteuil, engoncé dans son costume trois-pièces, le teint terreux, il semble chercher une aide, les yeux dans le vague. Sa ligne Maginot prend l'eau. Pour acharnée qu'elle soit, sa résistance ne sert plus à grand-chose. Il sait qu'il ne fera pas nulle. Enfoncées au plus profond de sa défense, la dame et la tour de Deeper Blue tournicotent dangereusement autour de lui, Garry Kasparov, roi aux abois méchamment attaqué. En un éclair, il tend la main à l'ingénieur, signe sa feuille, se lève et sort du champ de la caméra. (...) Quelques étages plus bas, le public applaudit à tout rompre. Un spectateur, très ému, exprime au micro sa sensation "d'avoir vécu là un moment d'histoire". Les représentants de la race humaine, dont le champion du monde voulait se faire le défenseur, réservent une standing ovation à l'équipe d'IBM. Aucun ne se montre triste de voir une des dernières frontières du vivant céder sous les coups de brute qu'assène la machine. Pour Kasparov, tout est à refaire. Un jour de repos pour se reconstruire un moral pourrait lui suffire. Il a quitté l'Equitable Center sans mot dire. Il est terriblement seul." J'ai souvent rencontré Garry Kasparov. Je connais son égo hypertrophié, son caractère difficile, son impatience, en bref beaucoup de ses défauts. Mais, ce jour-là, pour la première fois, j'ai eu pitié de lui.
Sa paranoïa ne fit que se renforcer lorsqu'il s'avéra qu'il disposait, dans cette deuxième partie, d'un coup paradoxal qui aurait pu forcer la nulle par échec perpétuel après sacrifice d'une pièce. Le Russe se demanda comment la machine avait pu lui laisser cette sortie de secours (qu'il n'avait pas vue). "Comment peut-il, à quelques coups de distance, jouer comme un champion et commettre une bourde ? (...) C'est étrange", insinua-t-il après la troisième partie. Il n'y avait probablement rien d'étrange mais le doute était dans son esprit et le champion du monde ne put élever son niveau de jeu. Complètement cuit, il lâcha la sixième et dernière partie du match, pris dans un piège théorique qu'il était pourtant censé connaître. C'était la première fois que le champion du monde perdait un match contre une machine. Dans un commentaire publié au lendemain de sa défaite, j'écrivais ceci : "Le match de New York permet en réalité de démontrer une bonne fois pour toutes, n'en déplaise aux pousseurs de bois, que le jeu d'échecs n'a rien d'intelligent. (...) A vrai dire, Deeper Blue, comme tous ses homologues, ne sait que compter. Mais cela, il le fait à merveille. Il ignore même qu'il joue aux échecs... Garry Kasparov aurait-il gagné, il n'aurait fait que repousser l'inéluctable, qui arrive simplement avec un peu d'avance sur l'heure prévue. Le Russe n'est plus que champion du monde des hommes. Pour être triste, la nouvelle, tout compte fait, met fin à un suspense artificiel. Maintenant que la machine a franchi une nouvelle frontière, les joueurs du jardin du Luxembourg ou d'ailleurs peuvent tranquillement retourner autour de leur carré de cases blanches, de cases noires et de leur peuple de bois. Et jouer."
Bien d'autres rencontres ont eu lieu depuis 1997. En 2002, Vladimir Kramnik a fait match nul contre Deep Fritz, 4-4. En 2003, Kasparov a fait de même contre Deep Junior (3-3). Par la suite, les choses ont moins bien tourné pour les représentants de l'espèce humaine. En 2005, Michael Adams, pourtant un abonné au Top 10 mondial, se faisait laminer par le programme Hydra, 5,5 points à 0,5. Quelques mois plus tard, trois des récents "champions du monde" de la FIDE, Rouslan Ponomariov, Alexandre Khalifman et Roustam Kazimdjanov affrontaient un trio de programmes (Hydra, Junior et Fritz). Résultat, un impressionnant 8 points à 4 pour les tas de ferraille. Seul Ponomariov fut capable de remporter une partie. Tout l'enjeu est là désormais. Gagner un match contre un logiciel semble presque impossible en raison de la fatigue et du stress. Mais gagner une partie peut suffire à prouver que l'homme n'a pas dit son dernier mot.