Mieux comprendre Fritz et Rybka

Il ne s'agit évidemment pas ici de modéliser en quelques lignes le fonctionnement complet des puissants moteurs d'Echecs utilisables de nos jours. Juste d'ouvrir quelques pistes de réflexion - l'article s'adressant à des collégiens (ou à leurs enseignants en mathématiques en vue d'organiser un atelier plus complet). La question de base en est la suivante: sur quelles bases concevoir un programme apte à jouer aux Echecs - et quelles sont les limites/contraintes de cet objectif?

1) Une première approche, basée sur une anticipation "un coup à l'avance":

Supposons que le programme joue avec les Blancs et cherche à trouver un coup de bonne qualité à partir d'une position donnée (appelée P1).

- En premier lieu, il est possible de définir une fonction f de toute position lui attribuant une valeur 'statique' du point de vue des Blancs. Par exemple, on pourra poser que

* f(P)= -10000 si les Blancs sont Echecs et Mat dans la position P

* f(P)=10000 si les Noirs sont Echecs et Mat dans la position P

* Dans tous les autres cas, f(P)=10*(Nombre de Dames Blanches)+5*(Nombre de Tours Blanches)+3*(Nombre de Fous Blancs)+3*(Nombre de Cavaliers Blancs)+(Nombre de Pions Blancs) - 10*(Nombre de Dames Noires)- 5*(Nombre de Tours Noires)-3*(Nombre de Fous Noirs)-3*(Nombre de Cavaliers Noirs)-(Nombre de Pions Noirs)

Ken Thompson (assis), inventeur du système d'exploitation Unix et du language 'B' (ancêtre du C). Il conçut dans les années 70 le programme d'Echecs 'Belle', plusieurs fois vainqueur du Championnat inter-ordinateurs des Etats-Unis. Claude Shannon - à l'origine par ailleurs de travaux fondateurs dans le domaine des Télécommunications - fut un autre grand mathématicien et ingénieur de l'après-guerre pionnier en matière de programmes d'Echecs.

On conçoit que cette fonction est à priori d'autant plus élevée que la position blanche est bonne. Ce n'est cependant pas une très bonne fonction d'évaluation, car elle ne tient pas compte du tout des positions relatives des pièces entre elles. Mais nous nous en contentons dans un premier temps.

Revenons à la position P1. Nous pouvons évaluer f(P1), mais cela ne nous en dit pas plus sur le coup à jouer par le programme. En revanche, le nombre de coups possibles - et de positions qui en découlent - est limité. Admettons qu'il y ait 3 coups possibles, menant aux positions P2, P3 et P4. Nous pourrions dire que nous allons jouer le coup qui maximise la fonction d'évaluation sur P2, P3 et P4. Par exemple, si f(P3)>f(P2) et f(P3)>f(P4), nous allons jouer le coup qui mène à P3.

C'est un choix possible, mais extrêmement limité, car il ne tient pas compte du tout de la réponse des Noirs! Par exemple, si P2 et P4 ne mènent à aucun gain de pièce, et si P3 permet de gagner un pion, le programme choisirait P3 - même si cela permettait aux noirs de prendre par exemple la Dame au coup suivant. Nous allons donc faire un peu mieux.

 

On peut d'aborder noter que les positions accessibles à partir de P2, P3 et P4 sont elles aussi en nombre limité (du fait des contraintes liées aux règles du jeu). Supposons par exemple qu'à partir de P2, les Noirs aient la possibilité de jouer 2 coups (menant aux positions P5 et P6), qu'à partir de P3 ils ne puissent jouer qu'un seul coup (menant à la position P7) et qu'à partir de P4 ils ne puissent jouer que 2 coups (menant aux positions P8 et P9). On a donc construit un arbre de positions possibles liées les unes aux autres.

Une anticipation à un coup revient alors à raisonner de la manière suivante: en supposant que les Noirs adoptent un comportement rationnel, ils joueront à partir de chaque position celle qui minimise la valeur des positions résultantes pour les Blancs. Par exemple, si les Blancs jouent le coup menant à P2, les Noirs joueront raisonnablement le coup menant à P5 si f(P5)<f(P6) et le coup menant à P6 si f(P5)>f(P6).

Pour chaque position P2, P3 et P4, on peut donc anticiper le coup qui sera joué en retour par les Noirs. Et le coup blanc sera celui qui maximise la valeur de f suite au coup Noir suivant.

Par exemple, supposons que:

* A partir de P2, on prévoit que les Noirs joueront le coup menant à P5

* A partir de P3, on prévoit que les Noirs joueront le coup menant à P7

* A partir de P3, on prévoit que les Noirs joueront le coup menant à P9

* Et que en outre f(P9)>f(P5)>f(P7).

Alors, le meilleur coup possible pour les Blancs sera celui menant à P4, car c'est lui qui mènera à la position la plus favorable suite au coup des Noirs. On "maximise pour le compte des Blancs le résultat de la minimisation effectuée par les Noirs". Cette approche est connue sous le nom d'"algorithme Min Max".

Une façon de représenter cette approche est de donner un "poids" à chacune des positions et de remonter ainsi jusqu'à la position initiale. Par exemple, dans le second schéma ci-contre, admettons qu'on ait f(P5)=8, f(P6)=6, f(P7)=5, f(P8)=1 et f(P9)=9. En reprenant la manière de raisonner ci-dessus, il apparaît que la valeur que les Blancs atteindront à partir de P2 est min (8,6)=6 (puisque les Noirs joueront à priori le coup le plus défavorable pour les Blancs. De même, la valeur que les Blancs atteindront à partir de P3 sera 5 et la valeur que les Blancs atteindront à partir de P3 est mlin (1,9)=1.

Au total, la meilleure valeur que les Blancs peuvent espérer est Max (6,5,1)= 6 - et les Blancs vont jouer le coup menant à la position P2.

De manière "mécanique", on peut donc:

* Calculer la valeur de l'ensemble des positions finales possibles.

* Donner un "Poids" à chacune des positions Oranges (celles issues d'un coup blanc) égale au minimum des valeurs des positions bleues qui peuvent être obtenues à partir d'elle.

* Donner un "Poids" à la position initiale égale au maximum des poids des positions Oranges - et décider de jouer le coup menant à la position ayant permis d'obtenir ce poids.

2) Approfondir l'arbre:

Cependant, même avec cette approche, on se heurte encore au côté "statique" de la fonction d'évaluation f. Autrement dit, l'algorithme décrit ne prend pas en compte la capacité des Noirs à anticiper le Coup blanc qui suivra! Pour rémédier à ce défaut, nous allons donc adopter exactement la même idée que plus haut, mais en approfondissant "d'un cran" l'arbre des possibilités. Pour chacune des positions de P5 à P9, il existe en effet un nombre limité de coups blancs possibles, représentés sur le schéma ci-contre entre P10 et P17. (Par exemple, P13 et P14 à partir de P7). Et à partir de chacune des positions possibles, il existe un nombre limité de coups noirs possibles - menant aux positions (allant de P18 à P28 sur le schéma).

On peut très bien définir l'ensemble des ces positions et de leurs liaisons et calculer la valeur de chacune des positions finales en leur appliquant la fonction f.

On peut alors raisonner de la même manière que plus haut:

* Par exemple, si f(P18)<f(P19), on peut considérer que les Noirs joueront le coup menant à P18 à partir de P10. Donc, le mieux que les Blancs peuvent espérer à partir de P10 est f(P18) et de même le mieux qu'ils peuvent espérer à partir de P11 est P20.

* Donc, en étant dans la position P5, ils joueront la position menant à max (f(P18), f(P20)) - ce qui fixe le "poids" de la position P5.

* De même, on peut fixer le poids de la position P6.

* En étant dans la position P2, les Noirs - qui sont censés anticiper tout cela - joueront le coup menant au minimum des poids de P5 et de P6 (puisque ce poids est ce que les Blancs atteindront par la suite à partir de ces positions). Ceci fixe le "poids" de P2.

* Il est ainsi possible de fixer les "poids" de chacune des positions de l'arbre, puis de définir le coup Blanc en choisissant entre P2, P3 et P4 la position ayant le poids maximal.

3) Les contraintes et les limites:

L'approche qui vient d'être décrire revient en fait à "anticiper deux coups à l'avance". Et là surgit un problème de taille. Dans les exemples d'arbres fournis, chaque position ne peut mener qu'à une ou deux autres positions. En cours de jeu, une position d'Echecs mène généralement à 40 positions possibles. Donc, même une anticipation d'un seul coup mène à évaluer un chiffre de l'ordre de 40*40=1600 positions.

Pour une anticipation à 2 coups, ce chiffre passe à 40*40*40*40=1600², soit plus de 2 millions de positions. Le chiffre passe à plus de 4 milliards pour 3 coups anticipés.

Pour fixer les idées, une partie d'Echecs "moyenne" étant de 40 coups, l'exploration de tous les chemins possibles mènerait à un nombre de positions finales de l'ordre de 10128 (à comparer au nombre d'atomes dans l'univers connu, qui est de l'ordre de 1080 ).

En termes de qualité de jeu, on peut considérer qu'un programme prévoyant 4 coups à l'avance aura un elo de l'ordre de 1300. 9 coups à l'avance le situeront à environ 2300 points elo. Il est estimé qu'une profondeur d'arbre de 14 coups est nécessaire pour obtenir 2800 points elo - et un niveau de l'ordre de celui d'un Champion du Monde.

* Un premier point  consiste donc à trouver des moyens de réduire le volume de calculs nécessaires. Pour cela, on peut noter qu'il est possible de "couper des branches de l'arbre". Par exemple, dans le premier exemple ci-dessus, dès qu'il est établi que f(P8)=1, il est inutile de calculer f(P9). En effet, on sait d'emblée que le poids de P4 vaudra 1 ou moins - et donc que P4 aura un poids inférieur à ceux de P2 et P3 quelle que soit la valeur de f(P9). Inutile de savoir jusqu'à quel point P4 est une mauvaise solution! Le procédé peut être largement généralisé.

* La qualité de la fonction d'évaluation constitue un paramètre structurant de la qualité d'un programme.

* Par ailleurs, notamment en début de partie, le programme doit être à même de choisir entre des coups impossibles à différencier en termes de poids. Les programmes incluent donc généralement des bibliothèques d'ouvertures prédéfinies. Ils disposent également souvent de données types adaptées aux fins de parties de manière à analyser plus rapidement des positions "classiques".

* Enfin, la puissance croissante des microprocesseurs a évidemment beaucoup contribué à l'amélioration du niveau de jeu des machines.

Pour finir, voici le PGN d'une partie jouée entre Kasparov et le programme Deep Blue en 1997. Noter que Deep Blue remporta (de manière très médiatisée) ce face à face en 6 parties. Mais sans convaincre de la supérorité absolue de la machine. La première partie ci-dessous se solda d'ailleurs par la victoire de Kasparov.

1. Nf3 d5 2. g3 Bg4 3. b3 Nd7 4. Bb2 e6 5. Bg2 Ngf6 6. O-O c6 7. d3 Bd6 8. Nbd2 O-O 9. h3 Bh5 10. e3 h6 11. Qe1 Qa5 12. a3 Bc7 13. Nh4 g5 14. Nhf3 e5 15. e4 Rfe8 16. Nh2 Qb6 17. Qc1 a5 18. Re1 Bd6 19. Ndf1 dxe4 20. dxe4 Bc5 21. Ne3 Rad8 22. Nhf1 g4 23. hxg4 Nxg4 24. f3 Nxe3 25. Nxe3 Be7 26. Kh1 Bg5 27. Re2 a4 28. b4 f5 29. exf5 e4 30. f4 Bxe2 31. fxg5 Ne5 32. g6 Bf3 33. Bc3 Qb5 34. Qf1 Qxf1+ 35. Rxf1 h5 36. Kg1 Kf8 37. Bh3 b5 38. Kf2 Kg7 39. g4 Kh6 40. Rg1 hxg4 41. Bxg4 Bxg4 42. Nxg4+ Nxg4+ 43. Rxg4 Rd5 44. f6 Rd1 45. g7 1-0

Deep Blue ne commit pas d'erreur manifeste - mais fut victime de l'"effet horizon", cette faiblesse typique des programmes, dépourvus de vision stratégique de long terme malgré leur profondeur d'analyse "tactique".

Cela étant, dans l'immense majorité des cas, la puissance de calcul de la machine - surtout lorsqu'elle est couplée à l'accès à des bases de données de positions - ne laisse aujourd'hui guère de chances à un adversaire humain...