Du Turk à Deep Blue
« Si je perds, cela signifie que les ordinateurs nous menacent désormais dans les dernières sphères qui étaient sous contrôle humain, comme l'art, la littérature ou la musique ». Garry Kasparov, février 1996

Un défi de la sagacité

L'informatique est la plus extraordinaire technologie de communication inventée par l'homme. Son histoire se confond avec celle des échecs, langage universel. Au départ, qu'y a-t-il de plus binaire que de choisir ou non de jouer un coup donné ?
A cet instant décisif de sa réflexion, le joueur n'envisage plus qu'une alternative dans l'absolu : soit ce coup est bon et il devrait le guider sur le chemin de la victoire (1-0), soit ce coup est mauvais et sa conséquence immédiate ou à venir sera une défaite (0-1). C'est le gain ou la perte pure et simple de la partie qui est en jeu.
Les échecs ont toujours été assimilés à une lutte d'intelligence. Les joueurs éprouvent leur talent en se défiant les uns les autres. Autrement dit, avant la création du QI (Quotient Intellectuel), voire du QE (Quotient Emotionnel), les hommes n'avaient quasiment pas d'outils à leur disposition pour se mesurer intellectuellement... Si ce n'est les échecs, ce jeu royal dont la première vertu est d'échapper à l'emprise du hasard.
C'est la raison pour laquelle les princes, les seigneurs et plus généralement tous les souverains les plus puissants, en toutes contrées, prirent l'habitude d'inviter à leur cour les joueurs les plus renommés de leur temps. En les côtoyant, voire en leurs accordant des rentes financières, ces potentats se paraient des atours de leur sagacité.

L'ère scientifique du jeu

Enclenchons la vitesse supersonique pour parcourir le temps et mettons le cap sur le 18e siècle. Les philosophes des Lumières, à commencer par Rousseau, Diderot et Voltaire, révolutionnèrent les chiffres et les lettres. Tous trois étaient des pousseurs de bois passionnés.
Ils suivirent l'exemple prôné par Leibnitz, le mathématicien allemand, lequel déclara que « les échecs sont utiles à l'exercice de la faculté de pensée, tant nous devons posséder une méthode élaborée pour atteindre des buts partout où nous devons conduire notre raison ». Fréquentant le même sérail, les virtuoses français du Café de la Régence révolutionnèrent quant à eux le jeu des Rois.
L'un de ces champions était un musicien prodige âgé d'à peine 20 ans. Il imposa sa norme scientifique sur les échiquiers d'Europe. En 1749, le jeune François-André Danican Philidor (1726-1795) édita ses préceptes sous le titre de « L'Analyse des échecs ».
Son jeu préfigurait celui des futurs tenants de l'Ecole Moderne, dont Steinitz. Il était déjà méthodique, voire mécanique. Les parties devinrent pour ainsi dire froidement orchestrées. Philidor venait d'inaugurer l'ère scientifique des échecs.

De Philidor à Deep Blue

C'est une constante : les joueurs d'échecs ont toujours épousé rapidement les inventions majeures et les technologies émergentes. Depuis l'invention de l'imprimerie au 15e siècle, l'idée est sensiblement la même : véhiculer un savoir en abolissant les notions de distance et de temps.
Internet s'inscrit dans cette perspective, mais c'est un autre pan de la recherche fondamentale qui nous intéresse ici. Après l'avènement des dogmes de Philidor, les savants s'ingénièrent à croire au rêve chimérique d'un cerveau artificiel. Voici quelques étapes de ce long cheminement :
1769 : Le baron autrichien Van Kempelen invente le Turk, pseudo automate joueur d'échecs. Ironiquement, la supercherie (un joueur dissimulé dans le coffre) sera éventée par Mouret, un arrière petit-neveu de Philidor, en 1834.
1890 : Un premier pas décisif est franchi. La machine électro-mécanique du savant espagnol Leonardo Torres y Quevedo est capable, après une programmation savante, de jouer une finale Roi + Tour contre Roi dépouillé.
1950 : Le mathématicien américain Claude Shannon définit les bases de ce que sera la programmation échiquéenne. Il propose la méthode Minimax.
1951 : Le chercheur anglais Allan Turing crée le premier programme d'échecs expérimental. Ce même Turing avait réussi à déchiffrer le système de communication des Nazis (le fameux code « Enigma ») durant la seconde guerre mondiale.

« Le génie à l'épreuve de la logique » - Magazine IBM 1972

Les échecs, une valeur étalon

Après Turing, le postulat de la recherche scientifique devint le suivant : si un programme échiquéen est capable de rivaliser avec un joueur humain, cela signifiera que l'ordinateur a franchi un palier décisif dans le domaine fondamental de la prise de décisions.
Une nouvelle étape capitale est franchie le 25 mai 1961. Le Président John Fitzgerald Kennedy annonce officiellement devant le Congrès des Etats-Unis le lancement du programme Apollo.
Il est évident que les milliards de données mathématiques induites par un vol lunaire ne peuvent être gérées par un cerveau humain. C'est l'époque où les ordinateurs occupent des étages entiers d'un immeuble et consomment plus d'électricité que tout un quartier. Au delà de la conquête spatiale, il y a un autre enjeu stratégique particulier : les progrès accomplis par la science balistique à des fins militaires (les fameux missiles intercontinentaux).
Où l'on comprend mieux cette évolution clé : à mesure que l'informatique a opéré sa mutation, les échecs se sont profilés comme la référence idéale (si ce n'est la seule !) pour mesurer les progrès accomplis par les ordinateurs.
Corrélativement, les programmes échiquéens expérimentaux à l'Est et à l'Ouest ont bénéficié des avancées les plus spectaculaires mises au point par les informaticiens.

De l'effet Papillon à l'effet Horizon

Au début d'une partie, il existe 20 coups légaux possibles pour les Blancs (16 de pions, 4 de Cavaliers). Au final, il y a dans l'absolu 10 puissance 120 de parties différentes possibles.
Les GMI le savent mieux que quiconque : il est excessivement rare qu'il renouvelle deux fois la même partie durant leur carrière. Et pourtant, il leur arrive de jouer des milliers de fois les mêmes ouvertures !
Ce qui nous ramène à l'effet papillon (un seul coup transpose la partie vers une multitude de variantes nouvelles) et son corollaire : l'effet horizon, ce stade ultime à partir duquel le programme s'aveugle...
Repousser les limites de l'informatique pour repousser la frontière de l'espace. C'est donc ainsi que tout au long des années 1960, les experts américains et soviétiques se sont affrontés par programmes interposés : IBM Stanford contre Kaïssa.
Les soviétiques l'emportèrent à chaque fois. Il est d'ailleurs étonnant de constater que ces duels étaient permis. Nous étions à l'apogée de la Guerre Froide, et les rencontres entre scientifiques des deux blocs, à priori, étaient proscrites. Les secrets étaient jalousement gardés, mais les ingénieurs, joueurs et passionnés, n'ont jamais cessé d'échanger leurs savoirs...

Exposition Musée Suisse du Jeu - Copyright Manfred Rahs 2002

Une culture binaire

Afin de parvenir à leur fin, battre un joueur d'échecs, et pourquoi ne pas vaincre un jour le champion du Monde, les programmeurs ont nourri les cerveaux artificiels de leurs machines avec des pans entiers de la culture échiquéenne.
Les programmes ont été gavés de dizaines, de centaines de milliers, puis de millions de parties jouées par les plus forts amateurs et les plus grands champions de l'histoire. Cette mémoire sélective diablement efficace relève d'une forme d'autisme : la capacité de mémoriser une infinité de bases de données. Ce bourrage de crâne fut possible, car ces cerveaux n'étaient qu'artificiels.
Au final, les programmes les plus performants ont appris méthodiquement à réfuter les coups incorrects, puis les coups directement perdants, puis les coups les moins pertinents... jusqu'à ne prendre en considération durant leurs analyses que les lignes d'avantages ou au moins égales, ou clairement gagnantes !
Les ordinateurs ont atteint le plus haut niveau par mimétisme. Ils ont copié sans le comprendre le mode de réflexion si atypique des meilleurs représentants humains : en fondant leur décision sur « le souvenir » de schémas de position ancrés au plus profond de leur mémoire.
Le fait qu'un programme (Deep Blue) ait battu en match, en 1997, le meilleur joueur du monde (Kasparov) n'ôte rien au plaisir.
Ces outils sont stupéfiants ! Aujourd'hui, le phénomène informatique a été banalisé. Il permet aux amateurs de jouer chez eux contre un Super GMI virtuel (Fritz, Junior, etc.) ou encore de se mesurer aux meilleurs programmes en les affrontant sur les zones de jeux en ligne comme echecs.com.

Faites-vous la Main !

Deep Blue - G. Kasparov 2785
[B17] Défense Caro-Kann
Match Homme-Machine ronde 6, New York 1997

19.c4!
Et Kasparov abandonne, car après 19...bxc4, le seul coup, les Noirs s'écroulent par exemple sur 20.xc4 b4 21.e1 etc. Malgré trois pièces pour la Dame, les Noirs n'ont pas la moindre compensation. Leur Roi restera sous la menace d'une attaque mortelle et leurs pièces n'auront jamais le temps de trouver la moindre coordination. 1-0
Cette défaite signa la fin d'un long calvaire pour l'humain. Ce fut la première victoire en match d'un ordinateur contre le champion du Monde en titre.
Deux siècles après Van Kempelen, le vieux rêve chimérique des chercheurs s'était accompli...


Publié le 21/04/2006 - 22:00 , Mis à jour le 25/11/2006 - 13:17