Les Newsletters Interstices
Garry Kasparov (New York, octobre 1989) Photo © Pierre Nolot
    Niveau facile
    Niveau 1 : Facile

    Les échecs électroniques : histoire d’une confrontation entre l’humain et la machine

    Histoire du numérique
    Intelligence artificielle
    Qui n’a jamais entendu parler de la défaite de Garry Kasparov contre le programme Deep Blue ? Mais quelle place tient cet événement dans l’histoire des échecs électroniques ?

    New York, 11 mai 1997. Le champion du monde de jeu d’échecs, Garry Kasparov, abandonne dans la sixième et dernière partie du match qui l’oppose depuis une semaine au programme Deep Blue, tournant sur un superordinateur conçu par une petite équipe de chercheurs d’IBM. Le score du match, 3,5 points contre 2,5 en faveur du programme, consacre la défaite inattendue de l’un des plus brillants joueurs d’échecs de tous les temps face au monstre cybernétique qui calcule environ deux cent millions de coups à la seconde.

    L’impact de ce résultat est considérable dans le monde entier. Toute la presse internationale titre sur l’événement et tente de comprendre comment le « génial » Kasparov a pu perdre ce match contre un adversaire qu’il avait largement dominé quinze mois plus tôt à Philadelphie sur le score de 4 à 2. L’action IBM gagne 10 % à la bourse de New York. Les experts financiers estiment que cette victoire de son programme fait gagner environ cent millions de dollars à la prestigieuse firme américaine. Kasparov touche quatre cent mille dollars pour sa défaite, il aurait gagné un million de dollars s’il avait gagné.

    Tous les experts échiquéens font immédiatement remarquer que Kasparov n’a pas joué à son niveau habituel, que dans la deuxième partie il a abandonné dans une position qu’il aurait très bien pu annuler et que dans la sixième et dernière il a joué comme un débutant ! Le monde échiquéen se console en se disant qu’il y aura obligatoirement une « belle » dans un an ou plus, et que le prestigieux champion humain, large vainqueur du monstre quinze mois plus tôt et battu de peu lors de cette revanche, sera cette fois mieux préparé techniquement et psychologiquement. Nul doute qu’il l’emportera et remettra la machine à sa place. Hélas, il n’en sera rien. Kasparov se montre très mauvais perdant. Il met en cause la régularité de l’affrontement, insinue que certains coups n’ont pas été joués par l’ordinateur mais par un très fort joueur humain qui aurait soufflé les coups à son adversaire électronique. Il cite même le nom du joueur en question, son prestigieux rival détesté, Anatoly Karpov, auquel il a pris le titre mondial douze ans plus tôt, et qu’il a affronté ensuite à nouveau à trois reprises dans des matchs fratricides pour la conservation de son titre. Il accuse purement et simplement l’équipe d’IBM d’avoir triché pour le battre ! Ces accusations sont tellement absurdes qu’IBM aurait pu les traiter par le mépris, proposer un troisième match en 1998 ou 1999 et continuer de développer à la fois son programme et la machine sur laquelle il tourne, pour l’emporter cette fois de manière indiscutable.

    Mais telle n’est pas la décision d’IBM. Considérant qu’il a gagné son pari de battre le meilleur joueur du monde dans un match disputé à la régulière, IBM met un terme au développement de Deep Blue qui ne jouera plus jamais une seule partie d’échecs !

    Comment en est-on arrivé là ?

    Entre 1947, date à laquelle le mathématicien anglais Alan Turing met sur papier l’idée d’un programme informatique qui pourrait jouer aux échecs, et le 11 mai 1997, date de la victoire de Deep Blue sur Kasparov, un demi-siècle de développement des programmes et des ordinateurs s’est écoulé. En voici l’histoire.

    Dès la création des premiers ordinateurs, les chercheurs ont eu l’idée d’écrire des programmes capables de jouer au plus prestigieux des jeux de réflexion, les échecs. Ils ont très rapidement compris que l’entreprise n’allait pas être simple, car les trente-deux pièces qui se déplacent sur un plateau de soixante-quatre cases donnent lieu à une multitude de possibilités. Le premier coup de la partie, toujours joué par les pièces blanches, offre déjà le choix entre vingt possibilités, même chose pour la réplique des pièces noires. Il y a donc quatre cents positions différentes rien que pour le premier coup d’une partie. Au fur et à mesure que les pièces sont jouées, le nombre des coups possibles augmente pour atteindre en moyenne trente-cinq coups en milieu de partie, mais parfois beaucoup plus, de cinquante à soixante. Ce qui fait que l’on a pu évaluer à environ 10130 le nombre de parties possibles aux échecs. On comprend ainsi aisément que malgré les formidables progrès de la puissance des ordinateurs d’aujourd’hui (et de demain), il ne sera sans doute jamais possible d’obtenir de l’ordinateur la réponse à la question fondamentale que se posent tous les joueurs d’échecs depuis quinze siècles que ce jeu existe : est-ce que, si les deux camps pouvaient jouer de manière parfaite, la partie serait nulle ou bien les blancs l’emporteraient-ils ? (sachant que le fait de jouer le premier coup pour les pièces blanches constitue un avantage démontré statistiquement).

    Deux écoles se sont opposées dans les années 1960, 1970 : les partisans de la « force brute » contre ceux de l’intelligence artificielle. Ces derniers, conduits par le chercheur français Jacques Pitrat, estimaient que le nombre astronomique des coups possibles dans une partie vouait à l’échec la « force brute ». Ils préconisaient de développer des « systèmes experts » capables de copier les raisonnements humains. L’absence de résultats dans ce domaine, conjuguée aux progrès fulgurants des programmes basés sur la « force brute », a fait disparaître cette approche.

    Tous les programmes d’échecs utilisent aujourd’hui une approche de type « force brute » pour tirer parti de la puissance toujours plus grande des ordinateurs. Leur principe de base est de calculer tous les coups possibles et leurs conséquences à des profondeurs toujours plus grandes. En réalité, ils n’examinent pas la totalité des coups à chaque niveau de profondeur. Afin de réduire l’arbre des configurations à explorer, ils mettent en œuvre des algorithmes qui analysent les positions et coupent les branches issues des positions jugées moins favorables. Ces méthodes heuristiques de plus en plus sophistiquées prennent en compte un nombre de plus en plus élevé de paramètres. C’est là qu’interviennent les talents des programmeurs, alliés à l’expertise des champions. Il est donc devenu impropre d’utiliser l’expression « force brute ». En fait, ces programmes utilisent énormément d’intelligence, celle des programmeurs, que les machines utilisent avec leurs capacités toujours plus grandes de force de calcul.

    Dans un jeu infiniment moins compliqué que les échecs, les checkers ou dames anglaises, qui se jouent aussi sur un damier de soixante-quatre cases, dont trente-deux seulement sont utilisées, avec douze pions pour chaque camp, on sait depuis 2007 que si les blancs et les noirs jouent de manière parfaite, la partie est nulle. C’est l’équipe de Jonathan Schaeffer, de l’université d’Alberta, qui a développé le programme qui le démontre (voir l’article d’Interstices : La fin des Dames anglaises ?).

    Des programmes de plus en plus performants

    C’est en Amérique du Nord qu’ont été développés dans les années 60 presque tous les premiers programmes d’échecs. Les soviétiques, qui dominaient très largement les échecs mondiaux à l’époque (il y avait plus de joueurs d’échecs en Union Soviétique que dans tout le reste du monde), développèrent avec succès le programme Kaissa, mais ils étaient handicapés par leur retard en matière d’informatique.

    En août 1968, le maître international anglais David Levy, qui occupe environ le 500e rang mondial, parie 1 250 livres sterling avec cinq chercheurs américains qu’à échéance de dix ans, aucun programme informatique ne sera capable de le battre aux échecs. Il ne croit alors pas du tout à la possibilité qu’un jour un programme puisse s’imposer contre les plus forts joueurs humains. Il déclare : « L’idée d’un champion du monde électronique d’échecs appartient seulement aux pages d’un livre de science fiction ».

    La décision de créer en 1970 un championnat annuel d’Amérique du Nord de programmes d’échecs va beaucoup contribuer au développement des échecs électroniques. Le premier voit la participation de six programmes, tous développés par des universités américaines. C’est le programme de la Northwestern University, Chess 3.0, qui l’emporte. Il gagne ensuite de la même façon en 1971, 1972 et 1973, sans jamais perdre une seule partie. En 1974 est organisé à Stockholm le premier championnat du monde des programmes d’échecs. À la surprise générale, c’est le programme russe Kaissa qui l’emporte… sans toutefois battre le programme Chess 4.0 qu’il n’a pas affronté parce que celui-ci a perdu contre un autre programme américain, Chaos. De plus, le très faible nombre de parties rend les résultats peu significatifs.

    Trois ans plus tard, à Toronto, lors du deuxième championnat du monde, le programme de la Northwestern University, Chess 4.6, ne laisse pas échapper la victoire et réalise un score parfait de quatre points sur quatre… sans avoir rencontré Kaissa, le tenant du titre, qui a perdu contre le programme américain Duchess dans une partie demeurée célèbre.

    diagramme 1

    Au 34e coup, Duchess vient de jouer Dame a8 échec au Roi. Tous les spectateurs dans la salle considéraient comme évident que le programme russe allait jouer 34… Roi en g7 pour se soustraire à l’échec. Or à la surprise générale, Kaissa joua Tour e8, perdant sa Tour et la partie. Tout le monde crut que Kaissa était victime d’un bogue, d’une erreur dans sa programmation. Il fallut plusieurs minutes avant qu’un joueur, plus perspicace que les programmeurs présents qui étaient tous d’assez médiocre niveau aux échecs, explique que Kaissa n’était nullement bogué, mais qu’il avait joué ce coup pour ne pas se faire immédiatement mater par la spectaculaire combinaison suivante : 34…Rg7 35.Df8 échec au Roi, sacrifice de la Dame ! 35…Rxf8 36.Fh6 échec au Roi 36… Fg7 seul coup 37.Tç8 échec 37…Dd8 38.Txd8 échec 38…Té8 39.Txe8 mat.

     
    Kaissa a évalué qu’il était préférable de donner sa Tour plutôt que de se faire mater. Tous les meilleurs programmes d’aujourd’hui, considérés comme bien plus forts que le champion du monde humain, font la même chose dans cette situation. À l’inverse, aucun joueur fort ne fait une chose pareille. La perte de la Tour ne laisse aucune chance de sauver la partie. En revanche, il existe une chance, aussi minime soit-elle, que les Blancs ne voient pas le sacrifice de Dame qui leur permet de mater. Voilà une des rares situations où l’intelligence humaine demeure, aux échecs, supérieure à la force de calcul de la machine.

    Chess 4.6 ayant remporté ce second championnat du monde des programmes confirmait qu’il était bien le meilleur programme mondial. Il s’affirmait ainsi comme le challenger tout désigné pour affronter au mois d’août 1978 David Levy, avec bien sûr beaucoup plus d’enjeu que les 1 250 livres sterling pariées. Le maître anglais ne jouait pratiquement plus aux échecs en compétition et son niveau de jeu avait nettement baissé depuis 1968. Il demeurait cependant très optimiste quant à l’issue de la confrontation qui devait se dérouler sur six parties à Toronto du 26 août au 5 septembre 1978.

    Dans la première partie, le maître anglais commit une grosse faute dès le 12e coup et se retrouva rapidement dans une situation complètement perdante. Ce fut alors au programme Chess 4.7 d’accumuler les erreurs et la partie fut finalement nulle en 64 coups. David Levy avait eu chaud et il décida désormais d’adopter sa stratégie mise au point depuis longtemps face aux divers programmes : « ne rien faire, mais le faire bien ! ». Autrement dit, ne prendre aucun risque, développer tranquillement ses pièces et attendre que le programme affaiblisse sa propre position.

    Ce plan connut un plein succès dans les deuxième et troisième parties, gagnées facilement par Levy en raison des fautes de la machine.

    Avec un score de 2,5-0,5, il était désormais certain de gagner son pari, puisqu’il lui suffisait de marquer un demi-point lors des trois dernières parties.

    Pour redonner un peu de piquant à la confrontation, le maître décida de prendre des risques dans la quatrième partie et d’aller sur le terrain de prédilection de son adversaire : la tactique. Comme dans la première partie, il fut dominé par la machine et ne parvint pas cette fois à rétablir l’équilibre.

    Le score était désormais de 2,5-1,5. Le suspense s’arrêta là, car David Levy, ne voulant plus prendre le moindre risque, reprit la stratégie qui lui avait si bien réussi dans les 2e et 3e parties et l’emporta dans la 5e. Il prit alors un nouveau pari de 1 000 dollars sans échéance dans le temps… et sans illusion. Il savait qu’à moyen terme, il allait être dépassé par l’amélioration des programmes et l’augmentation rapide de la capacité de calcul des ordinateurs. Il réaffirmait toutefois que les machines n’avaient aucune chance d’arriver au niveau du champion du monde humain (Anatoly Karpov à l’époque).

    Le règne du programme de la Northwestern University prend fin en 1980, lors du 3e championnat du monde disputé à Linz en Autriche. Chess 4.9 n’y prend que la 5e place. C’est le programme Belle, développé par Bell Telegraph Telephone, qui l’emporte de peu et qui sera considéré comme le plus fort pendant trois ans, avant d’être battu à son tour par le programme Cray Blitz en 1983 lors du 4e championnat du monde. Ce programme tourne sur le super calculateur Cray X – MP et c’est surtout sa très grande capacité de calcul qui lui permet de dominer ses adversaires électroniques.

    Trois ans plus tard, il l’emporte encore lors du 5e championnat, mais en perdant une partie sur les cinq disputées et en ne marquant pas plus de points que les 2e, 3e et 4e. Son règne est terminé.

    En cette même année 1986, au mois de novembre, le 17e championnat d’Amérique du Nord des programmes est remporté par le revenant Belle avec le score parfait de cinq points sur cinq. On fait peu de cas d’un nouvel arrivant, ChipTest, qui termine modestement 11e sur 16. Ce programme est développé par trois étudiants de l’université Carnegie Mellon de Pittsburgh, Feng-hsiung Hsu, Thomas Anantharaman et Murray Campbell.

    Moins d’un an plus tard, en octobre 1987, ce même programme appelé désormais ChipTest-m gagne le 18e championnat d’Amérique du Nord en gagnant toutes ses parties dont celle contre Cray Blitz en 27 coups avec les pièces noires.

    Un an plus tard, lors du 19e championnat d’Amérique du Nord, ChipTest a changé de nom, il s’appelle désormais Deep Thought 0.02. Il gagne l’épreuve.

    Du 28 au 31 mai 1989 se déroule à Edmonton, au Canada, le 6e championnat du monde des ordinateurs d’échecs. Il oppose vingt-quatre programmes, un record. Deep Thought survole l’épreuve, il gagne toutes ses parties. David Levy profite de la présence de toute la fine fleur des programmeurs et autres experts pour leur poser par écrit la question « En quelle année pensez-vous qu’un programme d’échecs sera capable de battre le champion du monde humain ? » Les quarante-trois spécialistes doivent répondre sans connaître les réponses des autres. Les plus optimistes donnent 1992. Un seul répond : jamais, et il ne s’agit pas de David Levy, qui pronostique 2014. Seul Français présent, j’ai répondu 2005, qui constitue aussi la moyenne des quarante-deux réponses chiffrées.

    Il est désormais indiscutable que Deep Thought est de loin le plus fort programme au monde. Une première confrontation avec le champion du monde Garry Kasparov est organisée à l’Académie des Arts de New York le 23 octobre 1989 par Shelby Lyman, qui avait été l’artisan de la médiatisation du match de championnat du monde opposant Bobby Fischer à Boris Spassky en 1972. Deux parties disputées le même jour à un rythme inhabituel : 1 h 30 mn pour chacun tout au long de la partie. Kasparov écrase consciencieusement son adversaire électronique d’abord avec les noirs, puis avec les blancs. Les six cents spectateurs dans la salle sont ravis, ils sont à 95 % des supporters de Garry.

    Deux mois plus tard, à Londres, c’est au tour de David Levy d’affronter Deep Thought dans un match de quatre parties. Comme il fallait s’y attendre, le maître, ne jouant pratiquement plus, n’a pas le niveau et se fait étriller dans les quatre parties. Pari perdu cette fois.

    IBM a visiblement suivi de près les performances de ChipTest, devenu Deep Thought, et embauche les trois étudiants désormais diplômés, Murray Campbell en septembre 1989, Feng-hsiung Hsu en octobre 1989 et Thomas Anantharaman en février 1990. Ceux-ci vont travailler pendant sept ans au centre de recherche d’IBM, à 40 km de New York. Ils vont pour l’essentiel mettre au point une machine capable de calculer environ deux cent millions de coups par seconde. Cette machine constituée de 256 processeurs travaillant en parallèle pourra ensuite servir à bien d’autres usages. Pour la partie purement échiquéenne du projet, IBM fera appel à plusieurs Grands Maitres dont le champion américain Joël Benjamin et le champion espagnol Miguel Illescas. Durant ces sept années, Deep Thought qui changea encore de nom pour s’appeler par la suite Deep Blue affronte divers Grands Maîtres dans des matchs exhibitions avec des fortunes diverses. Il bat par exemple le grand champion danois Bent Larsen dans un Open américain en 1989, mais ce dernier prendra sa revanche dans un match de quatre parties gagné 2,5-1,5 en 1993.

    Kasparov contre Deep Blue

    Garry Kasparov affrontant Deep Blue en février 1996.
    Photo © Pierre Nolot.

    Lorsque, du 10 au 17 février 1996, Kasparov affronte Deep Blue dans un match de six parties à Philadelphie, il n’est pas très inquiet. Il pense l’emporter facilement. Mais en perdant la première partie dans laquelle il s’est laissé entraîner dans des positions tactiques favorables à la machine, le champion du monde a vite compris qu’il allait falloir jouer beaucoup plus serré que prévu. Il s’est très bien repris dans la deuxième remportée facilement. Les troisième et quatrième parties se terminent par le partage du point et les deux adversaires sont à égalité à deux parties de la fin. En dominant très largement Deep Blue dans les cinquième et sixième parties, Kasparov pense avoir « remis les pendules à l’heure » pour longtemps.

    diagramme 2

    Il n’est par conséquent pas particulièrement inquiet lorsqu’il affronte à nouveau ce même adversaire, qui a cependant doublé sa vitesse de calcul, quinze mois plus tard. En remportant assez facilement la première partie, Kasparov a toutes les raisons de penser que ce match ne sera pas plus difficile à gagner que celui de l’année précédente. Mais la deuxième partie va le déstabiliser psychologiquement. Après avoir tranquillement récité une quinzaine de coups inscrits dans sa bibliothèque d’ouvertures, Deep Blue va prendre l’avantage et maintenir le champion du monde dans une position inférieure pendant une trentaine de coups. Le programme sera pourtant loin de jouer de manière parfaite. Il ratera le gain aux 44e et 45e coups (voir le diagramme ci-contre). Kasparov prend alors la décision stupéfiante… d’abandonner. Ce n’est que plusieurs heures plus tard qu’un de ses secondants osera suggérer qu’il aurait peut-être pu essayer de jouer De3 ! Énormément d’analyses de la position ont été produites et concluent que ce coup aurait permis à Kasparov d’annuler cette partie et de continuer à mener dans le match. Cela demeure le seul exemple de l’abandon d’un champion du monde dans une position probablement nulle.

    Dans les parties suivantes, les 3e, 4e et 5e, Kasparov a tenté avec beaucoup d’énergie de reprendre le contrôle du match. Il a obtenu certaines positions supérieures, mais aucune gagnante. Avant la 6e et dernière partie, les deux adversaires sont par conséquent à égalité 2,5-2,5. Ayant les pièces noires dans cette partie, Kasparov aurait pu tout faire pour assurer le partage du point. Il prit au contraire le risque de jouer une défense qu’il ne pratiquait plus depuis de très nombreuses années. De plus, il joua au 7e coup une variante considérée comme inférieure. Au 11e coup, la partie est déjà quasiment perdue pour lui. Le champion du monde abandonne au 19e coup. Cette partie est sans aucun doute la plus faible disputée par Garry Kasparov entre 1977 et 1997. Aucune explication plausible n’a été donnée à ce jour sur cette déroute.

    Deep Blue a pris place au musée (Computer History Museum, Californie).
    Photo © James the photographer.

    Après avoir manifesté sa mauvaise humeur et avoir quasiment accusé l’équipe de Deep Blue d’avoir triché, Kasparov a réclamé à IBM un troisième match. IBM a refusé. Le but que la grande firme américaine s’était fixé était atteint, leur machine avait battu le champion du monde. Elle n’avait rien à gagner à tenter de confirmer une victoire obtenue avec pas mal de chance. De l’avis général, Kasparov mieux préparé techniquement et psychologiquement aurait sans doute eu de réelles chances de reprendre le dessus pendant encore quelques années.

    Considérant qu’il a gagné son pari de battre le meilleur joueur du monde dans un match disputé à la régulière, IBM a mis en 1997 un terme au développement de Deep Blue, lequel ne jouera plus jamais une seule partie d’échecs. La firme s’est alors lancée dans un tout autre projet, baptisé Watson, concevoir un ordinateur capable de l’emporter au Jeopardy, jeu télévisé de questions-réponses !

    La supériorité de Deep Blue sur les autres programmes était devenue si manifeste depuis 1989 que les différents projets sur les grosses machines dans les universités n’avaient plus grand intérêt et furent abandonnés, à l’exception d’Hydra, un programme de l’autrichien Christian Donninger financé par l’émirat d’Abu Dhabi. Ce projet avait clairement pour but de prendre la succession de Deep Blue et de défier les meilleurs joueurs du monde. Au mois de juin 2005 eut lieu à Londres un match de six parties entre Hydra et le meilleur joueur anglais, le Grand Maître Michaël Adams, septième joueur mondial. Le joueur devait toucher vingt-cinq mille dollars par partie gagnée et dix mille dollars par partie nulle. À l’issue des six parties, Adams a gagné… dix mille dollars, vous aurez donc compris qu’il perdit cinq parties et en annula une seule. Hydra, qui calculait avec ses soixante-quatre processeurs environ deux cent millions de coups par seconde, comme Deep Blue, mais dont le programme échiquéen était certainement meilleur que celui d’IBM, n’avait plus d’adversaire humain à sa taille. Son développement fut abandonné en 2006 faute désormais de but à atteindre.

    Des programmes à la portée de toutes les bourses

    Le développement des programmes sur les gros ordinateurs a beaucoup intéressé les dizaines de millions de joueurs du monde entier. Mais ces programmes avaient un gros inconvénient, ils n’étaient pas accessibles : on pouvait prendre connaissance de leurs performances, de leurs parties, mais pas jouer contre eux. L’arrivée sur le marché de microprocesseurs à partir de 1977 devait complètement changer la donne. Plusieurs firmes commerciales virent tout le profit qu’elles pourraient tirer de la vente de machines dédiées exclusivement à la pratique du jeu d’échecs. Une firme américaine spécialisée dans les prothèses électroniques, Fidelity Electronics, s’empara la première du marché. Puis des concurrents, la firme allemande Mephisto, les firmes hong-kongaises Novag et Saitek, mirent en vente de nombreux modèles à tous les prix.

    Machines dédiées au jeu d’échecs. À gauche, modèle Mephisto mobil (1985), à droite, Novag Super Forte C (1987) (collection Éric Gallula).
    Photo © Inria / Christian Tourniaire.

    Les premières machines jouaient très mal, mais comblaient déjà l’immense majorité des joueurs amateurs. Afin d’évaluer objectivement les forces respectives de ces beaux jouets, de nombreuses confrontations furent organisées, tant entre machines qu’entre machines et joueurs humains.

    À titre d’exemple, une compétition entre six machines du marché et six joueurs français classés fut organisée par la grande librairie échiquéenne de Paris, la librairie Saint-Germain, en avril 1982. Dans la partie opposant le programme allemand Mephisto à Philippe Boulanger, rédacteur en chef de la revue « Pour la science », ce dernier avait plutôt raté le début de partie et se trouvait dans une situation désespérée (voir le diagramme ci-dessous).

    diagramme 3

    Il tenta alors le coup de la dernière chance 19. Tour aé1 ! Mephisto n’a qu’un seul objectif, mater son adversaire. Il joue 19… Fou f3 ?? pour donner mat au coup suivant par Dame g2.
    Mais l’humain a vu plus loin que la machine et joue 20. Dame é8 échec, sacrifiant sa Dame. Les Noirs n’ont qu’un seul coup 20… Tour prend Dame é8. Et les Blancs continuent à donner du matériel : 21. Tour prend Tour é8 échec au Roi. Les Noirs n’ont qu’un seul coup 21… Tour prend Tour é8 et Philippe Boulanger n’a plus qu’à donner mat 22. Tour prend Tour é8.

     

     
    Le programme Mephisto a été victime de ce que l’on appelle l’effet horizon. Le programme n’a pas vu assez profond, il subit le « mat du couloir ». Le programme disposait d’environ trois minutes pour jouer chaque coup. J’avais alors fait l’expérience de mettre la position en question et de laisser tourner la machine jusqu’à ce qu’elle découvre le danger mortel qu’il y avait à laisser son Roi dans le couloir. Il lui avait fallu un peu plus de trois heures pour comprendre la menace. Aujourd’hui, aucun programme ne tombe plus dans ce piège, même avec une seule seconde de temps d’analyse.

    Des dizaines de modèles de machines dédiées aux échecs ont été mises sur le marché de 1978 à 1993, chaque année voyant la sortie d’un programme plus fort ou offrant des fonctions nouvelles. Mais petit à petit, ces machines, qui avaient l’inconvénient de coûter souvent assez cher, ont été supplantées par des programmes, d’abord sur disquettes, puis sur DVD.

    Des programmes toujours plus forts que les joueurs humains ?

    Les meilleurs programmes actuels sont vendus environ 50 € s’ils sont destinés à tourner sur un ordinateur mono processeur, et 100 € si vous voulez utiliser toute la puissance de calcul d’un quadri processeur (certains peuvent être téléchargés gratuitement sur internet en toute légalité). Ils ont pour nom Houdini, Rybka, Stockfish, Shredder, Fritz, Hiarcs, Critter et sont tous beaucoup plus forts que ne l’était Deep Blue en 1997, lorsqu’il battit Kasparov.

    En force tactique, les programmes sont incommensurablement plus forts que les meilleurs joueurs mondiaux.

    diagramme 4

    En voici un exemple (auteur : Iosif Krikheli – voir le diagramme ci-contre).
    Les blancs jouent et font mat en… 17 coups.
    Il faut moins d’une seconde aux programmes actuels pour vous annoncer ce mat et l’ensemble des coups :
    1. Cc2 , Rb3 ; 2. Cd4 , Ra3 ; 3. Cc4 , Ra4 ; 4. Cb6 , Ra3 ; 5. Cc2 , Rb3 ; 6. Ca1 , Ra3 ; 7. Fd6, f5 ; 8. Cc2 , Rb3 ; 9. Cd4 , Ra3 ; 10. Cc4 , Ra4 ; 11. Cb2 , Ra3 ; 12. Cc2 , Rb3 ; 13. Ca1 , Ra3 ; 14. Fc5, Tc6 ; 15. Td3, Txc5 ; 16. Cc2 , Rb3 ; 17. c4 mat

     

     
    Mais il existe encore des positions dans lesquelles même un joueur de force moyenne peut faire beaucoup mieux que le plus fort programme du monde. Ce sont les positions qui nécessitent de faire un plan à long terme, ce qu’aucun programme n’est encore capable de faire actuellement. Regardez cette position assez simple (voir le diagramme suivant). Sachez qu’aucun programme au monde, même en tournant pendant vingt-quatre heures, n’est capable de trouver comment gagner avec les pièces blanches.

    diagramme 5

    Vous constatez d’abord que les noirs sont paralysés malgré leur avantage matériel (Dame contre Fou et Cavalier). Le plan des blancs est simple, prendre le pion d7 et promouvoir ensuite le pion d6. Quelle pièce va pouvoir prendre le pion d7 ? Pas le Fou, puisqu’il n’est pas de la bonne couleur. Pas le Roi, parce que le pion est protégé par la Dame noire. C’est donc le Cavalier qui va prendre en d7, à condition d’être protégé par son Roi. Mais si le Cavalier quitte la case d8, la Dame noire pourra s’échapper de la nasse dans laquelle elle se trouve. Poser le problème, c’est le résoudre : il faut maintenir l’enfermement de la Dame adverse en substituant le Fou au Cavalier. En pratique, mener le Roi en e7 sans couper la diagonale du Fou, par exemple : Roi e4, f5, g6, f7 et e7. Ensuite, mettre le Fou sur une case qui empêchera la Dame de sortir, en f8 : Fou h6, f8. En sept coups, vous avez libéré le Cavalier pour qu’il puisse remplir son office : prendre le pion d7, ce qui est accompli en trois coups : Cavalier f7, e5 et prise du pion d7. En dix coups, vous avez pris le pion d7 et ouvert la voie à la promotion de votre pion d6. Ce plan simple, aucun programme n’est capable de le trouver à ce jour.

     
    Malgré les extraordinaires progrès accomplis en quarante ans, il reste encore beaucoup de pain sur la planche pour que les programmes jouent un jour de manière parfaite. Et encore bien des stratégies à mettre en œuvre par les meilleurs joueurs du monde afin de tenter de reprendre la main !

    • How computers play chess de David Levy et Monty Newborn, publié en 1991 aux Etats-Unis par Computer Science Press
    • Kasparov versus Deep Blue Computer Chess Comes of Age de Monty Newborn, publié en 1997 aux États-Unis par Springer New York (Attention, ce livre a été écrit et publié avant le match de mai 1997, les six parties du match Kasparov-Deep Blue ne s’y trouvent donc pas)

    Trois sites Web pour les passionnés d’échecs électroniques :

    Merci à Éric Gallula pour la réalisation des diagrammes.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Pierre Nolot

    Journaliste spécialiste du jeu d'échecs.
    Voir le profil

    Ces articles peuvent vous intéresser

    ArticleIntelligence artificielle
    Algorithmes

    Programmation des échecs et d’autres jeux

    Olivier Teytaud

    Niveau intermédiaire
    Niveau 2 : Intermédiaire