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é à 1040). 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à 3012 (soit environ
5.3 * 1012) 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 ;-)
|
|
| - Deep Blue v1:
http://www.ibm.com/stretch/eos/deepblue/dbo.phtml - Deep Blue v2: http://www.research.ibm.com/deepblue/ - Newsgroups : rec.games.chess.misc rec.games.chess.computer - Internet Chess Library http://www.freechess.org/ - Site de la revue "Europe Échecs" http://www.echecs.com/ - Algorithme de recherche "alpha-beta" : http://www.epita.fr/~dumesn_r/Les%20algo/alpha.htm - Crafty ftp://news.cis.uab.edu/pub/hyatt/ - GNU Chess http://www.fsf.org/software/chess/chess.html - Phalanx http://www.crosswinds.net/~dobes/phalanx/ - XBoard http://www.research.digital.com/SRC/personnal/Tim_Mann/chess.html |
| Utilisateur de GNU/Linux depuis 1993, Vincent Renardias
est activement impliqué dans son développement depuis 1996
: Développeur de la distribution Debian, auteur de la traduction
Française de l'environnement GNOME, créateur du groupe d'utilisateurs
Linux de Marseille (PLUG). Il continue aujourd'hui activement a promouvoir
le système GNU/Linux en tant que responsable technique de la société
Echo (créatrice du moteur de recherche www.voila.fr).
Vincent Renardias <vincent@echo.fr> |