L'HISTOIRE DES ORDINATEURS D'ECHECS

 

La conception d'un ordinateur d'échecs pose un passionnant problème technique évoqué il y a 55 ans par Claude Shannon, le fondateur de la théorie de l'information : "l'étude informatique du jeu d'échecs sert à mettre au point des techniques utilisables dans des applications plus pratiques. La recherche d'un ordinateur jouant aux échecs est un point de départ idéal pour plusieurs raisons. Le problème est bien défini, tant en ce qui concerne les opérations autorisées (le déplacement des pièces) que l'objectif (le mat) ; il n'est ne trop simple ni trop complexe. En opposant la machine réalisée à un être humain, on obtient une évaluation claire des capacités de la machine dans ce type de raisonnement."

Les ordinateurs qui jouent aux échecs démontrent surtout l'efficacité de l'analyse par ordinateur. L'amélioration des techniques utilisées aux échecs fera notamment progresser la conception des réseaux, la modélisation moléculaire en chimie, et l'analyse linguistique.

L'histoire des machines jouant aux échecs commença par une supercherie : vers 1770, le baron Wolgang von Kempelen (ingénieur autrichien) présenta en Europe un automate joueur d'échecs qui fut surnommé le Turc, car il se présentait sous l'aspect d'une marionnette enturbannée et moustachue, qui aurait été actionné par un mécanisme complexe, situé dans un coffre sous l'échiquier.

  

 

Le Turc jouait bien et mit un jour Napoléon en fureur ne le battant en 19 coups. A la mort de Kempelen en 1804, le Turc fut racheté par le musicien bavarois Johann Maelzel qui continua de l'exploiter par de nombreuses exhibitions notamment en Amérique. Edgar Poe attiré par le phénomène, fut surpris d'une défaite du Turc et annonça alors qu'il ne s'agissait pas d'un ordinateur puisque ce dernier est imbattable.

Poe avait découvert la supercherie mais pour une mauvaise raison, un ordinateur est battable, mais il avait vu vrai car la supercherie consistait bien à dissimuler un fort joueur sous l'échiquier qui par un jeu de miroir,  observait les pièces et pouvait contrôler les mouvements de l'automate. Ainsi, une dizaine de joueurs ce sont remplacés au service du Turc.

Maëzel  mourut en 1838 et le Turc fut dévoilé par un de ses opérateurs, sa place était désormais dans un musée (Philadelphie) ou il disparut  dans un incendie en 1854.

Le mathématicien britannique Alan Turing fut l'un des premiers à étudier l'informatisation du jeu d'échecs, mais préférait faire tourner son programme à la main pour évaluer les positions et calculer les coups à jouer. L'Allemand Konrad Zuse et quelques chercheurs réalisèrent également des programmes d'échecs, mais le travail le plus profond fut celui de Claude Shannon : il utilisa la théorie des jeux de John von Neumann et d'Oskar Morgenstern afin de déterminer, par la méthode du "minimax", le meilleur coup possible.

La fonction d'évaluation

L'algorithme de Shannon considère, pour un nombre fixe de coups des deux joueurs, toutes les positions résultantes possibles ; il évalue les positions, et, en fonction des valeurs obtenues, détermine le "meilleur" coup à jouer. Le programme de base est un "générateur de coups" qui détermine tous les coups jouables à partir d'une position, et toutes les ripostes que l'adversaire peut proposer. Il explore ainsi un arbre, où chaque position est reliée aux positions suivantes autorisées par les règles du jeu.

Chaque niveau de l'arbre des positions comporte environ 38 fois plus de positions que le niveau précédent : on réduit le nombre de positions à examiner par un étalage appelé "alpha-béta". Le programme évalue les positions aux extrémités des branches de l'arbre ; l'évaluation des positions tient compte de la valeur des pièces restant sur l'échiquier et des menaces qui pèsent sur elles ; il donne une valeur de 1 quand l'adversaire est mat et -1 quand l'ordinateur est mat, et attribue des valeurs intermédiaires aux positions rencontrées en cours de jeu. La fonction d'évaluation, cruciale pour la qualité du programme, peut tenir compte des positions des pièces à l'aide de paramètres précisant la localisation des pièces et la répartition générale des forces.

On améliore le jeu d'un ordinateur qui utilise cette stratégie, soit en augmentant la profondeur de son analyse (le nombre de demi-coups qu'il simule avant d'évaluer les positions), soit en perfectionnant sa fonction d'évaluation. Le jeu de l'ordinateur serait parfait si l'on pouvait examiner toutes les suites possibles de demi-coups jusqu'au mat ou à la partie nulle : on verrait alors la machine stupéfier son adversaire en annonçant, dès le premier coup : "blanc joue e4 et gagne en 137 coups maximum". Cela n'arrivera pas : l'analyse exhaustive est possible dans les jeux simples comme le morpion ou puissance 4, mais elle est impraticable aux échecs où 10 puissance 120 parties distinctes sont possibles. Le jeu serait également parfait, après l'examen d'un seul coup, si l'évaluation des positions était aussi bonne que celle revendiquée par José Raoul Capablanca, champion du monde en 1920 : "je ne prévois qu'un coup à l'avance" disait il "le meilleur".

La force brute

Les premiers programmes de jeux d'échecs, établis vers 1958, étaient encore rudimentaires car il fallut d'abord programmer les règles du jeu. Seulement huit ans plus tard, le programme MackHack 6 de Richard Greenblatt, de l'institut de technologie du Massachussets, put enfin jouer honorablement dans les tournois locaux.

Progressivement de plus en plus nombreux, les auteurs de programmes d'échecs se divisèrent en deux camps de philosophies distinctes : les "stratèges" et les "mécaniciens". Les stratèges considéraient que les ordinateurs devaient jouer comme l'Homme, à l'aide de raisonnements explicites décidant des coups. Les mécaniciens avaient un point de vue moins restrictif, admettant que des opérations correctement effectuées par l'Homme pouvaient ne pas être adaptées aux caractéristiques des ordinateurs et que ceux-ci devaient utiliser leurs propres avantages, c'est à dire leurs facilités de calcul. Initialement, la stratégie était plus à la mode.

Dans les années 1970, les mécaniciens s'imposèrent : on découvrit alors que les performances des programmes étaient quasi proportionnelles au nombre de demi-coups anticipés. Chaque fois qu'on augmentait la profondeur d'analyse d'un demi-coup, l'ELO augmentait de 200 points. Les programmeurs utilisèrent alors des ordinateurs de plus en plus rapides et cherchèrent à accélérer les calculs spécifiquent de leurs programmes sur les ordinateurs classiques.

Programmer la recherche des positions n'est cependant pas tout ! Les premiers programmes d'échecs recensaient les positions sans discernement, et ne distinguaient pas des suites de coups qui conduisaient à la même position par interversion de coups. On élimine aujourd'hui ce doublons en enregistrant les positions successives dans des tables qui servent également à éliminer de nombreuses suites de coups sans intérêt.

Quand le programme doit-il cesser d'examiner une branche de l'arbre de jeu ? S'il ne peut explorer indéfiniment chaque branche, il doit au moins ne pas s'arrêter à une position instable (en plein milieu d'un échange de pièces par ex). Supposons que l'ordinateur analyse huit demi-coups sur chaque branche et qu'il découvre une position où la perte d'un pion lui ferait gagner un Cavalier. L'avantage ne serait qu'apparent si, au coup suivant, l'adversaire prenait le Cavalier de l'ordinateur, gagnant ainsi un pion au total.

Cet "effet horizon", comme on le nomme, conduisit parfois des ordinateurs à des suicides échiquéens, auxquels mêmes des débutants humains ne se livrent pas : soudain et sans raison apparente, l'ordinateur commence à sacrifier ses pions et ses pièces, sapent sa position. Afin de se préserver de tels errements, la plupart des programmes actuels prolongent la recherche de base par une recherche d'équilibre : celle-ci examine les captures de pièces jusqu'à obtention d'un équilibre où une évaluation censée est possible.

La force brute prévalut dans les années 1970 et  le début des années 1980, parce que l'on obtenait de bons résultats en appliquant habilement les stratégies de recherche de base et de recherche d'équilibre. Progressivement adaptés aux nouvelles générations d'ordinateurs, le programme Chess 4.0 et ses améliorations successives, dues à des informaticiens de l'université Northwestern, l'emportèrent presque sans discontinuer sur tous les autres programmes. L'Elo augmenta régulièrement jusqu'à ce qu'il atteigne 2000 en 1979.

A cette époque apparurent des ordinateurs spécifiques, construits pour jouer aux échecs. Le plus célèbre, Belle, des laboratoires Bell, atteignit le niveau 2200 Elo en 1983. La force brute culmina en 1986 avec Cray Blitz, qui était exécuté par des superordinateurs dont 64 microprocesseurs (un pour chaque case de l'échiquier). Cray Blitz gagna le championnat du monde d'ordinateurs d'échecs en 1986, où il battit Hitech à la dernière ronde. Cray Blitz et Hitech examinaient respectivement 100 000 et 120 000 positions par seconde.

Pensée profonde

L'histoire de Deep Thought commence en 1985 avec F. Hsu  à partir des travaux de l'armée américaine sur une puce spécialisé et du générateur de Belle. Par Deep Thought, l'ère de la force brute s'achevait et, aujourd'hui, la plupart des programmes de pointe effectue certaines recherches séléctives.

Deep Thought (250 puces et 2 processeurs capable d'évaluer 750 000 positions par seconde. Profondeur 5 coups. ELO estimé : 2450) battit le grand maître Bent Larsen dans un tournoi, c'était le début de la fin, il fallait désormais compter avec l'évolution des logiciels et des processeurs. Il faut préciser qu'il s'agissait d'un tournoi en blitz (cadence rapide) la fébrilité, les gaffes humaines ne faisait pas le poids face à la rigueur des logiciels et à sa vitesse de réflexion qui est plus déséquilibré en cadence rapide.

 

Ses concepteurs parlent de Deep Thought :

"Malgré le maigre bagage échiquéen (900 parties de Maîtres analysées) dont nous l'avons doté, il bat d'excellents joueurs humains. Tout d'abord parce que l'ordinateur ne copie pas la pensée humaine ; il atteint les mêmes fins par des voies différentes, mieux adaptés à ses capacités. Deep Thought voit loin, mais observe peu ; il se rappelle de tout, mais n'apprend rien ; il ne faiblit jamais, mais ne progresse pas. Toutefois il découvre aussi, parfois des combinaisons que les GMI ne voyaient pas."

 En octobre 1989, un nouveau prototype, à six microprocesseurs, de Deep Thought joua deux parties en public contre Kasparov, à New York. L'ordinateur analysait plus de 2 millions de positions par seconde, mais Kasparov le battit nettement.

Le 2 février 1990, Deep Thought se produisit à nouveau en public contre Karpov cette fois. Les concepteurs avaient tiré les leçons de la défaite en 1989 contre Kasparov, Deep Thought, grâce à une fonction d'évaluation nettement amélioré, joua une de ses meilleurs parties jusqu'au 50 ème coup où arriva une énorme erreur.

Fort de ces expériences, les quatre concepteurs de Deep Thought planche déjà sur le futur Deep Blue. On connaît tous la victoire de ce dernier sur Kasparov en 1997, voilà ce que disait les quatre compère dès 1990 :

"Au centre de recherche d'IBM de Yorktown Heights, nous cherchons à rendre les nouvelles versions plus rapides : nous nous efforçons d'augmenter la puissance de calcul d'un facteur supérieur à 1000. La machine que nous prévoyons examinera plus d'un milliard de positions par seconde, de sorte que la profondeur de son analyse atteindra 14 ou 15 demi-coups dans la plupart des cas et 30 à 60 dans les situations forcées. Le classement Elo estimé est de 3400 Elo, 800 points au-dessus de la version actuel et 500 points au dessus du record de Kasparov. F.Hsu conçoit aujourd'hui une puce spécifique pour le jeu d'échecs, qui analysera au moins trois millions de positions par seconde, T Anantharaman et M Campbell améliorent divers aspects de l'actuel Deep Thougt (notamment les fonctions d'évaluations)."

"Nous pensons que la prochaine version de Deep Thought (Deep Blue) sera assez rapide pour menacer le champion du monde "

Kasparov, à l'époque n'était pas du tout de cet avis, il a admis qu'un ordinateur analysant 1 milliard de positions par seconde pourrait battre un GMI moyen mais ni Karpov ni lui. Il maintient,  que la créativité et l'imagination humaines, notamment sa créativité et son imagination, triompheront à coup sûr du silicum.

"En fait, lors de la prochaine rencontre, le génie d'un individu suprêmement talentueux ne luttera pas seulement contre du silicum ; il affrontera le fruit du travail de centaines d'experts. Cette rencontre ne révélera pas si les machines peuvent penser, mais plutôt si un effort humain collectif peut surpasser les individus les plus doués." l'équipe de Deep Blue

Les rencontres suivantes :
1996 : Kasparov - Deep Blue : 4-2
1997 : Kasparov - Deep Blue : 2,5 - 3,5
2002 : Kramnik - Deep Fritz : 4-4
2003 : Kasparov - Deep Junior : 3-3
2003 : Kasparov - Fritz X3D : 2-2
 

1996 : Kasparov - Deep Blue

Deep Blue de 1996 mesurait 2m de haut et pesait 700 kg. Il s'agissait d'un super-calculateur IMB (RISC SYSTEM / 6000 Scalable POWER paralell Systems) dont chacun des 32 processeurs consacrés au calcul pur a été connecté à une carte comprenant 8 processeurs dédiés aux échecs, soit au total 256 processeurs spécialisés fonctionnant en parallèle.

1997 : Kasparov - Deep Blue

Résultats : 2,5 - 3,5

En 1997, Deep Blue pesait 1 tonne 4 et mesurait 1,80 m. Il fallait 20 personnes pour qu'il fonctionne. Beaucoup de choses ont été dites à propos de cette première défaite de Kasparov face à une machine. Kasparov a accusé IBM d'avoir introduit certains coups humains.....et alors....il est champion du monde des humains.....objection recevable mais pas déterminante.

 Nous aurions plutôt tendance à penser que ce sont les énormes gaffes de Kasparov qui ont causé sa perte, il a joué la peur au ventre. Sûr de sa suprématie, ce dernier n'était pas préparé comme il se doit face un ordinateur très fort. Kasparov a perdu et ces deux autres confrontations en 2003 n'ont pas abouti à une victoire. On pourra dire ce qu'on voudra, les logiciels sont très forts et peuvent bousculer voire battre n'importe quelle joueur. Certes, un plus grand nombre de partie seraient plus significatifs, mais là encore, Kasparov pourrait dire, à raison, que la machine, elle, ne se fatigue pas et n'éprouve aucune tension, elle ne sait même pas qu'elle joue aux échecs....

2002 : Kramnik - Deep Fritz (octobre 2002)

Résultat : 4 - 4 sur 8 parties.

1,95 m et 100 kilos ! et non ce n'est pas la machine mais Kramnik qui mesure 1.95 m ! la machine elle était un ordinateur avec 8  processeurs à 2,4Ghz et 256 Mo.

Cinq ans après la défaite de Kasparov face au Deep Blue d'IBM, la rencontre entre l'homme et la machine se solde par un nul : la domination initiale du champion du monde s'est vue réduite brutalement à mi-compétition sans remontée possible. Si le logiciel n'est pas un adversaire invincible, sa puissance de prédiction des coups et son insensibilité psychologique en ont fait un adversaire redoutable pour l'intuitivité et le génie du grand maître.

Contrairement à Gary Kasparov qui avait adopté une tactique d'imprévisibilité qui lui était peu naturelle et qui lui avait plus nui qu'à son adversaire, Vladimir Kramnik avait pris soin de jouer à sa manière habituelle. La ressemblance des deux premières parties avec les deux premières qui lui avaient offert le titre aux dépens de Gary Kasparov est assez parlante.
 

"Les machines s'améliorent, mais, nous aussi, les humains, nous apprenons." Kramnik

2003 : Kasparov - Deep Junior (janvier 2003)

Résultats : 3 - 3 sur 6 parties.

Garry Kasparov, le premier joueur sur l'échelle du classement mondial, a affronté Deep Junior dans les salons du New York Athletic club de Manhattan.A ce jour il est trois fois champion du monde des logiciels d'échecs ayant notamment remporté en juillet 2002 à Maastricht (Pays-Bas) le dernier championnat du monde réservé aux machines, s'imposant face à 18 autres programmes.

Le championnat du monde officiel contre ordinateurs se déroule - c'est une première - sous les hospices de la FIDE (Fédération international des Echecs) et de la ICGA (International Computer Game Association ).

En 1997, l'ordinateur d'IBM Deep Blue calculait près de 300 millions de coups par seconde. En 2003, Deep Junior calcule 3 millions de coups par seconde (100 fois moins !) mais il est aussi fort."La puissance pure n'est pas tout", a expliqué Amir Ban, l'un des créateurs de Deep Junior. "L'important est d'utiliser la puissance efficacement. La qualité des connaissances du jeu d'échecs que l'on place dans la machine est aussi importante".

2003 : Kasparov - Fritz X3D (novembre 2003) 2  :  2

 Ce logiciel a déjà un beau palmarès. Il a battu Deep Blue, Polgar, Kortchnoï, Adams, Deep Junior.
Une des particularités de cette rencontre est que Kasparov n'a pas à toucher les pièces du jeu, X3D Fritz répondant à sa seule voix. Pour jouer, Kasparov ordonne au logiciel de faire bouger les pièces sur un écran représentant l'échiquier. Il suit le match en relief grâce à ses lunettes spécialement conçues pour donner l'illusion des trois dimensions. X3D Fritz est la version améliorée de Fritz, le programme sans 3D contre lequel, en 2002, le Russe Vladimir Kramnik avait fait match nul (4-4). On peut parler d'une confrontation a distance.
 

Kasparov a déclaré :

"nous pouvons voir que les ordinateurs ont encore beaucoup à apprendre de nous".... 
"Je pense que le joueur humain a été dominant. Les deux défaites ont surtout été dues à de terribles, terribles maladresses liées à l'énorme pression. Je n'ai pas été mis hors jeu par les ordinateurs, et j'ai gardé l'initiative au cours des deux duels", a-t-il précisé, se disant "plutôt content du développement général de ces matches." "C'est toujours à moi de faire la différence. Si je ne commets pas de maladresse terrible, alors je dois gagner ou en tout cas ne pas perdre."

IDEES RECUES SUR LES PROGRAMMES D'ECHECS

1) Deep Blue a battu Kasparov, donc les ordinateurs sont désormais plus forts que les humains aux échecs.

FAUX. Simplification abusive. Le faible nombre de parties jouées par Deep Blue (6) et contre un seul adversaire de surcroît, ne permet pas de déterminer la force exacte de l'ordinateur d'IBM.

 

2) Un logiciel calcule "toutes les possibilités" pendant la partie.

FAUX. L'analyse exhaustive du jeu dépasse d'infiniment loin la capacité de calcul des plus puissants ordinateurs. 10 puissance 120 partie différente possible aux échecs.

 

3) Plus un programme est rapide a résoudre des combinaisons, plus il est fort en parties.

FAUX. Trouver le coup décisif dans une position déséquilibrée et jouer des coups plausibles pendant toute une partie sont deux choses différentes.

 

4) Les programmes sont faibles en finales.

FAUX. Les meilleurs logiciels ont désormais un niveau de jeu très élevé en fin de partie, notamment grâce à la profondeur de calcul atteinte dans les positions à matériel réduit. cf tablebases

 

5) Les programmes d'échecs font appel aux technique d'intelligence articifielle (IA).

FAUX. Malgré ce qui est parfois dit dans la presse, aucun programme d'échecs de haut niveau n'utilise des algorithmes de type IA

 

6) Les programmes sont toujours meilleurs tactiquement que les humains.

FAUX. Pas toujours. Les humains sont parfois plus efficaces lorsque le calcul combinatoire est concentré sur un petit nombre de variantes forcées et très profondes (attaque de mat..)