Applied Concept ARB

Comment les ordinateurs jouent aux échecs

Il y a quelques années, nombreux étaient encore ceux qui prétendaient qu'un ordinateur ne pourrait jamais jouer correctement aux échecs.

Aujourd'hui, la question n'est plus de savoir si un programme sera un jour champion du monde, mais seulement dans combien de temps. Comment donc réfléchissent ces machines, du plus gros des ordinateurs au plus petit appareil du commerce ?

Pour essayer d'y voir clair, suivons une partie de Belle, le meilleur programme du monde, contre un de ses adversaires du dernier championnat nord-américain des ordinateurs.

I. La position

Dans un programme d'échecs, les pièces sont représentées par des nombres (1 = pion, 2 = cavalier, 3 = fou, 4 = tour, 5 = dame, 6 = roi), une case vide est désignée par un zéro. Attention, il ne s'agit pas là d'une valeur (nous y reviendrons plus tard), mais d'une simple étiquette.

Quant à l'échiquier, il est représenté par un tableau ... 12 x 10. Les cases extérieures au terrain légal 8 x 8 sont affectées du nombre 7.
Il est plus facile pour le programme de constater qu'une pièce se dirige vers une case portant cette valeur interdite que de voir qu'elle se promène dans le vide.

D'autre part, les cases sont numérotées de 1 à 120. Les déplacements sont donnés par des nombres qui représentent la différence entre le numéro de la case initiale et celui de la case d'arrivée.

Ainsi, par exemple, l'ensemble des déplacements légaux d'un cavalier est donné par la liste 21, 19, 12, 8 : le mouvement initial classique du Cavalier du Roi blanc (Cg1-f3) correspond ainsi à un déplacement 19 (case de départ = 28, case d'arrivée = 47).

La liste de tous les mouvements légaux est dressée de la sorte.

II. La bibliothèque d'ouvertures

Les blancs viennent de quitter leur bibliothèque d'ouvertures. Jusqu'à présent, ils n'ont fait que jouer des coups issus d'un arbre de variantes inscrit dans leur mémoire.

Ce procédé, qui semble mécanique, pose en fait deux problèmes. Le premier, le plus grave, concerne le choix même des variantes prévues.

Il ne suffit pas de mettre en mémoire les meilleures suites, encore faut-il qu'au moment où le programme quitte son livre, il sache exploiter cet avantage. On connait un exemple où, sur une des machines électroniques du commerce, pourtant de haut niveau, la bibliothèque d'ouvertures comprend une suite comportant un sacrifice de pièce reconnu comme excellent puisque donnant une forte attaque.

En fait, avec le camp adverse, il suffit, après avoir pris la pièce, de jouer un coup médiocre, donc pas prévu dans le programme, pour voir la machine s'effondrer rapidement.

Dès qu'on la sort ainsi de sa bibliothèque, elle reconnait d'ailleurs, si on lui demande d'évaluer sa position, que celle-ci est catastrophique ! C'est peut-être l'une des tâches les plus ardues des programmeurs d'échecs que de sélectionner des débuts compatibles avec le style de leur programme. Kaïssa, considéré il y a quelques années comme l'un des meilleurs programmes du monde, souffrait considérablement de ce défaut. Et pourtant, sa conception avait été supervisée par Botvinnik, ancien champion du monde d'échecs !

Autre problème, la technique même de fa mise en mémoire. Seuls, les très gros ordinateurs ont une capacité suffisante pour conserver des positions. Sur les petits et a fortiori sur les machines électroniques du commerce, les ouvertures ne sont mémorisées que sous la forme d'un enchaînement de coups.

Une simple petite inversion de coups et voici le programme sorti de sa bibliothèque, même s'il se retrouve deux coups plus tard dans la position exacte d'une ouverture dont il connait par cœur les quinze meilleurs coups suivants.

III. L'évaluation

Ici, Belle met 3'21" pour analyser les huit demi-coups suivants et prévoir la variante principale : 14. a5 ; 15. bxa5, Txa5 ; 16. Ff4, Db5 ; 17. Dxb5, çxb5 ; 18.a3 et estime son avantage à l'équivalent d'un dixième de pion. D'où vient cette évaluation ?

La fonction d'évaluation des positions constitue l'âme d'un programme d'échecs.

C'est en effet elle qui lui donne sa personnalité, son expression. Trouver une fonction d'évaluation n'est d'ailleurs pas très aisé. Comment prendre en compte tout ce qui constitue les multiples aspects de la qualité d'une position par rapport à une autre !

La mesure du matériel constitue le noyau d'une telle fonction. A chaque pièce est associée une valeur. Par exemple Roi = 500, Dame = 19, Tour - 10, Fou = 7, Cavalier = 6 et Pion = 2. Evidemment ces valeurs sont relatives. Peu importe que le pion vaille 1, 2 ou ... 37, à condition qu'un Cavalier vaille trois fois plus et une Dame 9, 9,5 ou 10 fois plus. Dans les analyses, on a d'ailleurs pris l'habitude de toujours ramener la valeur du point à 1.

Pour connaître le score d'une position, il suffit d'additionner l'ensemble des pièces de son propre camp et de soustraire celles de l'adversaire. A cette fonction de base, d'autres critères sont associés qui tendent à pondérer ces valeurs : mobilité des pièces, contrôle du centre, position du Roi, etc. D'autre part, ces facteurs peuvent varier au cours de la partie. Par exemple, si le Roi doit être mis à l'abri en début et milieu de partie, il doit au contraire participer activement à la finale.

IV. Position " morte " ?

Cette suite d'échanges pose un problème particulier aux programmes. Ici, par exemple, elle s'étend sur 7 demi-coups.

Imaginons que les blancs arrêtent leur analyse après 6 demi-coups, c'est-à-dire à la position résultant de 20. Txa2. Ils jugeraient cette position exceptionnelle puisqu'ils auraient une Tour de plus. En fait, la réponse des noirs anéantirait ce fol espoir. Il est donc indispensable de poursuivre l'exploration de l'arbre jusqu'à une position où il ne risque pas de se produire de renversement spectaculaire, on dit une position morte.

En fait, s'il est facile de vérifier à la fin de chaque branche qu'il n'y a plus de prise ou d'échec possible, il est extrêmement difficile de détecter alors les menaces stratégiques.

Dans la pratique, un programme décide qu'une position est morte quand, en regardant quelques demi-coups plus loin, il ne décèle pas d'inquiétante variation dans l'évaluation. Ici encore, c'est la science de savoir quand s'arrêter de calculer qui fait les grands joueurs... donc les bons programmes.

V. Des coups surprenants !

Pourquoi pas 33. Rç5 ? En fait, le programme craint les pions doublés après l'éventuelle poussée b5 - b6. C'est là tout le problème de la programmation : on est forcé de construire la fonction d'évaluation avec des critères généraux (ici : les pions doublés sont faibles, donc à éviter). Ce qui fait que dans de nombreux cas particuliers, le résultat soit faible et surtout surprenant.

VI. Mini-Max et Alpha-Bêta

Ici, Belle estime son avantage à 3,03 pions , soit à peu près l'équivalent d'un Cavalier et analyse en 7 min 44 s les 9 demi-coups suivants en suggérant la variante suivante : 33. ... Rb6 ; 34. h5, Tç5 ; 35. Tb4, Td5 ; 36. f4, Ra5 ; 37. Tc4, d3 ; 38. Tç1. Comment un programme peut-il ainsi choisir une suite ?

Dans notre exemple (simplifié -fig 1 et 2), la position initiale est représentée par le sommet de l'arbre. C'est aux blancs de jouer et ils disposent de trois coups possibles : les trois branches qui partent de ce sommet. Pour chacun de ces trois coups, les noirs disposent eux-mêmes de trois réponses possibles. Après un coup des blancs et la réponse des noirs, on se retrouve donc en présence de neuf positions à évaluer (de A à I). Notons que dans la réalité, il en existerait au même stade une moyenne d'un millier !

La méthode du mini-max est simple. On va évaluer toutes les positions. On va retenir, pour chacun des coups blancs, la meilleure réponse noire, c'est-à-dire celle qui laisse la position la plus faible pour les blancs. Entre AA, AB et AC, on ne va considérer que AB qui accorde un avantage de + 0,1 aux blancs (on admet ainsi que les noirs jouent au mieux et ne vont pas choisir une réponse qui laisse aux blancs un avantage supérieur, + 0,3 pour AA ou + 0,6 pour AC). De même, on va retenir la réponse BE (- 7) au coup B et la réponse GG (- 6) au coup C. C'est le stade de minimisation. Si les noirs jouent au mieux (et c'est là une hypothèse indispensable pour bien jouer) on peut donc dire que le coup blanc A vaut + 0,1, le B, - 7 et le C, - 6. Vous l'aurez deviné, on choisit le plus fort, le coup A. C'est le stade de la maximisation. D'o le nom de mini-max pour la méthode.

Le seul défaut de cette méthode est qu'elle oblige à évaluer toutes les positions possibles. Elle souffre ainsi d'une maladie très fréquente en informatique, l'explosion combinatoire .
Si l'on suppose qu'il existe dans une position une moyenne d'un peu plus de 31 coups légaux, il faudra analyser quelque 1 000 positions sur deux demi-coups (le coup des blancs suivi du coup des noirs), un million sur 4 demi-coups et un milliard sur 6 demi-coups !

Heureusement, on a trouvé une méthode qui permettait de diminuer considérablement le nombre de positions à évaluer. Reprenons notre exemple et supposons que le programme ait déjà évalué les positions résultant des coups AA, AB et AC. La plus faible des valeurs est de + 0,1. Ce sera donc la valeur attribuée au coup A. Si à présent le programme évalue la position issue du coup BD et trouve la valeur 0,5. La valeur la plus faible attribuée au coup B sera peut-être inférieure à - 0,5 mais en aucun cas supérieure puisqu'on ne retient que la plus faible. On sait donc déjà que le coup A est supérieur au coup B, sans avoir besoin d'examiner les réponses BE et BF. De la même manière, la valeur - 6 pour CG, encore inférieure à + 0,1, dispense de calculer CH et Cl.

Cette procédure s'appelle Alpha-Bêta. Elle peut, théoriquement, réduire dans les cas les plus favorables le nombre de positions à évaluer à la racine carrée de toutes les positions possibles, par exemple mille sur un million. Cela ne peut se produire que si l'on commence par envisager le coup qui finalement se révélera le meilleur. Il est évident que ce cas optimum théorique n'a que peu de chances de se produire dans la réalité.

En effet, si l'on connaissait le meilleur coup avant l'évaluation... on n'aurait évidemment pas besoin de celle-ci ! Cependant, on comprend l'importance de savoir placer en tête de liste les coups les plus plausibles, les coups-candidats . C'est d'ailleurs ce qui fait la force d'un bon joueur humain... C'est donc là que réside toute la difficulté d'écrire un bon programme !

VII. De bons jugements

Après 39. T x a5 + , R x a5 ; les noirs gagnent la finale sans problème. L'excentrique l'a vu. Bravo !

VIII. Sept coups à l'avance !

Le meilleur coup. Malgré son retard de matériel, Belle sait que sa position est gagnante puisqu'elle l'évalue à + 3,43 (l'équivalent d'un Fou de plus ! ). En 4 min 40 s, le programme a étudié une variante jusqu'à 13 demi-coups !
53. ... ç4 ; 54.h6, Rb2 ; 55. Td1, ç3 ; 56. Rxh7, Rb3 ; 57.Rg7, ç2 ; 58. Txd2, ç1=D; 59.h7, Dc3+ ;60. Rg6.

Fritz 11 préfère 53. ...b5 (+8,28)

IX. La politique du pire

Perd tout de suite, mais la meilleure défense ne sauvait pas la partie : 54. Rxh7, ç3 ; 55. Rg7, Rb2 ; 56. Td1, Rb3 (sinon, après 56. ... ç2 ?? ; 57. Txd2 le pion ç est cloué et ce sont les blancs qui gagnent !)

Les blancs ont vu qu'ils perdaient avec la meilleure suite. C'est l'explication de leurs prochains coups, vraiment ridicules. Pour le programme, ils ne sont pas pires, puisque menant au même résultat, une Dame en moins.

Un joueur humain, lui, résout ce problème... en abandonnant.

Jacques Ferber et Alain Ledoux