Les moteurs d’échecs

Histoire

Les premiers programmes de jeux d’Echecs sont nés avec l’avènement de l’informatique dès les années 40. Blitzchess présente un excellent historique.

A partir des années 80, avec l’apparition des ordinateurs personnels les programmes de jeux d’Echecs sont devenus accessibles au grand public et ont très rapidement progressé dans leurs niveaux de jeux, fonctionnalités à un prix de plus en plus abordable voire complètement gratuit.

En Aout 2005, le programme Fruit 2.1 développé par le Français Fabien Letouzey devient vice-champion du monde et montre qu’il demeure l’un des plus fort module au monde. En juillet 2007, l’auteur ouvre au public le code source de son programme. A partir de ce moment, tout s’accélère : on voit apparaitre en l’espace de peu de temps et à tour de rôle de nouveaux modules de plus en plus fort. Il est clair que si nous disposons de très forts programmes à ce jour, Fruit n’y est sans doute pas étranger...

L’originalité de Fruit 2.1 tient du fait que c’est un très fort module avec un nombre de ligne de programmation minimaliste et puissant : une fois compilé, il ne "pèse" que 180 Ko ! C’est dire les progrès algorithmiques dans la recherche des meilleurs coups dans l’arbre des possibilités des variantes.

Protocole entre moteur et interface graphique

Il faut bien faire la distinction entre moteur et interface :

• Le moteur contient tout le code informatique destiné à calculer le meilleur coup pour le module dans une position donnée. Ces programmes ont une personnalité, un style de jeux paramétrable, un nom. Il en existe de tout niveau de jeu. Ils peuvent être commercials ou gratuits.

• L’interface graphique (ou chess gui) est le programme qui va accueillir et faire fonctionner ces moteurs. On peut les faire se rencontrer dans le cadre de l’organisation de tournois entre moteurs. L’interface graphique gère donc tout l’environnement visible par l’utilisateur tel que l’échiquier et affiche des informations issues du calcul des modules (animation de l’échiquier à chaque coup, des variantes, de l’évaluation de la position, de l’utilisation des tablebases, de la profondeur de recherche, etc...)

Le principal avantage pour le programmeur est de se concentrer sur la performance du moteur afin d’en améliorer le niveau de jeu plutôt d’avoir à gérer la représentation visuelle de l’échiquier et le dialogue avec l’utilisateur.

Pour cela le moteur doit parler le même langage avec l’interface graphique grâce à un protocole, c’est-à-dire une norme commune entre l’interface graphique et chaque moteur pour échanger des données telles que les coups d’une partie d’Echecs.

Actuellement, 3 types de protocoles dominent les modules d’échecs :

• Protocole UCI (Universal Chess Interface) est le plus répandu de tous (Arena, Rybka Aquarium, ChessGui, José Chess etc..)
• Protocole Winboard, le premier interface libre (GnuChess, Crafty)
• Protocoles commerciaux (Fritz, Junior, Shredder, Hiarcs, etc... avec une extension .eng ou .exe du moteur)

Livres d’ouverture

Il s’agit d’un répertoire d’ouverture choisi par l’utilisateur dont les modules vont se servir pour jouer leurs premiers coups. Ces coups sont joués instantanément par les modules et doivent conduire à une position équilibrée à la fin du livre. D’une longueur variable (de 5, 10, 15, 20 coups, voir plus), ces livres peuvent être construits à partir d’une ouverture unique ou au contraire intégrer de multiples ouvertures. Ces bibliothèques d’ouverture peuvent occuper une place considérable sur disque par rapport à taille de l’exécutable du moteur.

Les livres d’ouverture peuvent être de différents formats plus ou moins compressés selon l’outil utilisé pour faire des tournois :

• .Abk pour Aréna, l’interface gratuit,
• .Ctg pour Fritz qui est un programme d’échecs commercial.
• .Bin pour Winboard

Les livres d’ouverture sont recommandés pour éviter que le moteur ne choisisse une variante réfutée. Elles sont indispensables à tout moteur d’échecs, apportent plus de variétés dans différentes ouvertures et font gagner énormément du temps car l’ouverture est la phase où l’arbre des coups est le plus large à cause du nombre maximal de pièces.

Les tables de finales

En finale, le nombre de pièces restantes est réduit mais l’arbre de coup doit être plus profond pour envisager par exemple la promotion d’un pion qui n’est encore qu’à sa position de départ.

Les tables de finales court-circuitent directement un arbre extrêmement profond. Elle permettent de résoudre instantanément une finale de 5 pièces (soit les 2 rois+3 autres pièces) et de calculer la distance au mat d’une position donnée. Ainsi, l’utilisation des tablebases permet d’éviter toute simulation dans un arbre ou de prévoir plus rapidement la conversion d’un milieu de jeu vers une finale favorable quand la finale est atteinte dans les feuilles terminales de l’arbre.

Il existe des outils pour générer les tablebases mais le temps de calcul peut prendre plusieurs jours. En pratique, on se sert de tablebases déjà générées et compressées. Parfois l’utilisation des tablebases ne permet d’améliorer que très modestement le niveau de certains modules car ces tables sont souvent trop importantes pour tenir en mémoire. Elles peuvent prendre plusieurs Giga sur le disque dur. C’est pourquoi on ne les installe pas systématiquement.

L’auteur du module Stockfish Tord Romstad considère que personne n’a trouvé le moyen d’utiliser efficacement ces tables de finale. D’après lui, grâce à évolution des technologies actuelles, les processeurs calculent de plus en plus vite alors que le temps d’accès des disques dur est toujours aussi lent qu’avant.

Les principaux formats que l’on retrouve :

• Table de Nalimov
• Gaviota Tablebase (EGTB)
• Robbobases (Triplebases et Totalbases)
• Schredder bases

• Voir le site de Jim ablett pour la mise à jour d’autres moteurs.
• Voir également Wikipédia

La controverse

Les modules dits "open source" sont livrés dans le package compressé avec les fichiers source du programme, ce qui permet à d’autres personnes ayant de bonnes connaissances en programmation échiquéenne d’améliorer le niveau du module en y apportant des modifications, le compilent, puis le distribuent sous un autre nom.

Par exemple :
Stockfish 1.7 -> Tinapa 1.01
Ivanhoe -> Deep saros.

Ces modifications qui sont très mal perçues par une partie de ce petit monde des échecs (et des éditeurs qui ont évidemment un intérêt commercial), provoquent des polémiques dont les discussions sont sans issus et cela d’autant plus que certains modules deviennent encore plus fort que les originaux....
Certains moteurs n’apparaissent tout simplement pas dans les classements (rating list) pour cause de plagiat selon les administrateurs de sites, et certains messages sont censurés des forums (ceux de Rybka entre autre). Il devient compliqué de savoir qui dit vrai puisque les modules actuels se sont pour la plupart inspirées de ceux qui existaient déjà... alors, comment définir ce qu’est un clone dans ce cas ?

La force des moteurs

Comme pour les joueurs humains, pour comparer la force des moteurs, on organise des tournois où les moteurs se rencontrent en duel.

L’organisateur du tournoi ou le spectateur peut visualiser la différence de performance de deux moteurs en comparant leurs profondeurs d’analyse en demi-coups ainsi que leurs nombres de positions calculées par seconde. La profondeur d’analyse est directement liée au ELO. Quand un moteur analyse plus profondément avec deux demi-coups de plus, on peut lui attribuer +100 ELO de plus.
Comparer la profondeur d’Houdini bien plus grande que celle de GnuChess et vous apprendrez à battre GnuChess en jouant comme Houdini.

Cependant certains moteurs préfèrent prendre plus de temps sur une profondeur plus courte. Dans ce cas là, la qualité de la fonction d’évaluation peut être compétitive par rapport à une recherche plus profonde mais c’est rare.
Une fonction d’évaluation de la position idéale n’aurait pas besoin de simulation de coups dans un arbre mais elle serait trop complexe sauf en finale avec les tablebases.
On préfère une fonction d’évaluation plus rapide que l’on peut exécuter à des profondeurs plus importante de l’arbre.
Selon la qualité de la fonction d’évaluation, le moteur saura élaguer les mauvaises branches de l’arbre pour se concentrer directement sur les meilleurs coups comme le ferait un grand maître.

Un critère important est la stabilité de la Principale Variation (PV), c’est-à-dire que le moteur est capable de sélectionner le plus tôt possible le meilleur parcours dans l’arbre, autrement dit le plus optimal pour les deux moteurs. Cela se traduit visuellement par un affichage stable des meilleurs coups simulés de gauche à droite, à comparer avec des variations dans le temps sur les premiers coups pour le moteur le plus faible capable de se remettre en question jusqu’au premier coup de l’analyse.

Liens :

Mise à jour des moteurs :

• Site de Jim Ablett
• WBEC

Classement des Moteurs :

• IPON Rating List
• Franks Chess Page
• CCRL
• Fou numérique

Pour Android :

• Chess for Android

Histoire de clones

• http://computerchessonline.net/103/rybka-3-vs-firebird-1-2-long-time-controls/

Organisation de tournois :

• TCEC par Martin Thoresen
• WBEC
• ChessWAR par Olivier Deville

Commentaires et interviews des programmeurs :

• http://www.schach-welt.de/interviews/interviews
• http://www.blitzchess.fr/fr/programmeurs/index.html

Forum :

• http://www.open-chess.org
• http://lefounumerique.xooit.com/index.php