Les moteurs d’échecs

Comment fonctionnent les moteurs pour jouer au é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 :

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 :


Exemple d’utilisation des tables de finale, dans la position suivante, les blancs font échecs et mat en 115 coups avec la meilleure défense possible des pièces noires : 1. Nd2 Ke3 2. Nf1+ Kf4 3. Kh3 Kf5 4. Nd2 Ke6 5. Ne4 Kf5 6. Nc5 Kg5 7. Ne6+ Kg6 8. Nd8 Kg5 9. Nf7+ Kg6 10. Ne5+ Kf5 11. Nc6 Ke6 12. Nd8+ Kd6 13. Nf7+ Kd7 14. Kg4 Ke6 15. Nh8 h5+ 16. Kh4 Kd5 17. Nf7 Ke6 18. Ng5+ Kf5 19. Ne7+ Kf6 20. Nc6 Kf5 21. Nh3 Ke6 22. Kg5 Kd5 23. Ne7+ Ke6 24. Ng6 h4 25. Ngf4+ Ke5 26. Kg6 Ke4 27. Kf7 Kf5 28. Ke7 Ke5 29. Kd7 Kd4 30. Kd6 Kc4 31. Ne6 Kb5 32. Kd5 Kb4 33. Nef4 Kb5 34. Nd3 Kb6 35. Nb4 Kb7 36. Kd6 Kb6 37. Na2 Kb5 38. Kd5 Ka4 39. Kc4 Ka3 40. Nb4 Kb2 41. Kd3 Kb3 42. Nc6 Ka4 43. Kc4 Ka3 44. Nd4 Kb2 45. Kb4 Kc1 46. Kc3 Kd1 47. Kd3 Kc1 48. Nb3+ Kb2 49. Nc5 Kc1 50. Na4 Kb1 51. Kd2 Ka2 52. Kc3 Kb1 53. Nc5 Ka2 54. Nd3 Ka3 55. Nb2 Ka2 56. Nc4 Kb1 57. Kd2 Ka2 58. Kc2 Ka1 59. Kb3 Kb1 60. Nb2 Kc1 61. Kc3 Kb1 62. Nd3 Ka2 63. Kb4 Kb1 64. Kb3 Ka1 65. Ne1 Kb1 66. Nf3 Kc1 67. Kc3 Kd1 68. Nf4 h3 69. Nh2 Kc1 70. Nd5 Kd1 71. Ne3+ Kc1 72. Kc4 Kb2 73. Kb4 Ka1 74. Nc4 Ka2 75. Kc3 Kb1 76. Kd2 Ka1 77. Kc1 Ka2 78. Kc2 Ka1 79. Kb3 Kb1 80. Nd2+ Kc1 81. Kc3 Kd1 82. Nb3 Ke1 83. Kd4 Ke2 84. Ke4 Ke1 85. Ke3 Kd1 86. Kd3 Ke1 87. Nd4 Kd1 88. Ne2 Ke1 89. Nc3 Kf2 90. Kd2 Kg2 91. Ke3 Kg3 92. Ne2+ Kg2 93. Nd4 Kg3 94. Ndf3 Kg2 95. Nd2 Kg3 96. Ndf1+ Kh4 97. Kf4 Kh5 98. Kf5 Kh6 99. Kf6 Kh7 100. Ne3 Kh6 101. Neg4+ Kh7 102. Kf7 Kh8 103. Ne3 Kh7 104. Nf5 Kh8 105. Kg6 Kg8 106. Ng7 Kf8 107. Kf6 Kg8 108. Ne6 Kh7 109. Kg5 Kg8 110. Kg6 Kh8 111. Kf7 Kh7 112. Ng4 h2 113. Ng5+ Kh8 114. Ne5 h1Q 115. Ng6#
[diag_echecs]
6N1/8/7p/8/2Nk4/8/7K/8 w - - 0 1
[config]
taille=35

modules au 3/1/11 Auteur Origine TableBases ? open source ? Commercial ?
Bright 0.5 AJ Siemelink - Scorpio egbb non non
Crafty 23.4 Dr. Robert M. Hyatt - Nalimov oui non
Critter 0.9 Richard Vida - EGTB non non
Fire(bird) 1.31 Kramnium (Norman Schmidt) IppoLit family Total&TripleBases non non
Fritz 12 Chessbase - Nalimov non oui
Hiarcs 13 Sigma Chess - Nalimov non oui
Houdini 1.5 Robert Houdart Ippolit/Robbolito, Stockfish and Crafty EGTB non non
Ivanhoe 9999XX The Decembrists Ippolit/Robbolito RobboTripleBases oui non
Komodo 1.3 Don Dailey - non non non
Junior 12 Amir Ban et Shy Bushinsky - Nalimov non oui
Protector 1.4.0 Raimund Heid Fruit Nalimov oui non
shredder 12 Stefan Meyer-Kahlen - shredderbase non oui
Spark 1.0 AJ Siemelink - Scorpio egbb non non
Spike 1.2Turin Ralf Schäfer et Volker Böhm Cheetah and IceSpell Nalimov non non
Stockfish 2.01 Tord Romstad, Marco Costalba, Joona Kiiski Glaurung non oui non

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 :

Classement des Moteurs :

Pour Android :

Histoire de clones

Organisation de tournois :

Commentaires et interviews des programmeurs :

Forum :

Posté le 24 mai 2011 par FREDO, Matt