Les ordinateurs d'échecs

L'histoire des machines joueuses d'échecs n'attend pas le développement de l'électronique et de l'informatique : la première fut l'automate turc, autour de 1770, qui joua notamment contre l'impératrice Catherine II et Napoléon Bonaparte. C'était en fait un homme de petite taille caché dans la machine.

Le turc

Puis viens Ajeeb:

Ajeeb est un « automate » joueur d'échecs créé par Charles Hooper présenté au Royal Polytechnical Institute en 1868. À l'instar du Turc mécanique, il s'agit en réalité d'une personne dissimulée et qui manipule les pièces. Les spectacles d'Ajeeb attirent des foules de milliers de spectateurs lors de parties contre Harry Houdini, Theodore Roosevelt et O. Henry.

Les joueurs dissimulés sont Harry Nelson Pillsbury (1898-1904), Albert Hodges, Constant Ferdinand Burille.

Dans la tradition des prétendus automates joueur d'échecs, Ajeeb a succédé au Turc mécanique et a précédé Mephisto.

Après de nombreux spectacles à Coney Island (New York), Ajeeb fut détruit dans un incendie en 1929.

Ajeeb est un mot arabe signifiant étrange ou inexplicable.

L'automate "Ajeeb".

Il faut attendre Torres Leonardo pour véritablement lancer "l'ère"  des échecs  automatisée:

Leonardo Torres Quevedo est un ingénieur civil, mathématicien, physicien et inventeur espagnol de la fin du xixe siècle et au début du xxe siècle. 

Torres fut le premier à utiliser des relais électromécaniques pour implémenter les fonctions arithmétiques d'une machine à calculer. Il montra que tous les éléments mécaniques de la machine analytique de Charles Babbage pouvait être remplacés par des éléments électriques construit avec des relais. Il en fit la démonstration en construisant deux machines analytiques extrêmement limitées mais fonctionnelles, une en 1914 et une en 1920.

Il inventa en 1912 le premier automate joueur d’échecs et créa ainsi le premier jeu électronique.

Cet automate jouait la finale Roi et tour contre roi seul contre un opposant humain. Un bras mécanique déplaçait les deux pièces de l'automate. La machine gagnait toujours.

« Si le joueur commet une erreur, la machine s’arrête, allumant une lampe. Elle se remet en marche quand l'erreur est réparée. Trois erreurs successives font bloquer le joueur d’échecs mécanique qui refuse de jouer... Ainsi, la machine répond au coup qui lui est porté et joue, soit avec son roi, soit avec la tour, mais toujours de la façon la plus judicieuse, de sorte qu'après un nombre de coups mathématiquement déterminés, la machine gagne et annonce elle-même : Échec et mat ! par un phonographe, en même temps que ces mots s'inscrivent dans un voyant lumineux. »

Son algorithme n'était pas optimal mais il arrivait toujours à faire échec au roi. Ce fut le premier automate capable de prendre une décision automatiquement.

Il présenta son premier joueur d'échecs à la foire de Paris de 1914. Le bras mécanique fut remplacé par des aimants dans une version ultérieure.

La machine a créé la sensation à la Foire de Paris de 1914 et a obtenu une mention dans la prestigieuse revue scientifique américaine sur les 6 Novembre 1915, dans un article intitulé Torres et son dispositif automatique remarquable. En 1922, Torres Quevedo, avec l'aide de son fils, a construit une deuxième version améliorée du joueur d'échecs qui est également conservée (et toujours en cours) dans le Musée Torres Quevedo de génie à l'Université Polytechnique de Madrid.

Le grand Norbert Wiener , qui en 1948 a inventé le terme de la cybernétique, a expliqué le fonctionnement de cette machine au cours du Congrès cybernétique de Paris de 1951.

Des débuts difficiles

Les premiers véritables programmes virent le jour dans les années 1950, avec le développement des ordinateurs. Ils passèrent en un demi-siècle de la connaissance des règles à un niveau au moins égal à celui des meilleurs joueurs humains.

L'un des pionniers fut Alan Turing qui, en mai 1952, écrit un programme de jeu d'échecs. Ne disposant pas d'un ordinateur assez puissant pour le faire tourner, il simule lui-même les calculs de la machine, mettant environ une demi-heure pour effectuer chaque coup. Une partie fut enregistrée, où le programme perdit contre Alick Glennie, un collègue de Turing.

La première partie connue "jouée" par une machine.

A la question d'un journaliste sur la possibilité de créer une machine automatique jouant aux échecs, il répondra: « C'est une question qui pourra être résolue expérimentalement dans une centaine d'années. »... on était en 1946.

Mais c'est surtout à Claude Shannon qui développait alors la théorie de l'information au Bell Laboratory, que l'on doit les bases de la programmation du jeu d'échecs; En fait il comptait s'appuyer sur l'étude de ce jeu pour élaborer de nouvelles techniques de traitement de l'information sur le schéma de réflexion du cerveau humain, à savoir: calcul-évaluation-décision. C'est en mars 1949 que le célèbre article parut. Dedans il introduisait de nombreux concepts et nouveaux termes qui allaient bientôt devenir indispensables et que l'on utilise encore aujourd'hui, pas seulement dans le jeu d'échecs, mais dans tous jeux de réflexion: Arbre des variantes, fonction d'évaluation, force brute/recherche heuristique... Il suggéra également que le programme pourrait apprendre directement sur ses erreurs en modifiant dynamiquement la fonction d'évaluation... Beaucoup plus facile à dire qu'à faire!

Les pères du formalisme algorithmique: Alan Turing (1912-1954), de la théorie de l'information: Claude Shannon (1916-2001), et de la théorie des jeux: John Von Neumann (1903-1957).

En 1957 eut lieu la première partie disputée par un programme d'échecs sur une machine automatique; d'accord le Los Alamos Chess Program ne jouait que sur un échiquier réduit de 36 cases où les fous avaient de plus été éliminés, où les pions dans l'ouverture ne pouvaient avancer que d'une case, où les roques n'étaient pas gérés... mais il jouait et c'était ça le plus important!

La partie fut d'ailleurs remportée par l'ordinateur. Qui était le joueur adverse? un Maître International? un joueur de club? un joueur de seconde catégorie? non... un inconnu! En fait on avait sélectionné un volontaire qui ne connaissait une semaine auparavant rien aux échecs! Mais malgré la toute petite performance, il est certain que les programmeurs venaient de remporter un sérieux point psychologique sur le joueur d'échecs.

Ce programme, conçu par Ulam et Stein, tournait sur un ordinateur à lampes Maniac I de 1950 qui avait servi pour le projet Manhattan et l'étude des réactions nucléaires, la technologie à transistors n'étant pas encore très développée. Durant ce match la machine se limitait à une profondeur d'analyse de 4 demi-coups, ce qui fait qu'elle jouait un coup en, environ, 12 minutes (soit 500 positions analysées par seconde).

L'ordinateur à lampes MANIAC I au laboratoire atomique de Los Alamos.

Los Alamos Paul Stein (à gauche) et Nick Metropolis jouant aux échecs avec l'ordinateur MANIAC 

Dès l'année suivante, une machine sut appliquer toutes les règles et disputer une partie entière. C'était un IBM 704, programmé par Bernstein, Roberts, Arbuckle et Belsky. La saisie des coups se faisait à l'aide de cartes perforées. Outre une meilleure fonction d'évaluation, les concepteurs se penchèrent sur la sécurité du roi, une des clefs de la réussite d'un programme. Une troisième évolution fut l'abandon de la force brute au profit de la sélectivité des coups. Mais les performances étaient encore très médiocres.

Puis au début des années 1960, avec le développement des circuits intégrés et transistors, apparurent les premiers ordinateurs commerciaux (série des PDP de Digital Equipment), alors les programmes d'échecs purent commencer à participer à des opens. Mais du fait de la très faible puissance des ordinateurs, il est évident qu'ils ne faisaient pas un pli contre des joueurs professionnels ni même contre des joueurs de club.

De plus l'algorithme MinMax, proposé par Von Neumann en 1945 avec la théorie des jeux, était très succinct. Au fait pourquoi utiliser un algorithme alors qu'on pourrait tout simplement calculer toutes les parties différentes possibles, les mettre en mémoire, puis l'ordinateur n'aurait plus qu'à chargé les coups qui le mènent à la victoire? Tout simplement parce que le nombre de parties distinctes s'élève à 10 et qu'il faudrait des centaines de milliard d'années à un super ordinateur pour résoudre le calcul. Mais imaginons que l'on dispose d'une machine incroyablement puissante (un ordinateur quantique?), il y aurait encore un problème: celui du stockage des parties car même la totalité des particules existant dans l'univers (environ 10 aux dernières nouvelles) n'y suffirait pas!

Bernstein qui développait la seconde version de MANIAC était lui aussi perplexe sur la possibilité de victoire des ordinateurs sur des amateurs. D'ailleurs les joueurs ne s'y trompaient pas et étaient bien content de tomber contre eux lors d'open. Mais cela allait vite changer...

En effet un programme conçu par Greenblatt et Eastlake à la célèbre Massachusetts Institute of Technology fit sensation en obtenant en 1968 une performance de 1400 points Elo dans un open; Ainsi le MAC HACK pouvait en théorie se défaire de tous amateurs d'échecs. La fonction d'évaluation comprenait maintenant plus de 50 critères et calculait les coups jusqu'à une profondeur de 6 demi-coups.

La même année, lors d'un congrès international d'informaticiens, Michie et un certain Mac Carthy déclarèrent à David Levy, grand joueur d'échecs puisque champion d'Ecosse, que « les machines joueront dans quelques années au niveau d'un Maître International ». Mais David Levy connaissait les limites de l'informatique, en tout cas en ces années là, et il paria 500£  qu'aucun programme ne le battrait avant dix ans et en soi, il ne prenait pas beaucoup de risques!

Un combat sans partage

Comme on était en pleine période de guerre froide, les Soviétiques se devaient de réagir et sous la direction de l'ex-champion du monde Mikhaïl Botvinnik, ils élaborèrent alors le programme Kaïssa qui allait dominer les programmes Américains par trois victoires à une en 1966 puis qui allait décrocher le premier titre des champions du monde des ordinateurs en 1974 à Stockholm. Entre temps, en 1970, fut crée le championnat d'Amérique du nord des ordinateurs d'échecs.

En 1976, un joueur d'élite Suisse est battu par un ordinateur Digital Equipment

La volonté des universités à obtenir le plus fort ordinateur d'échecs entraîna la conception de nouveaux algorithmes plus efficaces tel que l' Alpha-Bêta, dûe à John Mac Carthy, qui permettait d'éviter une recherche exhaustive des coups en divisant par 6 (dans le meilleur des cas) le nombre de coups à analyser. En parallèle, la recherche en informatique était en plein boom et sous la tutelle d'Intel la puissance des ordinateurs avait pris son envol. Certains avaient compris et pensaient que réellement David Levy avait une chance de perdre le match, ainsi Papert en 1969 puis Kozdrowicki en 1971 et enfin Michie qui doubla son enjeu en 1974 firent qu'au bout du compte, le pari portait sur 1250£.

D'où les quelques inquiétudes de David Levy avant son match en 1978 contre le meilleur programme du moment Chess 4.7.

Un Maître International tombe...

Chess, développé à partir de 1967 à la Northwestern University par David Slate et Larry Atkin, tournait sur un des plus puissants ordinateurs du moment, le Control Data Cyber 176 (14 MIPS). Cette dernière version 4.7 avait pratiquement remportée tous les derniers grands rendez-vous des tournois d'ordinateurs en battant notamment Kaïssa. De plus, elle avait fait ses preuves en battant à plusieurs reprises des bons joueurs de club mais venir à bout d'un Maître International était une autre affaire, surtout qu'aucun Maître International n'avait encore été battu par un ordinateur.

Pourtant, fort de ses 3000 positions analysées par seconde, il donna du fil à retordre à Levy. Si le joueur s'imposa 3,5 à 1,5 c'est grâce surtout à sa bonne connaissance des points faibles du programme comme l'absence de stratégie en finale.

La défaite de David Levy dans la quatrième partie

Mais ce qu'on a retenu de ce match c'était cette défaite à la quatrième partie de Levy... Les machines allaient-elles prendre le pas sur l'Homme?

Penser au lieu de calculer

Tous les chercheurs affirmaient que le développement de l'intelligence artificielle allait apporter de nouvelles idées pour l'élaboration de programmes d'échecs. Déjà, au début du 20ème siècle, les psychologues Alfred Binet puis Otto Seiz s'étaient intéressé aux représentations mentales abstraites du joueur d'échecs. Ils montrèrent que nos facultés intellectuelles étaient conditionnées par la mémoire et l'intuition. Le joueur d'échecs de classe mondiale utilise sa mémoire, bien évidemment pour retenir la théorie des ouvertures, mais surtout pour emmagasiner de nombreux types de positions et schémas de jeux qu'il tente de reproduire. Ainsi l'analyse d'une position du joueur pourrait être la suivante: "cela me rappelle une partie contre X, la position de mon cavalier était en Y et il avait permis une offensive sur l'aile dame avec pour résultat le gain de la partie. Donc mon plan va être de tenter de placer le cavalier en Y." L'ordinateur dispose également de mémoires de masse considérables, mais il est tout à fait incapable de l'exploiter, en dehors de l'ouverture, et de raisonner comme le joueur. Quand à l'intuition, l'ordinateur n'en possède tout simplement pas. Alors qu'un joueur professionnel n'envisage que dix pour cents des coups possibles et que son arbre de recherche contient à peine 100 nœuds, l'ordinateur, dans le même temps, calcule bêtement tous les coups possibles avec au final un arbre dépassant les milliards de nœuds!

Par conséquent, les recherches entreprises avaient pour but de rapprocher les programmes des caractéristiques de réflexion humaines et de créer un programme d'échecs intelligent.

Au début des années 70, plusieurs scientifiques s'étaient attaqués au problème de l'IA donc le français Jacques Pitrat, chercheur au CNRS. Il utilisa pour cela une arborescence de plans qui était une suite de coups dépendant du but à atteindre et qui avait l'avantage d'être très réduit en noeuds. Le nom du programme développé était ROBIN.

En fait le succès fut mitigé car d'un côté, dès 1990 on ne parlait plus de ce type de programme d'échecs, ceux-ci étant complètement dépassé par la symbiose supercalculateur-algorithme AlphaBêta.

Des ordinateurs d'une autre dimension

Si ce n'était en devenant intelligent que la machine battrait l'homme, cela le serait pas sa vitesse de calcul et a fortiori par la puissance des processeurs avec une loi érigée: "augmentez la profondeur d'analyse d'un demi-coup et vous gagnerez 200 points Elo". Cette constatation encouragea l'apparition de gros ordinateurs équipés de plusieurs microprocesseurs. Et ce fût Belle qui ouvra le bal en 1980 en détrônant Chess 4.7 . Belle, conçue par Kenneth Thompson au Bell Telephone Lab, était un ordinateur spécialement créé pour les échecs et pouvait calculer plus de 100 000 positions par seconde. Il atteignait en 1983 un classement Elo de 2100, c'est à dire qu'il pouvait battre 95% des joueurs.

Puis en 1983, Cray Blitz remportait la palme. Il tournait sur les remarquables, et non moins célèbres, calculateurs Cray. Un nouveau défit de 1000$ fut alors lancé par David Levy au programmeur du Cray Blitz, ce montant venait s'ajouter à une somme de 4000$ offert par le magazine Omni. Mais encore une fois, David Levy remporta haut la main les quatre parties.

Un Cray-1

Enfin en 1984, le programme Hitech, développé à l'université Carnegie-Mellon de Pittsburgh sous la direction d' Hans Berliner ancien champion du monde d'échecs par correspondance, commença à battre régulièrement des Maîtres Internationaux grâce à une meilleure compréhension du jeu. De plus cet ordinateur allait prédisposer l'architecture parallèle en utilisant un processeur pour chaque cases, cette puissance de calculs lui permettant ainsi d'atteindre la profondeur étonnante de 14 demi-coups.

Les micro-ordinateurs et machines électroniques

A la fin des années 1970, apparus les premiers jeux électroniques d'échecs ainsi que des programmes tournant sur des micro-ordinateurs. Ceci fut spécialement dû à la percée de l'informatique domestique mais également aux coûts de fonctionnement des gros ordinateurs dont chaque heure d'utilisation coûtait plusieurs centaines d'Euros et qui, de toute façon, n'auraient pas laissé beaucoup de chance à son adversaire humain. Ainsi le grand public en rêvait et Fidelity Electronics l'avait bien compris: en 1976 cette société lançait sur le marché le dénommé Chess Challenger qui se déclinera en de nombreuses versions. Puis le 15 décembre 1977 arrivait la version 3 (car trois niveaux de jeux) en France. Son prix avoisinait les 458 Euros et son niveau de jeu était très faible; imaginez que même des mats en un seul coup lui échappaient!

Une publicité de 1978 du premier Chess Challenger sorti en France

En 1978, sortait une nouvelle génération d'appareils qui avait un rapport qualité/prix meilleur et dont le succès ne se fit pas attendre puisqu'elle s'est  vendu dans le monde en centaines de milliers d'exemplaires. Les joueurs de club et aficionados durent encore attendre un peu avant de trouver adversaire à leur taille jusqu'en 1980, où sortit Sargon 2.5. Cette machine apporta de nombreuses améliorations avec tout d'abord une grande bibliothèque d'ouvertures, la possibilité de réfléchir sur le temps de l'adversaire et une modularité des programmes. Cette dernière permettait ainsi, moyennant un fort coût, d'acheter de nouvelles bibliothèques vraiment spécialisées telles que la "défense sicilienne". Comme pour le cas des gros ordinateurs, un tournoi international fût créé, et il va sans dire que le couronnement du titre mondial était très convoité afin de doubler ou tripler ses ventes. Aussi une bataille commerciale commença où les quatre principales marques (Fidelity Electronics, Novag, Mephisto et plus tard SciTech) s'arrachèrent les rares programmeurs à coup de milliers de dollars. "Rare" car faire tenir un bon programme d'échecs dans 2 Ko de mémoire était un vrai défi.

Parallèlement les programmes sur micro étaient devenus de plus en plus un outil de travail pour le joueur d'échecs avec, grâce aux disquettes, disques durs puis cdrom, la possibilité de visionner de vastes bases de données, lesquelles renseignent sur le style d'ouvertures d'un joueur etc. Aussi ces mines d'informations, telles que ChessBase ou ChessAssistant, allaient prendre de plus en plus d'ampleurs avec l'ajout de clips vidéo, de commentaires sonores... tout pour satisfaire chaque catégorie de joueurs.

Les machines dédiées aux échecs, au cours des années 1980, changèrent très sensiblement leurs ergonomies. Si l'afficheur digital remplaçant l'afficheur LED n'apportait pas grand chose, en revanche le déplacement des pièces par pression (sensitif) renvoyait l'ancienne méthode aux oubliettes. Fini les prises de têtes à saisir au clavier le coup à joué et les bips qui vous harcèlent! Plus tard arrivera l'auto répondeur qui permettra enfin de totalement s'immerger.

Voici un problème qui montre la très rapide évolution des jeux électroniques:

Les blancs jouent et font mat en trois coups

Délai pour trouver la solution 1.Fxh7+ Rf8 2.Cg6+ fxg6 3.Tf4 mat La vitesse en cinq ans aura été multipliée par un million!

Deep Thought

En 1987, quatre étudiants, de la même université que les créateurs de Hitech, concevaient Chip Test qui était une sorte de prototype sur laquelle les créateurs bidouillaient, rajoutant tous ce qu'ils récupéraient en mémoires ou processeurs afin d'augmenter sa puissance. Cet enchevêtrement de pièces fût rebaptisé en nom plus sérieux Deep Thought. Et Deep Thought (Pensée profonde) méritait bien son nouveau nom car les programmeurs gérèrent avec succès le problème de l'explosion combinatoire (c'est à dire que lorsque l'ordinateur est confronté à une succession de prise, il analysera cette ensemble de prises et ne s'arrêtera pas bêtement au milieu de l'échange) qui lui permettaient ainsi d'annoncer parfois des mats en 20 demi-coups... ce qui avait dons d'agacer l'adversaire! En novembre 1988 au tournoi de Long Beach, Deep Thought fût enfin opposé à des adversaires de taille, son niveau de jeu était saisissant et cela se concrétisa le 25 lorsqu'il battu le Grand Maître Bent Larsen, c'était la première victime d'une longue série. Le magazine Scientific American avança que la prochaine génération de machine atteindrait un Elo de 3400 points (!). Enfin début 1989 Deep Thought, avec ses 750 000 positions analysées par seconde, écrasa tous ses homologues lors du championnat du monde des ordinateurs.

Et ce fût le tournant; IBM décidait de soutenir les développeurs, y voyant là une formidable occasion de montrer que les ordinateurs IBM étaient les meilleurs au monde. Mais pour avoir le succès escompté il fallait frapper fort et rien de tel qu'un défi visant la victoire de l'ordinateur sur le meilleur joueur mondial. Des crédits illimités étaient alors alloués aux deux concepteurs principaux, Feng Hsiung Hsu s'occupait de la partie hardware (il ne connaissait rien aux échecs...) et Murray Campbell gérait le software. A ce moment Deep Thought pouvait analyser deux millions de positions par seconde. Il était à peu près 200 fois plus puissant qu'un ordinateur du commerce, mais pourtant il réussit à se faire battre en 1989 par le terrible Mephisto qui, lui aussi, raflait tout sur son passage avec, notamment, un cinquième sacre en tant que meilleur micro-ordinateur.

Deep Thought battait, début 1989, le Grand Maître Robert Byrne en match et, fin 1989, il était confronté au champion du monde, Garry Kasparov, en partie semi-rapide. L'ordinateur se fit humilié et perdit 2 à 0. Fort de sa victoire (et de ses 10000 dollars empochés), Gary Kasparov déclara dans son style bien provocant: « Aucun ordinateur ne me battra ! ». Mais il en fallait plus pour décourager IBM...

Les ordinateurs jouent et gagnent

En 1990, Anatoli Karpov, alors deuxième joueur mondial, était battu par Mephisto dans une simultanée. Ce même ordinateur gagna contre les Grands Maîtres Robert Huebner et David Bronstein. Enfin il obtient une norme de Maître International à l'open de Dortmund.

Quand à Deep Thought, il obtenait la même année une performance spectaculaire de 50% des points en jouant contre dix Grands Maîtres, et 86% des points en jouant contre 14 Maîtres Internationaux, et ce, dans des conditions de tournois. Puis en 1993 Deep Thought eut logiquement le privilège d'être sélectionné afin d'analyser le match des championnats du monde d'échecs entre Kasparov et Karpov.

C'est à cette époque, avec l'arrivée du cdrom, que des bases de données pour les finales sont apparues. Ces bases (dites tablebases), généralement de types Ken Thompson ou de Nalimov, sont simplement des positions, regroupées par pièces présentes (par exemple: la consultation de la base TT/D signifie que deux tours blanches ainsi qu'une dame noire -en plus des deux rois évidemment- sont les seules pièces présentes sur l'échiquier), qui ont déjà été analysées à l'avance et dont la meilleure suite est enregistrée. Ainsi si l'ordinateur a cette position dans sa base de données alors il trouvera toujours le meilleur coup.

Les bases des ordinateurs d'échecs, au départ, contenaient seulement les positions comprenant quatre pièces tandis que les bases cinq pièces compressées, occupant la bagatelle de 7.5 Go, étaient stockées sur des ordinateurs énormes. Elles n'étaient utilisées que dans de rares cas, comme pour la consultation après un ajournement ou bien pour vérifier des études faites il y a des années; par exemple, il y a une vingtaine d'année, la finale FF/C était considérée comme fréquemment nulle mais l'analyse par l'ordinateur a montré que le camp qui possède les deux fous doit gagné en maximum 70 coups. Plus tard ces bases cinq pièces allaient se démocratisées et en 1995 la plupart des ordinateurs professionnels et logiciels professionnels disposaient de cette fonctionnalité. Cette infaillibilité en finale, les informaticiens cherchèrent à la repousser encore plus loin avec, aujourd'hui, l'analyse des positions à six pièces dont on peut déjà télécharger sur le web quelques exemples.

Le tournoi de Munich le 19-20 mai 1994 réunissait les meilleurs joueurs mondiaux ainsi, une première dans un tournoi aussi élevé, que le programme Fritz 3. Et il n'y eut pas besoin de seconde fois pour montrer la supériorité des programmes en blitz... car Fritz 3 vainquit à tour de rôle Kasparov, Anand et Kramnik. Les matchs terminés, Kasparov et le programme occupaient la première place mais Kasparov motivé comme jamais se vengera dans le match départage et battra Fritz 3 à plates coutures sur le score de 4-1. Mais cette non moins superbe performance de Fritz à 2800 points Elo était tout de même à relativiser car tout d'abord les parties étaient des blitz de 5 minutes, or on savait depuis bien longtemps que l'ordinateur était très fort dans ce domaine puisqu' il ne loupe pratiquement aucun combinaison tactique et ne commet pas de gaffes en zeitnot, de plus les deux joueurs (Gueorguiev et Hertneck) qui réussirent à battre Fritz étaient les seuls, comme par hasard, à avoir testés le programme au préalable, donc avec un peu d'entraînement la manière de jouer de Fritz devait s'apprendre. Sponsorisé par Intel, Fritz tournait logiquement sur les nouveaux processeurs Intel Pentium et calculait 100 000 positions par seconde. Il était tout de même dommage, et cela allait se reproduire, que le nom du joueur informatique inscrit n'ait pas été le nom du programme lui même mais celui du processeur... de quoi un peu mépriser le travail des programmeurs!

Kasparov ne fera qu'une bouchée de Fritz en finale

Kasparov avait donc par trois fois battu Fritz; à chaque partie il avait joué 1.e3 ("début irrégulier") pour tenter de déstabiliser l'ordinateur et cela avait marché car les programmeurs de Fritz n'avaient pas prévu un tel cas (on sait que même si aucun premiers coups aux échecs n'est réfuté, il est toujours préférable de soit occuper le centre: théorie de Steinitz ou soit de contrôler le centre: théorie de Réti) et ne s'étaient pas penché sur l'élaboration d'une bibliothèque avec l'ouverture en question. Ainsi au bout de quelques coups le programme était déjà en difficulté. Autant dire que ce n'était pas resté inaperçu et Richard Lang, concepteur de Genius, dépêcha le Grand Maître International Gerald Hertneck afin d'établir une bibliothèque d'ouverture comprenant des variantes avec 1.e3, Hertneck en profita également pour créer une bibliothèque étudiée au jeu de chaque joueur du circuit.

C'est ainsi que Chess Genius 2.9 arriva au tournoi de Londres avec un tout nouveau bagage théorique, près à piéger les plus grands. Ce tournoi, à la différence de celui de Munich, était par élimination directe et le temps alloué à chaque participant de 25 minutes en faisait un tournoi beaucoup plus sérieux. Chess Genius et ses concepteurs n'avaient pas vraiment eu beaucoup de chance lors du tirage au sort puisqu'ils avaient tiré Kasparov. Pourtant il réussit l'impensable: battre le numéro 1 mondial. La nouvelle se répandit à travers le monde et elle fit la une de la presse. Kasparov était cette fois-ci tombée face à meilleur que lui.

Le match Deep blue-Kasparov

Maintenant restait un objectif, celui de battre Kasparov en match. Et c'est IBM qui allait s'employer à le faire. En février 1993, Deep Thought était renommé Deep Blue (en hommage à IBM qui est souvent surnommé "Big blue"). Mais l'amélioration en Deep Blue était bien plus qu'un simple changement de nom. En fait IBM introduisait la technologie "massivement parallèle" avec ses serveurs RS/6000 SP (scalable power parallel), ceci permet de connecter un nombre incroyable de processeurs en parallèle. Ainsi Deep Blue disposait de 32 serveurs Power2 (donc 32 nœuds) pilotant chacun 8 processeurs VLSI (composants à très haute intégration), ce qui donnait un total de 256 processeurs en parallèle et une puissance de 0.7 Tflops. Ainsi il pouvait évaluer 200 millions de positions par seconde, soit, en trois minutes, atteindre une profondeur de 7 coups (14 demi-coups).

Une des 32 cartes serveurs Power2

Deep blue

Fruit d'un pari réussi, IBM aura vendu en trois ans plus de dix milles RS/6000 SP!

Donc en 1996, Deep blue avait eu trois ans pour se préparer et un match contre Kasparov s'imposait. Çà commençait mal pour le joueur humain puisqu'il perdit la première partie. Mais le reste du match fût totalement à sens unique avec deux nuls et trois victoires pour le champion du monde. Encore une fois, IBM financerait Deep Blue tant que celui ci n'aurait pas battu Kasparov et, vu que le constructeur informatique pouvait se le permettre, une revanche fût organisé dès 1997. L'évènement fût pour une fois très médiatiser, pas autant que le match Spassky-Fischer, mais suffisamment pour que la radio, la presse, la télévision et surtout Internet (cinq millions d'internautes ont suivis le match) en parlent. Toute la pression était donc sur le dos de Kasparov, surtout que les développeurs s'étaient renforcer du Grand Maître International Joël Benjamin et annonçaient une version beaucoup plus forte de Deep Blue (qu'ils nommèrent d'ailleurs Deeper Blue).

La première partie se déroula très bien pour Kasparov puisqu'il s'imposa grâce à une succession d'erreurs stratégiques de son adversaire et n'eut pas à forcer son talent.

Curieusement dans le début de la deuxième partie, Deep Blue semblait métamorphoser tellement qu'il joua les coups justes, pourtant à partir du quarantième coup il commit à nouveaux deux faux pas, hélas Kasparov abandonna prématurément alors que selon les analyses ultérieures le joueur pouvait annuler facilement. Dommage pour lui et pour les échecs en général... Les trois parties suivantes se soldèrent par des nulles.

Il restait donc une dernière partie à jouer. Il est sûr que dans cette partie Kasparov voulait gagner le point décisif, et ne pas se contenter d'une nulle qui aurait renvoyé les deux adversaires dos à dos.

Seulement au huitième coup, après que l'ordinateur ait fait un superbe sacrifice matériel digne des meilleurs joueurs, Kasparov, pourtant si redoutable d'habitude dans l'ouverture, était déjà dans une position très compliquée et il n'y avait qu'à voir la position noire au onzième coup pour comprendre que cette fois ci l'ordinateur aurait sa peau.

Position après le onzième coup noir

La dernière partie et la défaite en 19 coups de Kasparov

Et en effet l'ordinateur ne lui laissera aucune chance avec une inexorable attaque contre son roi noir. Lorsqu'il abandonnera au 19ème coup (une des plus rapides défaites de sa carrière) ce sera un véritable choc pour tous les spectateurs et humains que nous sommes: un monstre cybernétique, ne comprenant que les 0 et les 1, aura réussi ce qu'aucun joueur n'a jamais fait: battre Kasparov en match.

Les spectateurs n'en croient pas leurs yeux: la position de Kasparov prend l'eau de toute part!

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é a été atteint, leur machine a 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 25 000 dollars par partie gagnée et 10 000 dollars par partie nulle. À l’issue des six parties, Adams a gagné… 10 000 dollars, vous aurez donc compris qu’il perdit 5 parties et en annula une seule. Hydra, qui calculait avec ses 64 processeurs environ 200 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.

Adams contre Hydra en 2005.

Du 20 au 23 novembre 2005, Hydra a joué quatre parties à Bilbao en Espagne contre trois ex-champions du monde, dans le cadre d'une rencontre hommes-machines. Hydra a remporté une victoire contre Rustam Qosimjonov, fait nulle contre Alexander Khalifman, puis remporté une autre victoire contre Ruslan Ponomariov et finalement obtenu une nulle contre Rustam Qosimjonov. Les machines, représentées par Junior et Fritz en plus d'Hydra, ont nettement remporté le match 8 points à 4.

Le nouveau champion du monde, Vladimir Kramnik, affronte le logiciel Deep Fritz dans un match en six parties, du 25 novembre au 05 décembre 2006, au prestigieux Palais Fédéral des Arts et expositions de Bonn, en Allemagne. Kramnik recevra la somme d'un million de dollars s'il gagne le match. Score final : 4.0 à 2.0 pour la machine après 6 parties.

Après chaque partie, l'équipe de Deep Fritz devra imprimer toutes les analyses de la machine et les communiquer à l'arbitre et à l'équipe de Kramnik. Ce document devra inclure les évaluations, la profondeur de recherche, les coups envisagés et les temps de réflexion.

Avec la participation de: M. CIVITARESE Jonathan ( http://proceduralobjects.free.fr/echecs.htm).

Quelques jeux d'échecs électroniques

Méphisto

A l'attention d'Enguerran mon estimé ami qui ne connaît pas la gamme "Méphisto".

Le premier ordinateur d'échecs MEPHISTO vit le jour en 1980 et fit sensation sur le marché après avoir remporté la victoire dès son premier tournoi à Stockholm.

En 1984, MEPHISTO prit part au championnat du monde d'échecs pour micro-ordinateur à Glasgow et décrocha pour la première fois le titre de champion du monde. Les championnats du monde suivants confirmèrent cette supériorité.

MEPHISTO fut proclamé champion du monde des micro-ordinateurs en 1985 à Amsterdam, en 1986 à Dallas, en 1987 à Rome, en 1988 à Almeria, en 1990 à Lyon et en 1991 à Vancouver.

Lors aussi des tournois «homme contre ordinateur», MEPHISTO se révéla un adversaire respectable et parfois même redouté. C'est avant tout à l'occasion de parties-éclair que les diaboliques ordinateurs d'échecs montrèrent leur force. Sur l'échelle Elo, l'échelle internationale de comparaison de la force des joueurs d'échecs, MEPHISTO a déjà franchi des barrières qui, jusqu'ici, avaient été considérées comme infranchissables pour un ordinateur.

Aussi n'est-il pas étonnant que l'ordinateur d'échecs MEPHISTO serve de référence dans le monde des échecs.

Citons à ce propos le grand maître Dr. Helmut Pfleger, auteur bien connu de livres d'échecs et commentateur de télévision. « Les jeux d'échecs électroniques ont maintenant atteint un niveau fort respectable et doivent être pris au sérieux comme adversaires et partenaires. Ils se prêtent bien à l'entraînement mental tout en offrant une possibilité de détente et d'amusement ».

Avant tout voici les différents types de plateaux de la gamme Mephisto:

Chaque case de l'échiquier est munie d'une petite diode électroluminescente rouge (appelée aussi LED). Ces LED indiquent en s'allumant les coups effectués par l'ordinateur. Sous chaque case de l'échiquier se trouve un capteur qui est sensible à l'aimant permanent logé dans le socle des pièces. Lorsque vous exécutez un coup sur votre échiquier, le capteur de la case en question signale à l'ordinateur que vous venez d'enlever une pièce de cette case. De son côté, le capteur de la case sur laquelle vous posez votre pièce enregistre ceci et le signale également à l'ordinateur qui sait maintenant de où à où vous avez déplacé une pièce. Cette technique s'appelle la technique des capteurs magnétiques.

Le mode de fonctionnement du Mephisto Bavaria est semblable. Nous y trouvons aussi des diodes électroluminescentes sur les cases de l'échiquier qui sont également munies chacune d'un capteur. Par contre, l'enregistrement des mouvements ne se fait pas au moyen de capteurs magnétiques, mais par induction. Les pièces du modèle Mephisto Bavaria sont munies de bobines à induction au lieu d'aimants permanents. Comme les diverses pièces sont munies de bobines à induction différentes, l'ordinateur est en mesure de reconnaître quel type de pièce se trouve sur une case. Les ordinateurs utilisant la technique des capteurs magnétiques peuvent uniquement distinguer si une case est occupée par une pièce ou non, niais pas de quel pièce il s'agit. Si, dans la position de départ, vous intervertissez le Roi et la Dame, l'échiquier Bavaria s'en apercevra. Les échiquiers  Exclusive ou  ne sont pas capables de reconnaître ceci. Le programme Vancouver reconnaît automatiquement s'il a à faire à un échiquier Bavaria ou à un échiquier à capteurs magnétiques. L'utilisation de cette technique à capteurs exige que vous utilisiez toujours les pièces d'origine livrées avec votre ordinateur. Le jeu de pièces du Bavaria comprend deux pièces supplémentaires qu'on appelle pièces joker.. Elles se présentent comme des Pions avec un petit chapeau. Ces jokers peuvent prendre la place de n'importe quelle autre pièce et sont donc indispensables lorsque vous désirez jouer avec une deuxième Dame ou un troisième Cavalier."

Quelques modèles du MEPHISTO:

Quelques programmes d'échecs informatiques

Épilogue

Nombreuses ont été les analyses et commentaires après ce match. Il a d'ailleurs été critiqué sur de nombreux points: Déjà il est certain que Kasparov n'a pas joué son jeu qui le rend si redoutable, sans doute, voulant éviter les positions tactiques. Ensuite il semble que Deep blue a joué des coups qu'il n'aurait jamais dû jouer... aussi Kasparov pense toujours qu'il y a eu sur certains coups une intervention humaine... difficile de juger. Dès la fin du match Deep blue est parti à la retraite et n'a plus jamais été utilisé. Or rappelons tout de même que Kasparov avait remporté le premier match en 1996 et il était donc assez logique de disputer une belle, mais après avoir empoché quelque 100 millions de dollars avec l'impact publicitaire, IBM a sans doute estimé qu'il avait été chanceux tout au long des six parties et qu'il ne servait à rien de risquer de ternir son image de marque. Pour finir un match en six parties contre un ordinateur était tout à fait inégal car la fatigue mentale et la lassitude jouent énormément. Aussi Kasparov n'aurait sans doute pas perdu cette dernière partie si il n'y en avait pas déjà eu cinq, chacune dépassant les deux heures de jeu. Beaucoup plus récemment (fin 2002) Kramnik menant 3-1 contre le programme Deep Fritz se fera rattraper avec, là aussi, un abandon dans une position nulle, sans doute due à la fatigue. Bref chacun jugera.

En fin de compte il aura fallu "seulement" une cinquantaine d'année pour battre le champion du monde. Selon les prédictions, et comme pour toutes prédictions, certains étaient dans le vrai, d'autres avaient à peu près vu juste, et d'autres par contre étaient soit complètement pessimistes soit optimistes. Ainsi l'ordinateur battrait le champion du monde en 1993 selon McCarthy, en 1999 selon Shannon, en 2010 selon Kasparov et en 2018 selon Thompson...

Ne croyons pas pour autant que la machine est devenue intelligente car Deep blue n'utilisait aucun algorithme d'intelligence artificielle. Aussi pouvons nous espérer dans les prochaines années qu'un nouveau défit sera relevé. Pourquoi pas un jour un ordinateur réseau neuronal jouant aux échecs...

Les ordinateurs champions du monde (WCCC)

Quelques photos

Les dates clés de l'aventure cybernétique échiquéenne

1770, Wolfgang von Kempelen construit l'automate joueur-d'échecs, le Turc mécanique, qui devient le plus grand canular de cette période. 

1868, Charles Hooper présente l'automate Ajeeb — qui avait également un joueur d'échecs à l'intérieur. 

1876, Charles Geoffrey Gumpel contrôla cette fois-ci l'automate nommé Mephisto a distance grâce a des moyens électromécaniques. 

1912, Leonardo Torres y Quevedo construit une machine qui peut jouer les finales roi et tour contre roi.

 1948, le livre Cybernétique de Norbert Wiener décrit comment un programme d'échecs peut être développé en utilisant une profondeur minimale de recherche avec une fonction d'évaluation. 

1950, John von Neumann développe un programme d'échecs (sur un échiquier 6x6 sans fou) sur le MANIAC I.

1950, Claude Shannon élabore son algorithme permettant d'évaluer les coups possibles jouer aux échecs.

Le nombre de Shannon, soit 10 à la puissance 120, est une estimation de la complexité du jeu d'échecs, c'est-à-dire du nombre de parties différentes, ayant un sens échiquéen, possibles. Ce nombre est à distinguer du nombre, beaucoup plus élevé, de parties légales qu'autorisent les règles du jeu.

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".

 1952, Alan Turing développe sur le papier le premier programme capable de jouer une partie d'échecs complète. 

1952, Dietrich Prinz développe un programme résolvant des problèmes d'échecs. 

1956, invention de l'algorithme de recherche alpha-beta par John McCarthy.

 1958, NSS devient le premier programme d'échecs à utiliser l'élagage alpha-beta.

 1958, les premiers programmes qui sont capables de jouer une partie complète voient le jour, le premier par Alex Bernstein et l'autre par des programmeurs russes sur mainframe BESM. 

1962, le premier programme avec un jeu crédible, Kotok-McCarthy est publié au MIT. 

1966-1967, le premier match entre programmes d'échecs voit le jour. Le programme Kaissa de l'Institut de physique théorique et expérimentale de Moscou triomphe de Kotok-McCarthy de l'université Stanford. Les coups étaient échangés par télégraphe et le match a duré 9 mois.

 1967, Max Hack 6 de Richard Greenblatt utilise des tables de transposition pour la première fois et devient le premier programme à gagner contre une personne en tournoi. 

1970, le premier Championnat nord-américain des ordinateurs d'échecs est organisé.

 1974 Kaissa devient le premier champion du monde des ordinateurs.

 1977, le premier jeu d'échecs électronique, Chess Challenger, est commercialisé. 

1977, l'International Computer Chess Association (ICCA) est créée. 

1977, Chess devient le premier ordinateur à remporter un tournoi d'échecs majeur. 

1978, Belle, un ordinateur spécialisé construit par Ken Thompson atteint le niveau de maître.

 1985, HiTech réalise une performance Elo de 2530, c'est le premier programme à atteindre le classement de 2400 (niveau d'un maître international),

 1988, HiTech remporte le championnat de l'état de Pennsylvanie après avoir battu le maître international Ed Formanek (2485). Il bat également le grand maître international Arnold Denker en match (3,5-2,5)1.

 1989, Deep Thought, le premier ordinateur du niveau d'un grand maître est facilement battu en match 2-0 par Garry Kasparov.

 1994, Fritz 3 gagne une partie de blitz contre le champion du monde de l'époque, Garry Kasparov et ils terminent ex æquo. Kasparov prend sa revanche dans les départage : 4-12. Cette même année à Londres, Chess Genius bat Garry Kasparov en partie semi-rapide (1.5-0.5) avec un Pentium 100 MHz. 1996, le super ordinateur Deep Blue perd contre Garry Kasparov. (1 victoire, 2 nulles et 3 défaites).

 1997, Deep Blue bat Garry Kasparov. (2 victoires, 3 nulles et 1 défaite) Cependant Kasparov ternit l'image de son adversaire en accusant l'équipe d'IBM d'avoir triché en faisant intervenir un humain dans les choix des coups de Deep Blue, surtout à la deuxième partie qui s'achèvera par une victoire de Deep Blue.

 2003, Kasparov fait match nul contre Deep Junior et plus tard contre Fritz X3D, 

2005, Hydra gagne face à Michael Adams par 5 victoires et une nulle contre 0 victoire. 

2005 en novembre Hydra a remporté une victoire contre Rustam Qosimjonov, fait nulle contre Alexander Khalifman, puis remporté une autre victoire contre Ruslan Ponomariov et finalement obtenu une nulle contre Rustam Qosimjonov. 

2006, Deep Fritz gagne face à Vladimir Kramnik par 2 victoires et 4 nulles contre 0 victoire.