Comment les ordinateurs

jouent-ils aux échecs ?

Depuis quasiment l'aube de l'informatique, au début des années 50, les programmeurs ont essayé de faire jouer les ordinateurs au échecs. Cependant, l'enthousiasme initial a rapidement laissé place à la perplexité puis à la déception : faire battre le champion du monde d'échecs en titre par un ordinateur n'est pas une chose aussi simple qu'il y paraissait à première vue.
Dans cet article, après avoir fait un petit historique des programmes d'échecs, nous allons expliquer les principales techniques utilisées par les ordinateurs pour jouer aux échecs ainsi que leurs diverses variantes. Nous examinerons ensuite plus en détails les techniques d'optimisations utilisées par les programmes performants pour obtenir un meilleur niveau de jeu.

    Historique des programmes d'échecs

En 1950, Alan Turing (un des pères de l'informatique) a écrit le premier programme d'échecs. Turing avait à l'époque dû se contenter de simuler l'exécution de son programme sur papier. Son programme jouait extrêmement mal, mais il avait l'avantage de marcher. La même année, Claude Shannon (un autre des pionniers de l'informatique a qui l'on doit notamment la théorie du codage de l'information) énonça 2 stratégies permettant aux ordinateurs de jouer aux échecs, cependant étant donné les médiocres (et le mot est faible) performances des ordinateurs de cette époque, il était alors impossible de savoir si un ordinateur serait un jour capable de battre un joueur humain ayant un niveau correct.

Il fallu attendre 1958 pour voir un ordinateur battre un joueur humain pour la première fois. Ce délai de huit ans étant largement dû au fait qu'étant donné les fortunes colossales que coûtaient les ordinateurs à cette époque, ceux-ci étaient en général réservés à des tâches plus productives que de les faire jouer aux échecs. La première personne a avoir été battue par un ordinateur était la secrétaire de l'équipe des programmeurs qui n'avait jamais joué aux échecs auparavant en dehors d'une heure d'apprentissage dispensée par ses collègues. Cette première victoire, loin d'être spectaculaire, permis néanmoins de prouver qu'un programme pouvait accumuler suffisamment d'"intelligence", égale à environ une heure d'apprentissage, pour battre un joueur humain.

Après cet événement, certains programmeurs prédirent que d'ici la fin des années 60, un ordinateur serait capable de battre aux échecs le champion du monde en titre. Or, à la fin des années soixante, le champion du monde en titre était Boris Spassky, et celui-ci n'avait que très peu de risque de se faire battre par un ordinateur étant donné que ceux-ci jouaient alors avec un niveau similaire à celui d'un adolescent moyennement entraîné.
La même prédiction a néanmoins été renouvelée pour les années 70. Ce que n'empêcha pas qu'en 1978 le meilleur programme d'échecs du moment (qui portait le nom peu original de "CHESS 4.7") a été battu par David Levy (Maître International d'échecs).
Loin d'avec été refroidis par cette nouvelle défaite, les "experts" en programmes d'échecs de l'époque ont naturellement réitéré la prédiction qu'un ordinateur serait capable de battre le champion du monde en titre durant la décennie suivante. Ce qui prouve bien que tout ce que l'on apprend de l'Histoire, c'est que l'on apprend rien de l'Histoire ;-)
Sans surprise, dix ans plus tard, en 1988, le champion du monde d'échecs était toujours humain. L'année suivante, IBM a mis au point l'ordinateur Deep Thought qui battit assez aisément D. Levy. Puis, en 1990, une partie fut organisée entre Deep Thought et le champion du monde en titre de l'époque (Garry Kasparov) au cours de laquelle le Russe infligea une défaite cuisante à l'ordinateur.
Sans se décourager IBM mis au point Deep Blue (évolution de Deep Thought) en 1996 et le reconfronta contre Kasparov. Cette fois, bien qu'ayant encore perdu, la défaite de la machine fut beaucoup plus "honorable". Malgré les quelques années qui nous séparent de 1996, les performances de cette première version de Deep Blue ne seront pas égalés sur des ordinateurs à porté du grand public avant encore quelques années. Deep Blue fonctionne sur un super-calculateur de type SP/2 avec l'aide de processeurs spécialement étudiés pour l'évaluation des positions. Chacun d'entre eux contient 48 Mo de mémoire et peut analyser 3 millions de coups par seconde.
Dernier épisode en date : en 1997, IBM est revenu à la charge avec Deeper Blue et cette fois (enfin!) le match s'est soldé par la victoire de la machine. Les experts relativisent ce succès dans la mesure où le programme utilisé par Deep Blue n'est pas un programme d'échecs "générique", mais a été spécialement optimisé pour être opposé au style de jeu de Kasparov (que les programmeurs d'IBM ont eu tout le temps d'analyser au cours des années), d'autre part Kasparov n'était visiblement pas au meilleur de sa forme durant le match dans la mesure ou il a commit une grossière erreur au 7ème coup de la dernière partie, ce qui a entraîné sa défaite.

    Première approche du problème

Faire un programme qui joue aux échecs est quasi-trivial : il suffit de générer la liste des coups possible à partir de la position actuelle et de choisir un de ces coups au hasard. Bien évidement cette technique a été testée et les programmes qui les utilisent peuvent dans la plupart des cas être vaincus en une dizaine de coups.
Maintenant que vous êtes persuadés (au cas ou vous ne l'étiez pas déjà) qu'un ordinateur peut jouer aux échecs, demandons-nous comment un ordinateur peut bien jouer aux échecs (et c'est précisément là que tout se complique).
En théorie, il "suffit de" créer un programme qui explore tous les coups possibles jusqu'à la fin de la partie et utilisera ensuite le résultat de cette exploration pour toujours choisir la meilleure stratégie.
Considérons comme exemple le jeu du morpion sur une grille de trois cases de coté : la meilleure stratégie permet toujours d'obtenir soit une victoire, soit une égalité. Quelle que soit la tactique utilisée par l'adversaire, il existe toujours un coup qui permet de s'assurer la victoire, voire au pire une partie nulle. Pour cela il suffit à partir de la position initiale de considérer tous les coups possibles, puis toutes les réponses possibles de l'adversaire pour chacun de ces coups, et ainsi de suite jusqu'à la fin de la partie. Une fois l'analyse terminée, le programme choisira à chaque tour la meilleure possibilité en évitant la défaite à coup sûr.
Il se trouve que, malheureusement, dans le cas des échecs le nombre de possibilités qui doivent être explorées est gigantesque (estimé à 10⁴⁰). Ce nombre étant bien au delà des possibilités des ordinateurs actuels (et cela pour encore un bon moment), les programmes d'échecs doivent utiliser des techniques permettant de limiter le nombre de possibilités à évaluer.

    Les techniques de base

Dès 1950, Claude Shannon a proposé 2 stratégies pour restreindre le nombre de possibilités a explorer. Ces deux méthodes sont toujours largement utilisées par les programmes d'échecs actuels.
La première méthode, appelée "stratégie de Shannon type A", considère tous les mouvements possibles à partir d'une position donnée jusqu'à un certain nombre de coups (déterminé à l'avance). A chaque position explorée, une fonction d'évaluation est appliquée pour déterminer si cette position est intéressante ou non. A la fin de cette exploration, le coup le plus intéressant est joué. L'idée de base étant que puisqu'il n'est pas possible d'explorer toutes les alternatives possibles, on se limite à regarder les positions engendrées en jouant un nombre de coups donné, ce qui peut se faire en un temps raisonnable.

    Fonction d'évaluation

Pour déterminer si une position est favorable ou non, l'ordinateur utilise une fonction d'évaluation qui assigne une valeur à chaque position en fonction de la situation de l'échiquier : avantage matériel ou positionnel, etc.

Morgenstein et von Neumann, qui ont formalisé la théorie des jeux sur ordinateurs, ont réalisé que le jeu peut être considéré comme une arborescence de positions possibles reliées entre elles par les mouvements de pièces. A chaque embranchement, le joueur qui a le trait choisi de s'engager sur une branche de l'arbre qui maximise ses chances de gagner ou qui minimise les chances de gain de l'adversaire. D'où le nom de cette méthode : min-max.
Du fait que la complexité de ce problème est exponentielle, les ordinateurs actuels utilisant cette méthode doivent limiter leur recherche à une douzaine de déplacements. A raison de 30 possibilités de déplacement en moyenne pour chaque coup, cela représente déjà 30¹² (soit environ 5.3 * 10¹²) cas à explorer.
L'arbre d'exploration est également trop gros pour tenir en mémoire et les programmes utilisant cette méthode de recherche ne conservent en mémoire que les meilleures branches de l'arbre, ce qui fait que celui-ci doit être recalculé à chaque mouvement.

L'autre stratégie de base définie par Shannon, dite "stratégie de Shannon type B", consiste a limiter le nombre de possibilités a considérer à chaque niveau. Pour chaque configuration de l'échiquier examinée, un générateur de mouvement détermine les mouvements possibles, et sélectionne seulement les meilleurs (approximativement huit). Par opposition à la stratégie A, celle-ci ne définie pas de profondeur maximale pour la recherche. Typiquement, la recherche est effectuée à une profondeur minimum, mais si on arrive à une position intéressante, comme une série de captures ou un échec au roi, alors l'exploration sera poursuivie quelques niveaux plus loin. L'explication est simple : si au dernier niveau d'exploration le joueur peut capturer une tour adverse avec sa dame, cela peut sembler être un bon coup, cependant si au coup suivant l'adversaire capture la dame du joueur avec un pion, le coup n'est plus du tout intéressant.

Les essais ont montré que les explorations en profondeur ne sont pas très efficaces si seulement certains mouvements sont sélectionnés à chaque position de l'échiquier. Pour cette raison, les ordinateurs rapides utilisent souvent la stratégie A, alors que les programmes qui tournent sur des architectures plus modestes, comme des microcontroleurs, utilisent la stratégie B.

    Optimisations et heuristiques !

Maintenant que nous avons planté le décors et présenté les algorithmes de base intéressons-nous aux diverses heuristiques et techniques permettant d'améliorer le niveau de jeu des programmes d'échecs.

    Recherche alpha-beta

Cette méthode est une amélioration du min-max. Au lieu d'explorer l'arbre des coups "bêtement" dans le sens de la largeur, on stoppe l'exploration sur les branches dont les meilleurs noeuds sont nettement moins favorables que les meilleurs coups possibles déjà trouvés sur d'autres branches. A elle seule, cette technique permet une amélioration considérable du niveau de jeu (Consultez le document cité dans les références si vous désirez en savoir plus sur l'algorithme alpha-beta).

    Dictionnaire d'ouvertures

Tous les débuts de parties d'échecs intéressantes connues sont rassemblés dans un dictionnaire que le programme peut utiliser pour choisir ses coups plus rapidement en début de partie. En effet, tout au long de l'histoire des échecs, des milliers de joueurs ont analysés un grand nombre de positions initiales et longuement écris à leur sujet. Il n'est donc pas judicieux que les programmes d'échecs perdent du temps à redécouvrir ces ouvertures. Les programmes évolués sont donc capables d'exploiter une base de données d'ouvertures connues soit comme étant "bonnes" soit à éviter absolument et joueront leurs coups quasi-instantanément en début de parties.
Comme pour la plupart des techniques, celle-ci résout certains problèmes, mais elle en crée aussi d'autres.
Par exemple, un excellent joueur peut exploiter le dictionnaire d'un programme en jouant une série de coups pour amener l'échiquier dans une configuration qu'il suppose ne pas être dans le dictionnaire. Ainsi, lorsque le programme ne peut plus utiliser son dictionnaire et doit commencer à "réfléchir", il peut se trouver en assez mauvaise posture et perdre de précieux coups à replacer ses pièces. D'autre part, si un joueur connaît le contenu exact du dictionnaire d'ouverture de son adversaire, il peut préparer des pièges spécialement contre lui. Contre un joueur humain, ce genre de piège ne marchera qu'une seule fois. En revanche, contre un programme qui n'est pas capable d'"apprendre", un même piège marchera évidemment à tous les coups. Pour éviter ce genre d'attaque, la plupart des programmes d'échecs sérieux sont capables d'analyser le début de la partie et d'éventuellement modifier leur dictionnaire d'ouvertures en conséquences. L'expérience a montré que la qualité du dictionnaire et sa méthode d'utilisation ont une influence déterminante sur la qualité de jeu d'un programme.

    Dictionnaire de fins de parties

Tout comme pour les ouvertures, il existe un certain nombre de configurations de fins de parties pour lesquelles les stratégies sont connues. De plus, lorsque le nombre de pièces restantes sur l'échiquier est suffisamment faible, il devient possible d'explorer de manière exhaustive toutes les possibilités. Par exemple, lorsqu'il ne reste que cinq pièces le nombre de configurations possibles n'est "que" de 160 millions (en tenant compte des symétries), ce qui est tout à fait à la portée des ordinateurs actuels.
De telles analyses ont d'ailleurs mené à certains résultats étonnants et totalement inattendus. Par exemple, il était connu depuis longtemps que lorsqu'il ne reste qu'une dame et un roi contre une tour et un roi, la partie peut être assez facilement gagnée par le joueur qui possède la dame, ce qui conduisait généralement l'adversaire a abandonner la partie. Cependant, l'analyse a montré que la victoire est en fait très difficile et que si le joueur possédant la dame ne connaît pas parfaitement cette fin de partie, il pourra être contraint à une partie nulle par l'adversaire.
L'autre surprise (de taille également) concerne la fin de partie entre un roi et deux fous contre un roi et un cavalier. On a longtemps considéré que cette position menait à la partie nulle, alors que l'ordinateur a montré que ce cas de figure se soldait dans la plupart des cas par la victoire du joueur possédant les fous. Cependant personne actuellement n'a pu prétendre comprendre la méthode à utiliser. Celle-ci semble être une série de mouvements aléatoires qui mène, après un grand nombre de coups, à la prise du cavalier adverse; le mat est ensuite simple pour le joueur qui possède les deux fous.
En pratique, les dictionnaires de fin de parties sont limités aux configurations avec au maximum 5 pièces, car au delà on assiste à une explosion combinatoire.
L'utilisation de ce genre de connaissances par les programmes d'échecs mène cependant parfois à des situations singulières. Par exemple un programme qui a un gros avantage matériel sur l'adversaire peut choisir de sacrifier délibérément sa dame uniquement pour simplifier la configuration de l'échiquier et mener à une configuration référencée comme gagnante dans le dictionnaire de fins de parties. De même, un programme peut refuser catégoriquement les "cadeaux" qui lui sont fait pour éviter de tomber dans une configuration qui amènera à sa défaite de manière quasi-certaine.

    Matériel spécifique

Une fois les stratégies utilisées par l'ordinateur déterminées, il est possible de construire des cartes spécifiques pour réaliser certaines opérations. De même que la plupart des ordinateurs actuels contiennent des cartes graphiques qui savent gérer elles-mêmes les fonctions de base du calcul en 3D, voire même des fonctions plus évoluées comme l'application de textures, des cartes ont été mises au point pour accélérer les programmes d'échecs. Les ordinateurs d'échecs produits par IBM, par exemple, utilisent ce type de matériel spécifique.

    Tables de transpositions

Souvent, une même position peut être atteinte de plusieurs manières différentes. Pour éviter d'avoir a explorer des sous-arbres identiques, une liste des positions atteintes est conservée en mémoire. Lorsqu'une de ces positions est atteinte par un autre chemin, on peut arrêter la recherche sur cette branche.

     Rien en vue à l'horizon

L'effet d'horizon constituait un des principaux problèmes des premiers programmes d'échecs. Dans le cas où l'une de ses pièces était sur le point d'être prise, si le joueur humain repérait le problème suffisamment tôt, il lui était possible de l'éviter en modifiant sa tactique de jeu pour faire "reculer" ce coup dans l'arbre d'exploration avec des déplacements qui retardent ce coup, comme une mise en échec inoffensive, une attaque inutile sur la dame de l'adversaire, etc; jusqu'à ce que le coup remonte suffisamment loin dans l'arbre pour qu'il devienne hors de portée du programme. A ce moment, il devait lui être possible de trouver un déplacement qui permettait d'éviter ce mauvais coup. La plupart des programmes d'échecs actuels évitent ce problème en conservant une liste des meilleurs coups trouvés ("killer moves") et vérifient régulièrement s'il est toujours possible de les atteindre. De la sorte, lorsqu'un "bon" coup est trouvé mais qu'il ne peut être joué de suite, celui-ci est gardé en mémoire pour essayer de le jouer dès que l'occasion se présente.

    Distance

Lorsqu'un programme sait qu'il a partie gagnée (par exemple dans le cas d'une fin de partie avec une dame et roi contre un roi), il peut arriver qu'il se limite à tenter en permanence d'améliorer sa position sans jamais faire de réel progrès. Dans le cas où l'exploration utilise l'algorithme alpha-beta par exemple, le programme peut voir un mat en deux coups et du fait de la coupure introduite par l'algorithme ne pas voir un mat possible en un coup. Cela pourrait passer, sauf si le cas se reproduit au coup suivant, ainsi qu'au suivant, etc. ;-) La méthode classique pour éviter ce problème est très simple. Lorsque l'on détecte un mat possible en N coups, on force au tour suivant de choisir un déplacement qui mène à un mat en N-1 coups. L'utilisation de dictionnaires de fins de parties permet également d'éviter ce problème dans un bon nombre de cas.

    "Tranquillité" de l'échiquier

Si l'exploration est limitée à (par exemple) 8 coups, et qu'une position favorable est trouvée à cette limite, cela peut en fait s'avérer être un très mauvais coup si au tour suivant l'adversaire peut prendre la dame du joueur sans contrepartie. Du fait que l'évaluation d'une position est statique, c'est-à-dire qu'elle ne tient compte que de la position courante, le seul moyen d'éviter ce problème est de poursuivre la recherche un cran plus loin; sachant qu'arrivé là, on se trouvera en face du même problème. La solution classique consiste à diviser l'exploration en deux phases : La phase statique, durant laquelle tous les coups, même ceux qui paraissent les plus mauvais sont examinés ; puis la phase dynamique qui permettra de creuser un peu plus loin si besoin est. Durant cette deuxième phase, seuls les coups intéressants ou menant à la prise d'une pièce sont considérés. De la sorte, l'exploration peut aller jusqu'à 15, voire 20 coups en avance lorsque la situation de l'échiquier l'exige.

    Considérations périphériques

En plus des méthodes énumérées ci-dessus, il faut également tenir compte d'un certain nombre de considérations supplémentaires qui sont plus difficiles à évaluer de manière objective. En voici quelques unes :

    Offres de parties nulles

Dans le cas où l'adversaire propose une partie nulle, dans quelles conditions doit-on accepter? Si l'exploration de l'arborescence découvre une série de coups qui mène à une partie nulle, doit-elle être jouée? Dans quelles situations peut-on ou doit-on proposer une partie nulle? Si l'on découvre que quoi qu'il arrive l'adversaire va faire mat dans 8 coups, peut-on tenter de bluffer et proposer une partie nulle? Lorsque ce genre de décision doit être prise, la situation actuelle de l'échiquier doit bien évidement être prise en compte, mais il faut également tenir compte d'autres paramètres comme le niveau de jeu de l'adversaire ou le score du match en cours (Lors d'un match, une partie gagnée rapporte un point, une partie nulle un demi-point et une défaite zéro point. Le gagnant est le premier qui obtient trois points). Si l'adversaire est un grand maître ou si une partie nulle est suffisante pour gagner le match, une offre de partie nulle est tout à fait acceptable. En revanche si l'adversaire joue avec un niveau assez faible ou si une victoire est indispensable pour gagner le match, alors il vaut peut être mieux refuser l'offre même si les chances de faire mat sont faibles.

    Complexité contre simplicité

L'ordinateur doit apprendre a gérer les éventuelles imperfections de son adversaire (que celui-ci soit humain ou non). C'est-à-dire que dans certains cas, il est préférable de prendre le risque que l'adversaire n'ait pas vu une combinaison gagnante extrêmement obscure et continuer à jouer comme si de rien n'était, plutôt que de tenter de l'éviter à tout prix dans la mesure où cela peut mener à une situation embarrassante. De même, dans certains cas, la meilleure alternative consiste à jouer en ne prenant absolument aucun risque et a attendre que l'adversaire fasse une gaffe. La gestion de ce genre de considérations est extrêmement délicate pour un ordinateur dans la mesure ou ils relèvent de critères totalement subjectifs.

    Gestion du temps

Toutes les parties sérieuses se jouent en temps limité. Les programmes doivent donc apprendre à gérer ce temps au mieux. Ils doivent donc régulièrement comparer l'avancement de leur recherche avec le temps imparti et décider si le meilleur coup trouvé doit être joué ou si plus de temps peut ou doit être consacré à la recherche d'un meilleur coup. Si un coup "suffisamment bon" est trouvé ou si le coup à jouer est "évident", c'est en général une bonne chose de jouer avant que le temps initialement imparti pour le calcul du coup soit écoulé pour économiser du temps qui peut être précieux plus tard dans la partie.

    Résolution de problèmes

La résolution de problèmes d'échecs (du genre "les blancs jouent et font mat en trois coups" ou similaire) est un peu différente des parties classiques. Dans certains cas, le nombre de coups à jouer n'est pas important et il suffit de trouver une combinaison gagnante. Un programme d'échecs peut être transformé en solveur de problèmes en modifiant la fonction d'évaluation pour qu'elle retourne toujours zéro sauf lorsque le mat est atteint.

    Les programmes d'échecs disponibles sous Linux

Il existe une multitude de programmes d'échecs disponibles sous Linux. Les 3 plus intéressants (ie: ceux qui offrent le meilleur niveau de jeu) sont Crafty, GNU Chess et Phalanx. Leurs modes de fonctionnement ainsi que leurs niveaux de jeu respectifs ont été abordés dans l'article "Jouez aux échecs contre Linux" paru dans le numéro précédent. Les 3 sont compatibles avec les interfaces graphiques XBoard et gnome-chess. Maintenant, vous pourrez jouer contre eux en sachant un peu mieux comment ils fonctionnent (Bonne chance ;-)